Implementation of stable solutions in a restricted matching market

I analyze the admission mechanism used in Spanish universities. The system is open to strategic manipulation. This is because students are not allowed to express the whole list of available options. However, the mechanism implements the set of stable matchings in Nash equilibrium and the student's optimum in strong equilibrium. The mechanism also implements the students' optimum, in Nash equilibrium, under the class of “non-reverse” preferences. All these properties come from the fact that colleges do not have the opportunity to misrepresent their preferences. Received: 30 June 1995 / Accepted: 31 January 1997     

Manipulation of the Walrasian mechanism in production economies with unbounded short-selling

Hurwicz (1979) and Otani and Sicilian (1982, 1990) characterized the Nash equilibrium allocations of the Walrasian demand manipulation game in successively more general exchange environments. In this paper, I extend the analysis to production economies with short-selling. First, I generalize Hurwicz’s and Otani and Sicilian’s theorem that any allocation at which each agent’s consumption bundle lies above her true offer curve can be supported in Nash equilibrium. I then show that for finite economies of any size the set of such allocations is often topologically large.Received: 17 January 2003, Accepted: 4 April 2005, JEL Classification: D51, D82For comments on this and earlier versions of the paper, I wish to thank Rick Bond, Bhaskar Chakravorti, Tom Gresik, Costas Syropoulos and William Thomson. I would especially like to thank Mike Jerison for helping to overcome a difficulty with a previous version. Also, the comments of the anonymous referees are gratefully acknowledged.     

Partnership-enhancement and stability in matching problems

In two-sided matching problems, we consider “natural” changes in preferences of agents in which only the rankings of current partners are enhanced. We introduce two desirable properties of matching rules under such rank-enhancements of partners. One property requires that an agent who becomes higher ranked by the original partner should not be punished. We show that this property cannot always be met if the matchings are required to be stable. However, if only one agent changes his preferences, the above requirement is compatible with stability, and moreover, envy-minimization in stable matchings can also be attained. The other property is a solidarity property, requiring that all of the “irrelevant” agents, whose preferences as well as whose original partners’ preferences are unchanged, should be affected in the same way; either all weakly better off or all worse off. We show that when matchings are required to be stable, this property does not always hold.     

Imitation and price competition in a differentiated market

We study the stable market outcome that evolves in a spatially differentiated market when price-competing firms choose actions by imitation of the most profitable firm. We compare and contrast the stable outcomes under two imitation procedures: one, where each firm immediately imitates the most profitable firm, and the other when a firm imitates another firm only if it is more profitable while being “sufficiently similar” (in context of the market segment it operates in) or “sufficiently close”. In either case, the symmetric pure strategy Nash equilibrium is always a stable outcome. However, when imitation of the most profitable firm is immediate and market differentiation is ‘moderate’, states with prices lower than the Nash equilibrium are also stable. In contrast, when imitation of the most profitable firm is more gradual and market differentiation is below a threshold, states with prices above the Nash equilibrium are also stable. Thus, while competitive evolutionary pressure in this imitation based model does result in the Nash equilibrium always being stable, other outcomes may be stable as well. Interestingly, the states that are stable under gradual imitation give the firms a higher profit than the stable states under immediate imitation.     

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.     

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).     

Agreement toward stability in matching markets

For firms with responsive preferences, we prove that the set of stable matchings unanimously preferred by workers to any firm quasi-stable matching has a lattice structure. This follows from a generalization of the Decomposition Lemma. The result does not hold when firms have q-substitutable preferences. Nevertheless, we show that the set of stable matchings unanimously preferred by workers to a firm quasi-stable matching contains an element which is unanimously least preferred by workers, and most preferred by firms. When a firm quasi-stable matching is fed into our extension of the Deferred Acceptance algorithm (where firms propose), the existence of this matching guarantees the success of the algorithm.     

Countervailing power? Collusion in markets with decentralized trade

