Weak monotonicity and Bayes–Nash incentive compatibility

An allocation rule is called Bayes–Nash incentive compatible, if there exists a payment rule, such that truthful reports of agents' types form a Bayes–Nash equilibrium in the direct revelation mechanism consisting of the allocation rule and the payment rule. This paper provides a characterization of Bayes–Nash incentive compatible allocation rules in social choice settings where agents have multi-dimensional types, quasi-linear utility functions and interdependent valuations. The characterization is derived by constructing complete directed graphs on agents' type spaces with cost of manipulation as lengths of edges. Weak monotonicity of the allocation rule corresponds to the condition that all 2-cycles in these graphs have non-negative length. For the case that type spaces are convex and the valuation for each outcome is a linear function in the agent's type, we show that weak monotonicity of the allocation rule together with an integrability condition is a necessary and sufficient condition for Bayes–Nash incentive compatibility.     

The Dynamic Vickrey Auction

We study the efficient allocation of a single object over a finite time horizon. Buyers arrive randomly over time, are long-lived, and have independent private values. The valuation of a buyer may depend on the time of the allocation in an arbitrary way. We construct an incentive compatible mechanism in which (A) there is a single financial transaction (with the buyer), (B) ex-post participation constraints are fulfilled, (C) there is no positive transfer to any agent and (D) payments are determined online. We exploit that under the efficient allocation rule, there is a unique potential winning period for each buyer. This reduces the multidimensional type to one dimension and the payment of the winner can be defined as the lowest valuation for the potential winning period, with which the buyer would have won the object. In a static model, this payment rule coincides with the payment rule of the Vickrey Auction.     

Information acquisition and full surplus extraction

It is well known that when agents' types are correlated, the mechanism designer can extract the entire surplus. This creates an incentive for agents to acquire information about other agents' types. Robust lotteries (are payment schemes that) support full extraction and partially robust lotteries support efficient implementation in the presence of information acquisition opportunities. Necessary and sufficient conditions for existence of robust and partially robust lotteries are derived. If an agent's information signal spans other agents' types then robust lotteries do not exist. However, if all agents report their signal realizations then robust lotteries exist in an extended type space.     

A characterization of virtual Bayesian implementation

We provide a characterization of virtual Bayesian implementation in pure strategies for environments satisfying no-total-indifference. A social choice function in such environments is virtually Bayesian implementable if and only if it satisfies incentive compatibility and a condition we term virtual monotonicity. The latter is weaker than Bayesian monotonicity—known to be necessary for Bayesian implementation. Virtual monotonicity is weak in the sense that it is generically satisfied in environments with at least three alternatives. This implies that in most environments virtual Bayesian implementation is as successful as it can be (incentive compatibility is the only condition needed).     

Optimal combinatorial mechanism design

We consider an optimal mechanism design problem with several heterogenous objects and interdependent values. We characterize ex post incentives using an appropriate monotonicity condition and reformulate the problem in such a way that the choice of an allocation rule can be separated from the choice of the payment rule. Central to the analysis is the formulation of a regularity condition, which gives a recipe for the optimal mechanism. If the problem is regular, then an optimal mechanism can be obtained by solving a combinatorial allocation problem in which objects are allocated in a way to maximize the sum of virtual valuations. We identify conditions that imply regularity using the techniques of supermodular optimization.     

Profit sharing in unique Nash equilibrium: Characterization in the two-agent case

Two agents jointly operate a decreasing marginal returns technology to produce a private good. We characterize the class of output-sharing rules for which the labor-supply game has a unique Nash equilibrium. It consists of two families: rules of the serial type which protect a small user from the negative externality imposed by a large user, and rules of the reverse serial type, where one agent effectively employs the other agent's labor. Exactly two rules satisfy symmetry; a result in sharp contrast with Moulin and Shenker's characterization of their serial mechanism as the unique cost-sharing rule satisfying the same incentives property [Moulin, H., Shenker, S., 1992. Serial cost sharing. Econometrica 60 (5), 1009–1037]. We also show that the familiar stand-alone test characterizes the class of fixed-path methods under our incentives criterion [Friedman, E.J., 2004. Strong monotonicity in surplus sharing. Econ. Theory 23, 643–658].     

Coalitional Bayesian Nash implementation in differential information economies

