Large economies and two-player games

We characterize the core and the competitive allocations of a continuum economy as strong Nash equilibria of an associated game with only two players.     

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.     

Endogenous mechanisms and Nash equilibrium in competitive contracting games

We model strategic competition in a market with asymmetric information as a noncooperative game in which each firm competes for the business of a buyer of unknown type by offering the buyer a catalog of products and prices. The timing in our model is Stackelberg: in the first stage, given the distribution of buyer types known to all firms and the deducible, type-dependent best responses of the agent, firms simultaneously and noncooperatively choose their catalog offers. In the second stage the buyer, knowing his type, chooses a single firm and product-price pair from that firm’s catalog. By backward induction, this Stackelberg game with asymmetric information reduces to a game over catalogs with payoff indeterminacies. In particular, due to ties within catalogs and/or across catalogs, corresponding to any catalog profile offered by firms there may be multiple possible expected firm payoffs, all consistent with the rational optimizing behavior of the agent for each of his types. The resolution of these indeterminacies depends on the tie-breaking mechanism which emerges in the market. Because each tie-breaking mechanism induces a particular game over catalogs, a reasonable candidate would be a tie-breaking mechanism which supports a Nash equilibrium in the corresponding catalog game. We call such a mechanism an endogenous Nash mechanism. The fundamental question we address in this paper is, does there exist an endogenous Nash mechanism—and therefore, does there exist a Nash equilibrium for the catalog game? We show under fairly mild conditions on primitives that catalog games naturally possess tie-breaking mechanisms which support Nash equilibria.     

Coalitional games with veto players: Consistency, monotonicity and Nash outcomes

Following Dagan et al. [Dagan, N., Volij, O., Serrano, R. (1997). A non-cooperative view on consistent bankruptcy rules, Games Econ. Behav. 18, 55–72], we construct an extensive form game for veto-balanced TU games in which a veto player is the proposer and the other players are responders. The set of Nash outcomes of this extensive form game is described, and compared to solutions of TU games such as the nucleolus, kernel and egalitarian core. We find necessary and sufficient conditions under which the nucleolus of the game is a Nash outcome.     

Integrating the Nash program into mechanism theory

Abstract. The present paper provides a method by which the Nash Program may be embedded into mechanism theory. It is shown that any result stating the support of any solution of a cooperative game in coalitional form by a Nash equilibrium of some suitable game in strategic form can be used to derive the mechanism theoretic Nash-implementation of that solution. Received: 29 June 1999 / Accepted: 3 April 2002     

Stable matchings and the small core in Nash equilibrium in the college admissions problem

Both rematching proof and strong equilibrium outcomes are stable with respect to the true preferences in the marriage problem. We show that not all rematching proof or strong equilibrium outcomes are stable in the college admissions problem. But we show that both rematching proof and strong equilibrium outcomes in truncations at the match point are all stable in the college admissions problem. Further, all true stable matchings can be achieved in both rematching proof and strong equilibrium in truncations at the match point. We show that any Nash equilibrium in truncations admits one and only one matching, stable or not. Therefore, the core at a Nash equilibrium in truncations must be small. But examples exist such that the set of stable matchings with respect to a Nash equilibrium may contain more than one matching. Nevertheless, each Nash equilibrium can only admit at most one true stable matching. If, indeed, there is a true stable matching at a Nash equilibrium, then the only possible equilibrium outcome will be the true stable matching, no matter how different are players' equilibrium strategies from the true preferences and how many other unstable matchings are there at that Nash equilibrium. Thus, we show that a necessary and sufficient condition for the stable matching rule to be implemented in a subset of Nash equilibria by the direct revelation game induced by a stable mechanism is that every Nash equilibrium profile in that subset admits one and only one true stable matching. Received: 30 December 1998 / Accepted: 12 October 2001 This paper is a revision of the paper “Manipulation and Stability in a College Admissions Problem” circulated since 1994. I thank Rich McLean, Abraham Neyman, Mark Satterthwaite, Sang-Chul Suh, and Tetsuji Yamada for helpful discussions. I thank the associate editor and the two anonymous referees for their helpful comments that have greatly improved the paper. I am grateful to the Kellogg G.S.M. at the Northwestern University for the hospitality for my visit. Any errors are mine.     

