Nash implementing social choice rules with restricted ranges

We consider Nash implementation of social choice rules with restricted ranges, i.e., where some of the available alternatives are chosen at no preference profile. We show that the appropriate adaptation of Maskin monotonicity to this context depends on the range of the mechanisms: the wider is this range, the weaker is the monotonicity condition to be used. As a result, mechanisms employing outcome functions which allow for out-of-range alternatives at off-equilibrium messages can Nash implement social choice rules which fail to be Nash implementable by mechanisms whose ranges are restricted to the range of the social choice rule to be implemented. The Walrasian social choice correspondence is a particular instance of this. Moreover, social choice rules which are not Maskin monotonic can be “monotonized” by the addition of artificial out-of-range alternatives—a point we illustrate through Solomon’s Dilemma.     

Feasible implementation of taxation methods

This paper studies implementation of taxation methods in one-commodity environments in which the incomes of the agents are unknown to the planner. Feasibility out of equilibrium imposes that the mechanism depend on the environment. We present two mechanisms. The first one, which requires complete information, implements every taxation method in Nash, strong and coalition-proof equilibrium. The second, where informational requirements are relaxed, implements a large class of consistent and monotone methods in subgame perfect equilibrium. Neither mechanism employs the off-equilibrium devices used by the general theory. Under fully private information no method is implementable. Received: 12 March 1997 / Accepted: 21 July 1998     

Full Nash implementation of neutral social functions

This paper characterizes neutral social functions that are fully implementable. A neutral social function must be monotonic and simple to be fully implementable under either the Nash equilibrium concept or the strong Nash equilibrium concept. If a neutral social function is monotonic and simple, then the social function is fully implementable by a set of Nash equilibria. For finite alternative sets a neutral social function will be fully implementable by a set of strong Nash equilibria if and only if it is monotonic, simple and dictatorial.     

Implementation with coalition formation: A complete characterization

The basic difference between Nash and strong (Nash) implementations originates from the possibility of coalition formation. The results of Nash implementation are applicable when agents in no group can cooperate (or form a coalition) and those of strong implementation are applicable when agents in every group can cooperate. In the present paper we consider an environment where agents in some groups can cooperate and agents in other groups cannot. We completely characterize the set of correspondences that are implementable in such a general environment, and we provide an algorithm which enables us to verify whether a correspondence satisfies the condition that appears in the characterization results. By applying the algorithm in an exchange economy, we show that the core, the definition of which depends on the possibility of cooperation, is implementable in the equilibrium corresponding to the cooperation possibility.     

Virtual Nash implementation with admissible support

A social choice correspondence (SCC) is virtually implementable if it is ?$?$-close (in the probability simplex) to some (exactly) implementable correspondence [Abreu, D., Sen, A., 1991. Virtual Implementation in Nash Equilibrium. Econometrica 59, 997–1021] proved that, without restriction on the set of alternatives receiving strictly positive probability at equilibrium, every SCC is virtually implementable in Nash Equilibrium. We study virtual implementation when the supports of equilibrium lotteries are restricted. We provide a necessary and sufficient condition, imposing joint restrictions on SCCs and admissible supports. Next, we discuss how to construct supports, and we underline an important difficulty. Finally, we study virtual implementation when the support is restricted to the efficient or individually rational alternatives.     

Implementation and orderings of public information

We explore the relationship between public information and implementable outcomes in an environment characterized by random endowments and private information. We show that if public signals carry no information about private types, then an exact relationship holds: a more informative public signal structure, in the sense of Blackwell, induces a smaller set of ex-ante implementable social choice functions. This holds for a large set of implementation standards, including Nash implementation, and Bayesian incentive compatibility. The result extends the notion, dating to Hirshleifer (1971), that public information can have negative value to an endowment economy under uncertainty.Received: 23 September 2003, Accepted: 30 July 2004, JEL Classification: D80Colin M. Campbell: I thank two referees and seminar participants at the 2002 meetings of the Society for Economic Design, at the 2003 Winter Meetings of the Econometric Society, and at Yale University for helpful input.     

