Selecting contestants for a rent-seeking contest

In this paper, a contest designer derives profits from aggregate effort exerted by the contestants. I develop a revelation mechanism that enables the contest designer to select a subset of contestants from a pool of candidates in a way that maximizes her profits, even though she is uninformed about the candidates’ valuations for the contest prize. I prove the existence of an incentive compatible and individually rational mechanism. I solve the designer’s problem by using a three-stage game. At Stage 0, the designer designs a mechanism. At Stage 1, candidates participate in the mechanism then a subset of candidates become contestants. Lastly, at Stage 2, information is revealed and the contestants participate in a contest. I show that the optimal size of a contest depends on contestants’ types, the cost of the prize to the designer and on the marginal cost that a contestant imposes on the designer. Contrary to models in which an entry fee s access to the contest, the designer can elicit truthful revelations by imposing revelation costs, and in turn is able to select the optimal subset of contestants.     

Natural implementation with semi-responsible agents in pure exchange economies

We study Nash implementation by natural price–quantity mechanisms in pure exchange economies when agents have intrinsic preferences for responsibility. An agent has an intrinsic preference for responsibility if she cares about truth-telling that is in line with the goal of the mechanism designer besides her material well-being. A semi-responsible agent is an agent who, given what her opponents do, acts in an irresponsible manner when a responsible behavior poses obstacles to her material well-being. The class of efficient allocation rules that are Nash implementable is identified provided that there is at least one agent who is semi-responsible. The Walrasian rule is shown to belong to that class.     

Revenue in contests with many participants

We show that in a contest with a single prize, the expected effort made by the k$k$th highest valuation participant bounds the sum of the expected efforts made by all of the participants with valuations less than the k$k$th highest valuations. We also show that in the limit case of a contest with m$m$ prizes, the expected effort made by the k$k$th highest valuation participant when the bidders are risk-neutral is greater than the expected effort in the risk-averse case.     

A two-person game of timing with random termination

We consider a marksmanship contest in which the first contestant to hit his target wins and the contest is to be terminated at a random timeT with cdfH(t). The model is evidently an extension of the classical discrete fire duel to the timing problem under an uncertain environment. It is shown that the uncertainty on the termination of the contest has influence on the equilibrium strategies and the equilibrium values.     

Three-player sequential contests with asymmetric valuations

We compare the total effort of simultaneous versus (partially and completely) sequential contests with three players competing for asymmetric valuations. We show that the total effort is always maximized by the fully sequential contest, where the strongest player moves first, the second, strongest second, and the weakest third. On the other hand, the total effort is minimized when the players move in the opposite direction (weakest first, strongest last), but the optimal contest may be simultaneous, have a single follower, or be fully sequential.     

On Reverse Hypercontractivity

We study the notion of reverse hypercontractivity. We show that reverse hypercontractive inequalities are implied by standard hypercontractive inequalities as well as by the modified log-Sobolev inequality. Our proof is based on a new comparison lemma for Dirichlet forms and an extension of the Stroock–Varopoulos inequality. A consequence of our analysis is that all simple operators ${L = Id - \mathbb{E}}$ as well as their tensors satisfy uniform reverse hypercontractive inequalities. That is, for all q < p < 1 and every positive valued function f for ${t \geq \log \frac{1-q}{1-p}}$ we have ${\| e^{-tL}f\|_{q} \geq \| f\|_{p}}$ . This should be contrasted with the case of hypercontractive inequalities for simple operators where t is known to depend not only on p and q but also on the underlying space. The new reverse hypercontractive inequalities established here imply new mixing and isoperimetric results for short random walks in product spaces, for certain card-shufflings, for Glauber dynamics in high-temperatures spin systems as well as for queueing processes. The inequalities further imply a quantitative Arrow impossibility theorem for general product distributions and inverse polynomial bounds in the number of players for the non-interactive correlation distillation problem with m-sided dice.     

Ideals generated by reverse lexicographic segments

Let k be a field, and let S = k[x ₁, …, x _n ] be the polynomial ring in x ₁, …, x _n with coefficients in the field k. We study ideals of S which are generated by reverse lexicographic segments of monomials of S. An ideal generated by a reverse lexicographic segment is called a completely reverse lexicographic segment ideal if all iterated shadows of the set of generators are reverse lexicographic segments. We characterize all completely reverse lexicographic segment ideals of S and determine conditions under which they have a linear resolution.     

Effort Games and the Price of Myopia