Strong Nash equilibrium in games with common and complementary local utilities

A rather general class of strategic games is described where the coalitional improvements are acyclic and hence strong Nash equilibria exist: The players derive their utilities from the use of certain facilities; all players using a facility extract the same amount of local utility therefrom, which amount depends both on the set of users and on their actions, and is decreasing in the set of users; the ultimate utility of each player is the minimum of the local utilities at all relevant facilities. Two important subclasses are “games with structured utilities,” basic properties of which were discovered in 1970s and 1980s, and “bottleneck congestion games,” which attracted researchers’ attention quite recently. The former games are representative in the sense that every game from the whole class is isomorphic to one of them. The necessity of the minimum aggregation for the existence of strong Nash equilibria, actually, just Pareto optimal Nash equilibria, in all games of this type is established.     

School choice: Nash implementation of stable matchings through rank-priority mechanisms

We consider school choice problems (Abdulkadiroğlu and Sönmez, 2003) where students are assigned to public schools through a centralized assignment mechanism. We study the family of so-called rank-priority mechanisms, each of which is induced by an order of rank-priority pairs. Following the corresponding order of pairs, at each step a rank-priority mechanism considers a rank-priority pair and matches an available student to an unfilled school if the student and the school rank and prioritize each other in accordance with the rank-priority pair. The Boston or immediate acceptance mechanism is a particular rank-priority mechanism. Our first main result is a characterization of the subfamily of rank-priority mechanisms that Nash implement the set of stable matchings (Theorem 1). Our second main result is a strong impossibility result: under incomplete information, no rank-priority mechanism implements the set of stable matchings (Theorem 2).     

Trading equilibrium in a public good economy with smooth preferences and a mixed measure space of consumers

Lindahl and Nash equilibria are often used in the theory of public good. Shitovitz and Spiegel (1998) present an example of 2-person economy with one private good and one pure public good, where the core efficient Lindahl allocation does not Pareto dominate the (inefficient) Nash allocation. In this paper we introduce the new concept of Trading equilibrium for a general public good economy with smooth preferences and a mixed measure space of consumers. We obtain that this economy admits a unique Trading equilibrium. Moreover, the Trading equilibrium induces a core allocation that strictly Pareto dominates the Nash allocation.     

Maximizing political vote in multiple districts

This paper models a resource allocation problem in the political context. Voters and political candidates of two parties are positioned in each of n given electoral districts. We assume that each voter will vote for the candidate he is more attracted to. This attraction is modeled by an attraction function. Each of the parties now attempts to allocate a finite budget to maximize their objective, which is either the popular vote or the number of districts, in which the party has a majority. Individual scenarios are examined with respect to leader-follower solutions and Nash equilibria. The paper then describes a dynamic model that successively allocates existing funds plus additional donations to candidates in different electoral districts.     

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.     

Double implementation of the Lindahl equilibrium by a continuous mechanism

We consider a class of economies with public goods that have the following properties: (i) The preferences of the agents are convex, interior, and strictly increasing. (ii) The technology for production of public goods is a closed convex cone that satisfies free disposal and an additional mild assumption. No assumptions are made on continuity, completeness or transitivity of preferences. We provide a continuous and feasible mechanism that implements the Lindahl equilibrium by Nash equilibria, and has the following property: For every economy in our class every Nash equilibrium of the game induced by the mechanism is a strong Nash equilibrium.     

A noncooperative foundation of the asymmetric Nash bargaining solution

We consider a noncooperative multilateral bargaining model with heterogeneous time preferences in which the first rejector of a proposal in the current round becomes the proposer in the next round. We show the existence of a stationary subgame perfect equilibrium (SSPE), characterize SSPEs and show the efficiency of SSPEs. We show that any sequence of SSPE payoff profiles converges to the asymmetric Nash bargaining solution weighted by the inverses of discount rates as the bargaining friction vanishes.     

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.     