Summary. A mechanism coalitionally implements a social choice set if any outcome of the social choice set can be achieved as a coalitional Bayesian Nash equilibrium of a mechanism and vice versa. We say that a social choice set is coalitionally implementable if there is a mechanism which coalitionally implements it. Our main theorem proves that a social choice set is coalitionally implementable if and only if it is interim individually rational, interim efficient, coalitional B ayesian incentive compatible, and satisfies a coalitional Bayesian monotonicity condition as well as a closure condition. As an application of our main result, we show that the private core and the private Shapley value of an economy with differential information are coalitionally implementable. Received: January 12, 1998; revised version: March 30, 2000     

A Risk‐Dominant Allocation: Maximizing Coalition Stability

This paper presents a rule to allocate a coalition’s worth for superadditive games with positive externalities. The allocation rule awards each member their outside payoff, plus an equal share of the surplus. The resulting allocation maximizes coalition stability. Stable coalitions are Strong Nash equilibria since no subset of members has an incentive to leave. Similarly, no subset of non‐members has an incentive to join a stable coalition if the game is concave in this region. The allocation is risk‐dominant. All stable coalitions are robust to the maximum probability of 50% that players’ deviate from their individual best‐responses. The paper compares the allocation to the Shapley value and the Nash bargaining solution, and illustrates why these traditional rules result in small coalitions when applied to issues such as international environmental agreements.     

The communication cost of selfishness