We consider the collective incentives of buyers and sellers to form cartels in markets with decentralized trade and pairwise bargaining. Cartels are coalitions of buyers or sellers that limit market participation and compensate inactive members for their abstention. In stable market outcomes, cartels set Nash equilibrium quantities and cartel memberships are immune to deviations. The set of stable market outcomes is non-empty and its full characterization is provided. Stable market outcomes are of two types: (i) at least one cartel restrains trade and market participation is balanced; (ii) only one cartel is active and it reduces trade slightly below the opponent’s.     

A bargaining set for roommate problems

Since stable matchings may not exist, we propose a weaker notion of stability based on the credibility of blocking pairs. We adopt the weak stability notion of Klijn and Massó (2003) for the marriage problem and we extend it to the roommate problem. We first show that although stable matchings may not exist, a weakly stable matching always exists in a roommate problem. Then, we adopt a solution concept based on the credibility of the deviations for the roommate problem: the bargaining set. We show that weak stability is not sufficient for a matching to be in the bargaining set. We generalize the coincidence result for marriage problems of Klijn and Massó (2003) between the bargaining set and the set of weakly stable and weakly efficient matchings to roommate problems. Finally, we prove that the bargaining set for roommate problems is always non-empty by making use of the coincidence result.     

The Blocking Lemma for a many-to-one matching model

The Blocking Lemma identifies a particular blocking pair for each non-stable and individually rational matching that is preferred by some agents of one side of the market to their optimal stable matching. Its interest lies in the fact that it has been an instrumental result to prove key results on matching. For instance, the fact that in the college admissions problem the workers-optimal stable mechanism is group strategy-proof for the workers and the strong stability theorem in the marriage model follow directly from the Blocking Lemma. However, it is known that the Blocking Lemma and its consequences do not hold in the general many-to-one matching model in which firms have substitutable preference relations. We show that the Blocking Lemma holds for the many-to-one matching model in which firms’ preference relations are, in addition to substitutable, quota q-separable. We also show that the Blocking Lemma holds on a subset of substitutable preference profiles if and only if the workers-optimal stable mechanism is group strategy-proof for the workers on this subset of profiles.     

Observable implications of Nash and subgame-perfect behavior in extensive games

We provide necessary and sufficient conditions for observed outcomes in extensive game forms, in which preferences are unobserved, to be rationalized first, weakly, as a Nash equilibrium and then as the unique subgame-perfect equilibrium. Thus, one could use these conditions to find that play is (a) consistent with subgame-perfect equilibrium, or (b) not consistent with subgame-perfect behavior but is consistent with Nash equilibrium, or (c) consistent with neither.     

Coalitional stability in the location problem with single-dipped preferences: An application of the minimax theorem

This study considers a situation in which agents choose the location of a public facility from a street according to a given mechanism. Agents have single-dipped preferences over a set of feasible locations. We analyze coalitional behavior for any given mechanism for this situation. We identify a necessary and sufficient condition for a mechanism to possess a strong Nash equilibrium by applying the minimax theorem of von Neumann and Morgenstern (1944). We introduce a class of core solutions and show that these solutions are characterized by strong Nash implementability. As a byproduct of these results, we propose a simple mechanism that implements any core solution in strong Nash equilibria.     

Is having a unique equilibrium robust?

We investigate whether having a unique equilibrium (or a given number of equilibria) is robust to perturbation of the payoffs, both for Nash equilibrium and correlated equilibrium. We show that the set of n  -player finite games with a unique correlated equilibrium is open, while this is not true of Nash equilibrium for n>2$n>2$. The crucial lemma is that a unique correlated equilibrium is a quasi-strict Nash equilibrium. Related results are studied. For instance, we show that generic two-person zero-sum games have a unique correlated equilibrium and that, while the set of symmetric bimatrix games with a unique symmetric Nash equilibrium is not open, the set of symmetric bimatrix games with a unique and quasi-strict symmetric Nash equilibrium is.     

Stable many-to-many matchings with contracts