机制设计中的履约理论研究综述

显示原理和履约理论是机制设计理论中的两大基石。履约理论把社会选择规则和博弈论联系起来，确保计划者预设的社会目标可以实现。马斯金首先提出了纳什履约理论的充分必要条件，即马斯金单调性和无否决权，随后其他学者提出了其它均衡策略的履约条件。文章论述了履约理论的产生背景和过程，分析了完全信息和不完全信息两种情形下不同的均衡策略履约条件及其精炼，并讨论了履约理论的局限性和未来的研究方向。     

On the robustness of strategy proof mechanisms

Following the Gibbard-Satterthwaite impossibility theorem, the incentives literature has explored restrictions on the domains of unknown characteristics which enable the implementation of some social choice rules by dominant strategy incentive compatible mechanisms. This paper makes precise the intuitive idea that, even when restrictions on preferences take the extreme form of finite- dimensional parametrizations, implementable social choice rules display a lack of robustness and in a sense made explicit are rare.     

Natural and double implementation of public ownership solutions in differentiable production economies

This paper examines the implementation of two public ownership solutions in convex production economies with differentiable production functions. The two public ownership solutions we focus on are the proportional and equal benefit solutions. Two “natural” mechanisms which doubly implement the proportional and equal benefit solutions respectively in Nash and strong Nash equilibria are proposed without assuming free disposal. Received: 7 May 1996 / Accepted: 1 December 1998     

On Maskin monotonicity of solution based social choice rules

Howard (J Econ Theory 56:142–159, 1992) argues that the Nash bargaining solution is not Nash implementable, as it does not satisfy Maskin monotonicity. His arguments can be extended to other bargaining solutions as well. However, by defining a social choice correspondence that is based on the solution rather than on its realizations, one can overcome this shortcoming. We even show that such correspondences satisfy a stronger version of monotonicity that is even sufficient for Nash implementability.     

Efficiency and truthfulness with Leontief preferences. A note on two-agent,two-good economies

In exchange economies where agents have private information about their preferences, strategy-proof and individually rational social choice functions are in general not efficient. We provide a restricted domain, namely the set of preferences representable by Leontief utility functions, where there exist mechanisms which are strategy-proof, efficient and individually rational. In two-agent, two-good economies we are able to provide an even stronger result. We characterize the class of efficient and individually rational social choice functions, which are fully implementable in truthful strategies.Received: 28 April 2003, Accepted: 23 June 2003, JEL Classification: D51, D71The author thanks Matthew Jackson, Jordi Massó and James Schummer for fruitful discussions, William Thomson for many valuable comments on an earlier version. A particular thank to Salvador Barberá for his fundamental help.     

Multiproduct price competition with heterogeneous consumers and nonconvex costs

This paper extends the oligopolistic model of price competition to environments with multiple goods, heterogeneous consumers, and arbitrary continuous cost functions. A Nash equilibrium in mixed strategies with an endogenous sharing rule is proven to exist. It is also shown that, in environments with fixed costs and constant marginal costs, all (symmetric and asymmetric) equilibria exhibit price dispersion across stores. Furthermore, the paper identifies scenarios in which prices will necessarily be random. In these markets, stores keep each other guessing because, given the fixed costs, they would incur a loss if their price strategies were anticipated and beaten by competitors. This is interpreted as an important economic feature that is possibly behind random price promotions such as weekly specials.     

Switching from complete to incomplete information

We construct an elementary mechanism [Dutta, B., Sen, A., Vohra, R., 1995. Nash implementation through elementary mechanisms in economic environments. Review of Economic Design 1, 173–203] that Nash implements the constrained Walrasian correspondence. We extend it to incomplete and non-exclusive information economies by enlarging the message space of agents. In addition, measurability restrictions on allocations with respect to prices proper to constrained rational expectations equilibria are imposed in the outcome function. We show that by imposing such restrictions, the mechanism Bayesian implements the constrained rational expectations equilibrium correspondence. This result shows game-theoretic connections between these two market equilibrium concepts. However, these connections are obtained at the price of strong restrictions on the behavior of agents.     