We consider Effort Games, a game‐theoretic model of cooperation in open environments, which is a variant of the principal‐agent problem from economic theory. In our multiagent domain, a common project depends on various tasks; carrying out certain subsets of the tasks completes the project successfully, while carrying out other subsets does not. The probability of carrying out a task is higher when the agent in charge of it exerts effort, at a certain cost for that agent. A central authority, called the principal, attempts to incentivize agents to exert effort, but can only reward agents based on the success of the entire project. We model this domain as a normal form game, where the payoffs for each strategy profile are defined based on the different probabilities of carrying out each task and on the boolean function that defines which task subsets complete the project, and which do not. We view this boolean function as a simple coalitional game, and call this game the underlying coalitional game. We suggest the Price of Myopia (PoM) as a measure of the influence the model of rationality has on the minimal payments the principal has to make in order to motivate the agents in such a domain to exert effort. We consider the computational complexity of testing whether exerting effort is a dominant strategy for an agent, and of finding a reward strategy for this domain, using either a dominant strategy equilibrium or using iterated elimination of dominated strategies. We show these problems are generally #P‐hard, and that they are at least as computationally hard as calculating the Banzhaf power index in the underlying coalitional game. We also show that in a certain restricted domain, where the underlying coalitional game is a weighted voting game with certain properties, it is possible to solve all of the above problems in polynomial time. We give bounds on PoM in weighted voting effort games, and provide simulation results regarding PoM in another restricted class of effort games, namely effort games played over Series‐Parallel Graphs (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Overconvergent modular sheaves and modular forms for GL 2/F

Given a totally real field F and a prime integer p which is unramified in F, we construct p-adic families of overconvergent Hilbert modular forms (of non-necessarily parallel weight) as sections of, so called, overconvergent Hilbert modular sheaves. We prove that the classical Hilbert modular forms of integral weights are overconvergent in our sense. We compare our notion with Katz’s definition of p-adic Hilbert modular forms. For F = ?, we prove that our notion of (families of) overconvergent elliptic modular forms coincides with those of R. Coleman and V. Pilloni.     

(k,c) – coloring via Column Generation

In this paper we study the (k,c) – coloring problem, a generalization of the well known Vertex Coloring Problem (VCP). We propose a new formulation and compare it computationally with another formulation from the literature. We also develop a diving heuristic that provides with good quality results at a reasonable computational effort.     

Silent-noisy marksmanship contest with random termination

We consider a marksmanship contest in which Player I has one silent bullet, whereas Player II has one noisy bullet, the first contestant to hit his target wins, and the contest is to be terminated at a random timeT with cdfH(t). The model is a silent-noisy version of our previous paper (Ref. 8), and an extension of silent-noisy duel to nonzero-sum games of timing under an uncertain environment. It is shown that the uncertainty on the termination of the contest has influence on the equilibrium strategies and the equilibrium values, but the silent player has no advantages over the noisy one, in such a nonzero-sum model.The author thanks Professor M. Sakaguchi, Osaka University, who contributed to the research on mathematical decision-making problems and expresses appreciation for his continuous encouragement and guidance. The author also thanks Professor G. Kimeldorf, The University of Texas at Dallas, who invited the author to his university. Finally, the author expresses appreciation to Professors K. Sugahara and W. Fukui, Himeji Institute of Technology, for their encouragement and support.     

Comparison of tightly and loosely coupled decision paradigms in multiagent expedition

Frameworks for cooperative multiagent decision making may be divided into those where each agent is assigned a single variable (SVFs) and those where each agent carries an internal model, which can be further divided into loosely coupled frameworks (LCFs) and tightly coupled frameworks (TCFs). In TCFs, agent communication interfaces render their subuniverses conditionally independent. In LCFs, either agents do not communicate or their messages are semantically less restricted. SVFs do not address the privacy issue well. LCF agents cannot draw from collective knowledge as well as TCF agents can. However, disproportional effort has been dedicated to SVFs and LCFs, which can be attributed partially to unawareness of the computational advantages of TCFs over performance, efficiency and privacy. This work aims to provide empirical evidence of such advantages by comparing recursive modeling method from LCFs and collaborative design network from TCFs, both of which are decision-theoretic and the latter of which is based on graphical models. We apply both to a testbed, multiagent expedition, resolve technical issues encountered, and report our experimental evaluation.     

Rankin-Cohen brackets on pseudodifferential operators

Pseudodifferential operators that are invariant under the action of a discrete subgroup Γ of SL(2,R) correspond to certain sequences of modular forms for Γ. Rankin-Cohen brackets are noncommutative products of modular forms expressed in terms of derivatives of modular forms. We introduce an analog of the heat operator on the space of pseudodifferential operators and use this to construct bilinear operators on that space which may be considered as Rankin-Cohen brackets. We also discuss generalized Rankin-Cohen brackets on modular forms and use these to construct certain types of modular forms.     

Coordinating multi-location production and customer delivery