We consider several notions of setwise stability for many-to-many matching markets with contracts and provide an analysis of the relations between the resulting sets of stable allocations for general, substitutable, and strongly substitutable preferences. Apart from obtaining “set inclusion results” on all three domains, we introduce weak setwise stability as a new stability concept and prove that for substitutable preferences the set of pairwise stable matchings is nonempty and coincides with the set of weakly setwise stable matchings. For strongly substitutable preferences the set of pairwise stable matchings coincides with the set of setwise stable matchings.     

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.     

Incentivizing resilience in financial networks

When banks extend loans to each other, they generate a negative externality in the form of systemic risk. They create a network of interbank exposures by which they expose other banks to potential insolvency cascades. In this paper, we show how a regulator can use information about the financial network to devise a transaction-specific tax based on a network centrality measure that captures systemic importance. Since different transactions have different impact on creating systemic risk, they are taxed differently. We call this tax a systemic risk tax (SRT). We use an equilibrium concept inspired by the matching markets literature to show analytically that this SRT induces a unique equilibrium matching of lenders and borrowers that is systemic-risk efficient, i.e. it minimizes systemic risk given a certain transaction volume. On the other hand, we show that without this SRT multiple equilibrium matchings exist, which are generally inefficient. This allows the regulator to effectively stimulate a ‘rewiring’ of the equilibrium interbank network so as to make it more resilient to insolvency cascades, without sacrificing transaction volume. Moreover, we show that a standard financial transaction tax (e.g. a Tobin-like tax) has no impact on reshaping the equilibrium financial network because it taxes all transactions indiscriminately. A Tobin-like tax is indeed shown to have a limited effect on reducing systemic risk while it decreases transaction volume.     

Good neighbors are hard to find: computational complexity of network formation

We investigate the computational complexity of several decision problems in a simple strategic game of network formation. We find that deciding if a player has a strategy that guarantees him a certain payoff against a given strategy profile of the other players is an NP-complete problem. Deciding if there exists a strategy profile that guarantees a certain aggregate payoff is also NP-complete. Deciding if there is a Nash equilibrium in pure strategies which guarantees a certain payoff to each player is NP-hard. The problem of deciding if a given strategy profile is a Nash equilibrium is investigated as well. We would like to thank both referees for valuable corrections and suggestions and one referee in particular for a very detailed and beneficial critique. We thank Colin de la Higuera for fruitful discussions. Support by the French Ministry for Youth, Education and Research, through project SCSHS-2004-04 is gratefully acknowledged.     

Strategic behavior in non-atomic games

In order to remedy the possible loss of strategic interaction in non-atomic games with a societal choice, this study proposes a refinement of Nash equilibrium, strategic equilibrium. Given a non-atomic game, its perturbed game is one in which every player believes that he alone has a small, but positive, impact on the societal choice; and a distribution is a strategic equilibrium if it is a limit point of a sequence of Nash equilibrium distributions of games in which each player’s belief about his impact on the societal choice goes to zero. After proving the existence of strategic equilibria, we show that all of them must be Nash. We also show that all regular equilibria of smooth non-atomic games are strategic. Moreover, it is displayed that in many economic applications, the set of strategic equilibria coincides with that of Nash equilibria of large finite games.     

Large but finite games with asymmetric information

Carmona considered an increasing sequence of finite games in each of which players are characterized by payoff functions that are restricted to vary within a uniformly equicontinuous set and choose their strategies from a common compact metric strategy set. Then Carmona proved that each finite game in an upper tail of such a sequence admits an approximate Nash equilibrium in pure strategies.     

A mechanism implementing the proportional solution

We consider the problem of a commonly owned technology which transforms a single input into a single output. We are interested in implementing a social choice rule called theproportional solution. We introduce a mechanism which implements the proportional solution in Nash, strong (Nash) and undominated Nash equilibria. In the mechanism each agent announces only two numbers which can be interpreted as the total output and her share of the total input-output combination. This paper was originally titled "Doubly implementing the proportional solution." I would like to thank my advisor William Thomson for his detailed comments and suggestions. I would also like to thank Jeffrey Banks and Sung-Whee Shin for their comments. Two anonymous referees and an editor’s comments improved this paper substantially.