Incentives and implementation in allocation problems with externalities

https://doi.org/10.1016/j.jmateco.2021.102613Get rights and content

Highlights

  • We study incentives and implementation in allocation problems with externalities.

  • No α-individually rational and efficient social choice function is implementable in dominant strategies.

  • Under a mild restriction, the α-core is implementable in Nash equilibrium.

  • The α-core is the minimal Nash implementable social choice rule.

Abstract

We study the implementation of social choice rules in environments with externalities. We prove the impossibility of implementing efficient and α-individually rational rules in dominant strategies. We prove that the α-core is implementable in Nash equilibrium under mild restrictions and discuss the maximality and the minimality of our results. We extend our analysis to weakly efficient rules.

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 (TTC 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 R˜ 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 R˜ 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 R˜. In this case, the α-core is the maximal implementable, α-individually rational, and efficient social choice rule with domain R˜.

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 R˜. 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 N,eiiN,Af,RiiN. N is the finite set of agents, we assume n=|N|3.5 For every iN, ei is the endowment of agent i, which is the finite set of objects that initially belong to i. We assume eiej= for all i,jN, ij. An allocation is a correspondence a:NiNei such that for all xiNei, |a1(x)|=1. We identify an allocation a with the n-tuple aiiN. Let iN. We denote by ai, the n1-tuple ajjN{i}. 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 TTC works as follows: 1. Each agent i points at her “top (most preferred)” house. Draw an arrow from each agent i to the agent who holds the top house of i. 2. 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 NE. We start introducing additional notation and results. Let iN and let Ri preferences over Af. Let La,Ri=bAf:aRib be the lower contour set of aAf at Ri. A SCR, Ω:DAf is (Maskin) monotonic if, for all R,RD and all aAf such that aΩR and La,RiLa,Ri for all iN, then aΩR. Let iN and XAf. 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.

Cited by (2)

  • Notes 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.

View full text