We consider how many bits need to be exchanged to implement a given decision rule when the mechanism must be ex post or Bayesian incentive compatible. For ex post incentive compatibility, the communication protocol must reveal enough information to calculate monetary transfers to the agents to motivate them to be truthful (agents' payoffs are assumed to be quasilinear in such transfers). For Bayesian incentive compatibility, the protocol may need to hide some information from the agents to prevent deviations contingent on the information. In both settings with selfish agents, the communication cost can be higher than in the case in which the agents are honest and can be relied upon to report truthfully. The increase is the “communication cost of selfishness.” We provide an exponential upper bound on the increase. We show that the bound is tight in the Bayesian setting, but we do not know this in the ex post setting. We describe some cases where the communication cost of selfishness proves to be very low.     

Subgame perfect implementation: A necessary and almost sufficient condition

We present a necessary and almost sufficient condition for subgame perfect implementation of social choice correspondences. In societies with at least three individuals, any social choice correspondence which satisfies no veto power and our necessary Condition α is subgame perfect implementable. Thus Condition α is analogous to monotonicity which, by Maskin's celebrated characterization, is necessary and, in a similar way, almost sufficient for Nash implementation.     

Core concepts in economies where information is almost complete

Summary. The paper analyzes the properties of cores with differential information, as economies converge to complete information. Two core concepts are investigated: the private core, in which agents' net trades are measurable with respect to agents' private information, and the incentive compatible core, in which coalitions of agents are restricted to incentive compatible allocations. Received: March 15, 2000; revised version: August 24, 2000     

Ex post implementation

We analyze the problem of fully implementing a social choice set in ex post equilibrium. We identify an ex post monotonicity condition that is necessary and—in economic environments—sufficient for full implementation in ex post equilibrium. We also identify an ex post monotonicity no veto condition that is sufficient. Ex post monotonicity is satisfied in all single crossing environments with strict ex post incentive constraints.We show by means of two classic examples that ex post monotonicity does not imply nor is it implied by Maskin monotonicity. The single unit auction with interdependent valuations is shown to satisfy ex post monotonicity but not Maskin monotonicity. We further describe a Pareto correspondence that fails ex post monotonicity but satisfies Maskin monotonicity.     

The robustness of the independent private value model in Bayesian mechanism design

Summary. In a Bayesian model of group decision-making, dependence among the agents' types has been shown to have a beneficial effect on the design of incentive compatible mechanisms that achieve the efficient choice associated with complete information. This effect is shown here to depend as much upon the use of large monetary transfers among the agents as it does upon dependence: if the transfers are bounded in magnitude, then nonexistence in the case of independence of an efficient, incentive compatible, ex ante budget-balanced and interim individually rational mechanism is robust to the introduction of a small amount of dependence among types. This robustness result supports the use of the simplifying assumption of independence in mechanism design. Received: October 28, 1996; revised version: May 28, 1997     

Ironing without control

I extend Myerson?s [R. Myerson, Optimal auction design, Math. Oper. Res. 6 (1981) 58–73] ironing technique to more general objective functions. The approach is based on a generalized notion of virtual surplus which can be maximized pointwise even when the monotonicity constraint implied by incentive compatibility binds. It is applicable to quasilinear principal-agent models where the standard virtual surplus is weakly concave in the allocation or appropriately separable in the allocation and type. No assumptions on allocation rules are required beyond monotonicity.     

Maskin's Theorem with limited veto power

We weaken the no-veto power condition of Maskin [Maskin, E.,1999. Nash equilibrium and welfare optimality. Rev. Econ. Stud. 66, 23–38] to limited veto power, and prove that any monotonic social choice rule is Nash implementable if it satisfies this weaker condition. The result is obtained by using the canonical Maskin mechanism without modification. An immediate corollary is that the weak core is Nash implementable in any coalitional game environment. An example is given to show that the strong core need not be implementable, even when it is monotonic.     

Equilibrium bids in practical multi-attribute auctions

This article proposes a nonlinear scoring rule which transforms multiple attributes of a bid into comparable dimensionless ones. Practically, the buyer can use it to select the most competitive winner. For risk-neutral bidders, we characterize a symmetric Bayes–Nash equilibrium and find that as the number of bidders increases the equilibrium quality improves, whereas the equilibrium price decreases.     

Strong Equilibrium in Congestion Games

[6]introduced the class of congestion games and proved that they always possess a Nash equilibrium in pure strategies. Here we obtain conditions for the existence of a strong equilibrium in this class of games, as well as for the equivalence of Nash and strong equilibria. We also give conditions for uniqueness and for Pareto optimality of the Nash equilibrium. Except for a natural monotonicity assumption on the utilities, the conditions are expressed only in terms of the underlying congestion game form. It turns out that avoiding a certain type of bad configuration in the strategy spaces is essential to positive results.Journal of Economic LiteratureClassification Numbers: C71, C72, D62.     

Nash implementing non-monotonic social choice rules by awards

Summary. By a slight generalization of the definition of implementation (called implementation by awards), Maskin monotonicity is no more needed for Nash implementation. In fact, a weaker condition, to which we refer as almost monotonicity is both necessary and sufficient for social choice correspondences to be Nash implementable by awards. Hence our framework paves the way to the Nash implementation of social choice rules which otherwise fail to be Nash implementable. In particular, the Pareto social choice rule, the majority rule and the strong core are almost monotonic (hence Nash implementable by awards) while they are not Maskin monotonic (hence fail to be Nash implementable in the standard framework).Received: 12 April 2004, Revised: 18 March 2005, JEL Classification Numbers: D 79.I thank François Maniquet, Efe Ok and Ipek Ozkal-Sanver for their valuable contributions. The paper is part of a project on Electoral System Design supported by Bilgi University Research Fund.     

Achieving efficiency with manipulative bargainers

Two agents bargain over the allocation of a bundle of divisible commodities. After strategically reporting utility functions to a neutral arbitrator, the outcome is decided by using a bargaining solution concept chosen from a family that includes the Nash and the Raiffa–Kalai–Smorodinsky solutions. When reports are restricted to be continuous, strictly increasing and concave, it has been shown that this kind of “distortion game” leads to inefficient outcomes. We study the distortion game originated when agents are also allowed to claim non-concave utility functions. Contrasting with the previous literature, any interior equilibrium outcome is efficient and any efficient allocation can be supported as an equilibrium outcome of the distortion game. In a similar fashion to the Nash demand game we consider some uncertainty about the opponent's features to virtually implement the Nash bargaining solution.     

Probability Logic for Type Spaces

Using a formal propositional language with operators “individual i assigns probability at least α” for countably many α, we devise an axiom system which is sound and complete with respect to the class of type spaces in the sense of Harsanyi (1967–1968, Management Science, 14 159–182). A crucial inference rule requires that degrees of belief be compatible for any two sets of assertions which are equivalent in a suitably defined natural sense. The completeness proof relies on a theorem of the alternative from convex analysis, and uses the method of filtration by finite sub-languages. Journal of Economic Literature Classification Numbers: D80, D82.