We study two parallel machine scheduling problems with equal processing time jobs and delivery times and costs. The jobs are processed on machines which are located at different sites, and delivered to a customer by a single vehicle. The first objective considered is minimizing the sum of total weighted completion time and total vehicle delivery costs. The second objective considered is minimizing the sum of total tardiness and total vehicle delivery costs. We develop several interesting properties of an optimal scheduling and delivery policy, and show that both problems can be solved by reduction to the Shortest-Path problem in a corresponding network. The overall computational effort of both algorithms is O(n ^m2+m+1) (where n and m are the number of jobs and the number of machines, respectively) by the application of the Directed Acyclic Graph (DAG) method. We also discuss several special cases for which the overall computational effort can be significantly reduced.     

The impact of constant effort harvesting on the dynamics of a discrete‐time contest competition model

In this paper, we study a general discrete‐time model representing the dynamics of a contest competition species with constant effort exploitation. In particular, we consider the difference equation x _{n +1}=x _n f (x _{n ?k} )?h x _n where h >0, k ∈{0,1}, and the density dependent function f satisfies certain conditions that are typical of a contest competition. The harvesting parameter h is considered as the main parameter, and its effect on the general dynamics of the model is investigated. In the absence of delay in the recruitment (k =0), we show the effect of h on the stability, the maximum sustainable yield, the persistence of solutions, and how the intraspecific competition change from contest to scramble competition. When the delay in recruitment is 1 (k =1), we show that a Neimark‐Sacker bifurcation occurs, and the obtained invariant curve is supercritical. Furthermore, we give a characterization of the persistent set.     

Invariant bilinear forms on a vertex algebra

In this paper we construct a linear space that parameterizes all invariant bilinear forms on a given vertex algebra with values in a arbitrary vector space. Also we prove that every invariant bilinear form on a vertex algebra is symmetric. This is a generalization of the result of Li (J. Pure Appl. Algebra 96(3) (1994) 279), who proved this for the case when the vertex algebra is non-negatively graded and has finite dimensional homogeneous components.As an application, we introduce a notion of a radical of a vertex algebra. We prove that a radical-free vertex algebra A is non-negatively graded, and its component A₀ of degree 0 is a commutative associative algebra, so that all structural maps and operations on A are A₀-linear. We also show that in this case A is simple if and only if A₀ is a field.     

Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling

We extend the classical linear assignment problem to the case where the cost of assigning agent j to task i is a multiplication of task i’s cost parameter by a cost function of agent j. The cost function of agent j is a linear function of the amount of resource allocated to the agent. A solution for our assignment problem is defined by the assignment of agents to tasks and by a resource allocation to each agent. The quality of a solution is measured by two criteria. The first criterion is the total assignment cost and the second is the total weighted resource consumption. We address these criteria via four different problem variations. We prove that our assignment problem is NP-hard for three of the four variations, even if all the resource consumption weights are equal. However, and somewhat surprisingly, we find that the fourth variation is solvable in polynomial time. In addition, we find that our assignment problem is equivalent to a large set of important scheduling problems whose complexity has been an open question until now, for three of the four variations.     

Explosion of Jump-Type Symmetric Dirichlet Forms on ℝ d

We give a sufficient condition for a class of jump-type symmetric Dirichlet forms on ? ^d to be conservative in terms of the jump kernel and the associated measure. Our condition allows the coefficients dominating big jumps to be unbounded. We derive the conservativeness for Dirichlet forms related to symmetric stable processes. We also show that our criterion is sharp by using time changed Dirichlet forms. We finally remark that our approach is applicable to jump-diffusion type symmetric Dirichlet forms on ? ^d .     

Strategies in competing subset selection

We address an optimization problem in which two agents, each with a set of weighted items, compete in order to minimize the total weight of their solution sets. The latter are built according to a sequential procedure consisting in a fixed number of rounds. In every round each agent submits one item that may be included in its solution set. We study two natural rules to decide which item between the two will be included. We address the problem from a strategic point of view, that is finding the best moves for one agent against the opponent, in two distinct scenarios. We consider preventive or minimax strategies, optimizing the objective of the agent in the worst case, and best-response strategies, where the items submitted by the opponent are known in advance in each round.     

Quality and entry deterrence

We analyze the role of quality, which we define as an attribute of a product that increases consumers’ willingness to buy, as a competitive tool in a quality-price setting. We consider an incumbent’s entry-deterrence strategies using quality as a deterrent when faced by a potential entrant. We investigate settings motivating the incumbent to blockade the entrant (i.e., prevent entry without extra effort), deter the entrant (i.e., prevent entry with extra effort), or accommodate the entrant (i.e., allow the entry to take place). We identify conditions under which the incumbent may actually over-invest in quality to deter entrance. More interestingly, we also identify conditions under which the incumbent may decrease his quality investment to make it easier for the entrant to penetrate the market. Our model sheds light on entry scenarios of particular platform product markets such as the entry of Xbox to the video game console market.