Incentives and implementation in allocation problems with externalities☆
Introduction
We study the non-cooperative implementation of cooperative solutions to allocation problems with externalities. That is, we are interested in environments in which the agents care not only about what they receive, but also about what other agents get. An example is the mask allocation in the midst of a viral pandemic where the use of the masks reduces contagion (see, among others Prather et al., 2020). Other relevant examples include housing markets and roommate problems in which the agents are concerned also about their potential neighbors, labor markets in which workers care about their colleagues, and school choice problems in which families care about their children’s classmates.
We are interested in implementing social choice rules that are efficient and guarantee individual participation. Among those, the core is of focal importance in cooperative game theory. An allocation is in the core if it is resistant to group deviations. Sönmez (1999) proves that a strategy-proof and individually rational social choice function exists if and only if the core is essentially single valued, whenever the core is nonempty. Unfortunately, the core is often empty in markets with externalities. The reason is that the standard definition of blocking assumes that, when a coalition deviates, the agents outside the coalition will not react. The assumption is overly optimistic from the point of view of the deviating agents and multiplies the number of blocking coalitions.1 In our model, the members of a coalition do not make any assumption about the goods assigned to the agents outside the coalition and they act prudently. More precisely, we assume that a coalition blocks an allocation if each member of the coalition prefers the worst allocation consistent with the deviation to the proposed allocation.2 We call this kind of blocking -blocking and the -core is the set of -unblocked allocations.3 The -core has been introduced in Aumann and Peleg (1960) and Aumann (1961).4 Several works have assumed prudent behavior for contexts with externalities. Among them, Sasaki and Toda (1996) and Contreras and Torres-Martínez (2021) study pairwise stability in marriage markets with externalities and in roommate problems with externalities, respectively.
First, we study implementation in dominant strategies. Hong and Park (2018) consider a model with externalities and prove that if the agents care about their allocation prior to the other agents’, the Top Trading Cycle ( from now on) generates an efficient, individually rational, and strategy-proof, social choice function. We prove that their result do not generalize to arbitrary externalities: no -individually rational and efficient mechanism is implementable in dominant strategies in allocation problems with externalities.
This negative result leads us to consider the implementation of the -core correspondence in Nash equilibrium. This research question relates to Sönmez (1996) who shows that the core correspondence is implementable in Nash equilibrium in a class of assignment problems in which the core is nonempty and agents have strict preferences over the objects, thus without externalities. Kara and Sönmez, 1996, Kara and Sönmez, 1997 prove the Nash implementability of stable (and thus core) solutions in one-to-one and many-to-one matching markets, respectively, under strict preferences over partners. Fonseca-Mairena and Triossi (2019) prove the Nash implementability of stable solutions in one-to-one matching markets with externalities, in which pairs act prudently when deviating. In the last case, stable allocations are not necessarily efficient and thus do not belong to the core.
We prove that the -core is not implementable in Nash equilibrium under general preferences. Restricting our attention to the domain in which the -core equals the weak -core and both are nonempty, we prove that the -core correspondence is implementable in Nash equilibrium. When preferences are strict the -core equals the weak -core. This condition is satisfied, for example, in the marriage market with externalities studied in Sasaki and Toda (1996), the roommate problem with externalities studied in Contreras and Torres-Martínez (2021), and the housing market with externalities studied in Mumcu and Saglam (2007), among others. The equality between the -core and the weak -core is also satisfied in marriage markets and roommate problems without externalities and strict preferences over agents (see Sönmez, 1996). Our result thus applies to all such markets when the -core is nonempty. Also, relaxing the efficiency requirement to weak efficiency, we prove the Nash implementability of the weak -core correspondence on the domain of preference in which it is nonempty.
We then study the limits of implementation. In the subdomain of in which the preferences are strict the -individually rational and efficient social choice rule is implementable in Nash equilibrium. We prove that this is no longer true in . In this case, the -core is the maximal implementable, -individually rational, and efficient social choice rule with domain .
Finally, we prove that the -core is the minimal monotonic (and thus implementable), -individually rational, and efficient solution, under an additional assumption which limits the externalities that can occur when agents keep their endowments. Thus, under this assumption, the -core is the unique implementable, -individually rational, and efficient social choice rule with domain . We also consider the limits of implementation of -individually rational and weakly efficient social choice rules.
The paper is organized as follows. In Section 2 we introduce the model. In Section 3 we consider implementation in dominant strategies. In Section 4 we study implementation in Nash equilibrium. In Section 5 we conclude. The Appendix includes complementary results and examples about the environments we consider.
Section snippets
The model
An allocation problem is a quadruple . is the finite set of agents, we assume .5 For every , is the endowment of agent , which is the finite set of objects that initially belong to . We assume for all , . An allocation is a correspondence such that for all , . We identify an allocation with the -tuple . Let . We denote by , the -tuple . With abuse of
Implementation in dominant strategies: an impossibility result
In house allocation problems without externalities, the Top Trading Cycles mechanism (Shapley and Scarf, 1974, Roth and Postlewaite, 1977) is an individually rational and efficient mechanism. The works as follows: . Each agent points at her “top (most preferred)” house. Draw an arrow from each agent to the agent who holds the top house of . . There is at least one cycle in the graph. Reallocate each house to the agent belonging to the cycle pointing to it and remove all the involved
Implementation in Nash equilibrium
In this section we relax the equilibrium requirement and study the possibility of implementing efficient and -individually rational correspondences in . We start introducing additional notation and results. Let and let preferences over . Let be the lower contour set of at . A , is (Maskin) monotonic if, for all and all such that and for all , then . Let and . Monotonicity is a necessary condition for
Conclusions
We have proved that no -individually rational and efficient mechanism is implementable in dominant strategies in allocation problems with externalities, when the set of admissible preferences of each agent includes all strict preferences. In particular, every strategy-proof and efficient mechanism does not provide all agents the right incentives to participate: for some preference profile, one agent will be strictly better off by not participating to the mechanism, independently on the
Declaration of Competing Interest
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
References (27)
- et al.
Implementability via protective equilibria
J. Math. Econ.
(1982) - et al.
Protective behavior in matching models
Games Econ. Behav.
(1995) On the existence of stable roommate matchings
Games Econ. Behav.
(2000)Strategy-proofness and essentially single-valued cores revisited
J. Econ. Theory
(2018)A generalization of scarf’s theorem: -core existence theorem without transitivity or completeness
J. Econ. Theory
(1992)- et al.
Nash implementation of matching rules
J. Econ. Theory
(1996) - et al.
Stable one-to-one matchings with externalities
Math. Soc. Sci.
(2010) - et al.
Weak versus strong domination in a market with indivisible goods
J. Math. Econom.
(1977) - et al.
Two-sided matching problems with externalities
J. Econ. Theory
(1996) Strategy-proofness and arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions
J. Econ. Theory
(1975)
On cores and indivisibility
J. Math. Econ.
Implementation in generalized matching problems
J. Math. Econom.
On Nash implementation of social choice correspondences
Games Econ. Behav.
Cited by (2)
Coalitional stability in matching problems with externalities and random preferences
2024, Games and Economic BehaviorNotes on marriage markets with weak externalities
2023, Bulletin of Economic Research
- ☆
This paper is a modified version of the second chapter of the Ph.D. dissertation of the first author at University of Chile. We thank the co-editor, Satoru Takahashi, two anonymous referees, Nicolás Figueroa, Daniel Hojman, Rahmi Ilkilic, Antonio Romero-Medina, and Juan Pablo Torres-Martínez for useful comments. In particular, we thank a referee for suggesting the preference profile employed in Example 3 and spotting mistakes of previous versions of the paper. Fonseca-Mairena and Triossi acknowledge financial support from the Institute for Research in Market Imperfections and Public Policy, ICM IS130002, Ministerio de Economía, Fomento y Turismo, Chile. Triossi acknowledges financial support from Ca’ Foscari University of Venice, Italy under project MAN.INS_TRIOSSI and from Ministerio de Ciencia e Innovación, Spain under project AEI PID2020-118022GB-I00.