Mechanism design for a solution to the tragedy of commons

We consider the problem of the tragedy of commons in cooperative production economies, and propose a mechanism to resolve this tragedy, taking into account that the coordinator cannot perfectly monitor each agent’s labor skill and each agent may have an incentive to overstate as well as understate his own skill. Even in such a situation, the mechanism implements the proportional solution (Roemer in Soc Philos Policy 6:74–92, 1989 and Roemer and Silvestre in J Econ Theory 59:426–444, 1993) in Nash and strong equilibria when it is played as a normal form game. Moreover, the mechanism triply implements the solution in Nash, subgame-perfect, and strong equilibria when it is played as a two-stage extensive form game. We are greatly thankful to Semi Koray, William Thomson, and an anonymous referee of this journal for their concrete and helpful comments on improving the paper. An earlier version of this paper was presented at the annual meeting of the Japanese Economic Association held at Hitotsubashi University in October 2001 and at the Conference on Economic Design held at NYU in July 2002. We are grateful to Takehiko Yamato for his useful comments in the former conference. We are also thankful to Tatsuyoshi Saijo, Kotaro Suzumura, and Yoshikatsu Tatamitani for their kind comments.     

库存成本约束下的供应链协调研究

在随机需求下,库存协调研究的核心是达到供应链整体成本的最小化,文中在考虑库存持有成本和缺货惩罚成本的情况下构建了基于供应商和零售商的基准库存水平的成本函数,在此基础上分别比较了集中决策和分散博弈下的纳什均衡最优情况。然后给出一个线性转移支付契约来达到整个供应链的协调,实现了库存成本在销售层面的任意分配。     

Efficient provision of public goods with endogenous redistribution

We study a balanced mechanism that is capable of implementing in Nash equilibrium all the Pareto-efficient individually rational allocations for an economy with public goods. The Government chooses a set of weights directly related to the Lindahl prices corresponding to the Pareto-efficient allocation to be implemented. The mechanism then guarantees that initial endowments are re-allocated so that the chosen vector of Lindahl prices is indeed a Lindahl equilibrium, and implements the corresponding Lindahl allocation. Finally, besides being balanced, our mechanism is simple. Each agent has to declare a desired increase in the amount of public good, and a vector of redistributive transfers of initial endowments (across other agents).Received: 9 May 2003, Accepted: 22 October 2003, JEL Classification: C79, H21, H30, H41We wish to thank Jeremy Edwards, Andrew Postlewaite and Emanuela Sciubba for helpful comments. Of course, any remaining errors are our own.     

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.     

An indifference trap of voting

In this paper strategic situations of voting and abstentions are analysed in a three-candidate voting model where voters are indifferent to various alternatives and candidates are interested in winning the election and seeing their most preferred alternative being realized. A specific decision problem is analysed, described by an Indifference Trap Game, with respect to, e.g., the corresponding Nash equilibria, perfect equilibria, and maximin solution. A second-best outcome is contained in the choice set of all three solutions while the Nash equilibrium concept is compatible with the Pareto efficient outcomes of the game.An alternative scenario where candidates suffer from incumbency but voters still are indifferent to some alternatives also supports the second-best outcome. Again, various solutions concepts are applied. We conclude that indifferent voters imply an eminent coordination problem for the candidates in the given voting game which, in general, ends up in inefficient outcomes. The inherent complexity of the decision situation cannot be sufficiently reduced to single out one and only one outcome.     

Convergence in games with continua of equilibria

In game theory, the question of convergence of dynamical systems to the set of Nash equilibria has often been tackled. When the game admits a continuum of Nash equilibria, however, a natural and challenging question is whether convergence to the set of Nash equilibria implies convergence to a Nash equilibrium. In this paper we introduce a technique developed in Bhat and Bernstein (2003) as a useful way to answer this question. We illustrate it with the best-response dynamics in the local public good game played on a network, where continua of Nash equilibria often appear.