Implementation in generalized matching problems

We search for (Nash) implementable solutions on a class of one-to-one matching problems which includes both the housing market (Shapley and Scarf, Journal of Mathematical Economics, 1974, 1, 23–28) and marriage problems (Gale and Shapley, American Mathematical Monthly, 1962, 69, 9–15). We show that the core correspondence is implementable. We show, furthermore, that any solution that is Pareto efficient, individually rational, and implementable is a supersolution of the core correspondence. That is, the core correspondence is the minimal solution that is Pareto efficient, individually rational, and implementable. A corollary of independent interest in the context of the housing market is that the core correspondence is the only single-valued solution that is Pareto efficient, individually rational, and implementable.     

Implementation of Pareto efficient allocations

This paper considers Nash implementation and double implementation of Pareto efficient allocations for production economies. We allow production sets and preferences are unknown to the planner. We present a well-behaved mechanism that fully implements Pareto efficient allocations in Nash equilibrium. The mechanism then is modified to fully doubly implement Pareto efficient allocations in Nash and strong Nash equilibria. The mechanisms constructed in the paper have many nice properties such as feasibility and continuity. In addition, they use finite-dimensional message spaces. Furthermore, the mechanism works not only for three or more agents, but also for two-agent economies.     

Implementation of optimal contracts under adverse selection

This paper studies a 2-agent, 2-type principal-multiagent model of adverse selection under the assumption that the agents each have complete information. We construct a mechanism implementing the first-best contracts in Nash equilibrium that: satisfies a condition related to individual rationality, is renegotiation-proof, has a small-sized message space, achieves unique implementation and satisfies undomination of Nash equilibrium strategies. Moreover, we prove that other requirements which relate to individual rationality (different from the one satisfied by our mechanism) are not compatible with implementation of the first-best contracts. Received: 27 July 1998 / Accepted: 26 May 2000     

Implementability via protective equilibria

We present a notion of non-cooperative strategic equilibrium for games generated by social choice functions, and fully characterize the class of those functions which are directly implementable under this equilibrium concept. Correct preference revelation turns out to always be such an equilibrium for the games generated by this class of implementable functions.     

Adaptive learning in an asymmetric auction: genetic algorithm approach

Agent-based simulations are performed to study adaptive learning in the context of asymmetric first-price auctions. Non-linearity of the Nash equilibrium strategies is used to investigate the effect of task complexity on adaptive learning by varying the degree of approximation the agents can handle. In addition, learning in different information environments is explored. Social learning allows agents to imitate each other’s bidding strategies based on their relative success. Under individual learning agents are limited to their own experience. We observe convergence to steady states near the predicted equilibrium in all cases. The ability to learn non-linear functions helps the agents with a non-linear equilibrium strategy but hurts the agents with an almost linear one. Better information about the opponent population has a relatively modest impact. A larger number of strategies to experiment with and an ability to systematically compare strategies by holding a number of factors constant have a comparatively stronger beneficial effect.     

The endowment game when n = 2

This paper considers a well defined problem in the implementation literature: A planner wants to re-allocate goods among two agents but she does not know each agent’s initial endowment of goods. We completely characterize social choice functions that can be implemented by feasible mechanisms in Nash equilibria in this n = 2 case.     

Repeated implementation and complexity considerations

A game form is commitment-free if single actions of players do not have physical consequences, i.e., affect the continuation game. Such game can be thought to represent inifinite interaction with complete patience. A choice rule can be Nash implemented via a commitment-free mechanism if and only if it coincides with the feasible set of a normal form game. However, when players are complexity averse (in the lexicographic sense), then any Nash implementable choice rule becomes available. I am very grateful to Matt Jackson and a referee for their comments. I also thank Klaus Kultti and Hannu Salonen for useful conversations.