Skip to main content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

11.10.2022 | Original Paper

Binary mechanism for the allocation problem with single-dipped preferences

verfasst von: Fumiya Inoue, Hirofumi Yamamura

Erschienen in: Social Choice and Welfare

Einloggen, um Zugang zu erhalten
share
TEILEN

Abstract

In this study, we consider the problem of fairly allocating a fixed amount of a perfectly divisible resource among agents with single-dipped preferences. It is known that any efficient and strategy-proof rule violates several fairness requirements. We alternatively propose a simple and natural mechanism, in which each agent announces only whether he or she demands a resource and the resource is divided equally among the agents who demand it. We show that any Nash equilibrium allocation of our mechanism belongs to the equal-division core. In addition, we show that our mechanism is Cournot stable. In other words, from any message profile, any path of better-replies converges to a Nash equilibrium.
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
See, for example, Roemer (1989) and Moulin (2003).
 
2
Contrary to the allocation problem with single-dipped preferences, there are several strategy-proof, Pareto efficient, and fair rules in the location problem of a public facility with single-dipped preferences. See, for example, Barberà et al. (2012) and Manjunath (2014).
 
3
Doghmi (2013b, 2016) and Doghmi and Ziad (2013) investigated Nash implementation in the allocation problem in more general preference domains.
 
4
Abreu and Matsushima (1992) and Jackson (1992) pointed out some drawbacks of Maskin’s (1999) canonical mechanism .
 
5
However, the solution implemented by the binary mechanism does not satisfy strong Pareto efficiency or envy-freeness. It is impossible to design a mechanism that Nash implements a solution, satisfying strong Pareto efficiency and envy-freeness (Remarks 1 and 2).
 
6
For surveys on several criteria for fair allocation, see Young (1995), Roemer (1996), Moulin (2003) and Thomson (2011).
 
7
Agent i’s message \(m_{i}\) is dominated by \(m_{i}^{\prime }\) at \(R_{i}\) if for each \(m_{-i}\in M_{-i},\) \(g(m_{i}^{\prime },m_{-i})\,R_{i}\,g(m_{i},m_{-i}),\) and for some \(m_{-i}^{\prime }\in M_{-i},\) \(g(m_{i}^{\prime },m_{-i}^{\prime })\,P_{i}\,g(m_{i},m_{-i}^{\prime }).\) Agent i’s message \(m_{i}\) is dominated at \(R_{i}\) if there is \(m_{i}^{\prime }\in M_{i}\) which dominates \(m_{i}\) at \(R_{i}.\) A mechanism \(\Gamma \) is bounded if for each \(R\in {\mathcal {R}}^{N},\) each \(i\in N,\) and each \(m_{i}\in M_{i},\) if \(\ m_{i}\) is dominated at \(R_{i}\), then there is \(m_{i}^{\prime }\in M_{i},\) such that \(m_{i}^{\prime }\) dominates \(m_{i}\) and there is no \( m_{i}^{^{\prime \prime }}\in M_{i}\) which dominates \(m_{i}^{\prime }\) at \( R_{i}.\)
 
8
Since for each \(k,k' \in \{0,1,\ldots,n,n+1\}\), such that \(k>k',\,N_k(R) \subseteq N_{k'}(R)\), we have
$$n=\left|N_{0}(R)\right| \ge \left|N_{1}(R)\right| \ge \ldots \ge \left|N_{n+1}(R)\right|=0.$$
Since \(\left|N_{0}(R)\right|=n>0\) and \(\left|N_{n+1}(R)\right|=0<n+1,\) there is \(k^{*}\in \{0,1,\ldots,n\}\) such that for each \(k\in \{0,1,\ldots,k^{*}\}, \left|N_{k}(R)\right|\ge k,\) and for each \(k\in \{k^{*}+1,\ldots,n+1\}, \left|N_{k}(R)\right|< k.\).
 
9
However, the equal-division core property does not imply anonymity. For example, let \(F(R)=\left\{ x\in EC(R)\text { }|\text { }x_{1}\ge x_{1}^{\prime }\text {, }\forall x^{\prime }\in EC(R)\,\right\} .\) Then, while this F satisfies the equal-division core property, it does not satisfy anonymity.
 
10
Doghmi (2013a) showed that the weak Pareto solution WP, the equal-division lower bound solution ELB, and \(WP\cap ELB\) satisfies Maskin monotonicity, so that they can be implemented by Maskin’s canonical mechanism. While \( F_{B}\) is a subcorrespondence of \(WP\cap ELD,\) the binary mechanism does not fully implement \(WP\cap ELD\) in Nash equilibria (Remark 6).
 
11
A path \(\left( s^{t}\right) _{t\in {\mathbb {N}} }\) is a best-reply path of G if for each pair \(t,t+1\in {\mathbb {N}} ,\) \(s_{t+1}\ne s_{t}\) if and only if there is \(i\in N\) such that \( s^{t+1}=(s_{i}^{t+1},s_{-i}^{t})\), \(f(s_{i}^{t+1},s_{-i}^{t})\,P_{i} \,f(s_{i}^{t},s_{-i}^{t}),\) and for each \(s_{i}\in S_{i}\), \( f(s_{i}^{t+1},s_{-i}^{t})\,R_{i}\,f(s_{i},s_{-i}^{t})\). Voorneveld (2000) and Jensen (2009) showed that in a finite best-reply potential game, any best-reply path is finite. Since any best-reply path is a better-reply path, stability in better-reply dynamics implies stability in best-reply dynamics.
 
12
Since \(0<\frac{1}{\left| S\right| ^{2}}<\frac{1}{(\left| S\right| +1)(\left| S\right| -1)},\) we have \(0<\frac{\left| S\right| -1}{\left| S\right| }\times \frac{1}{\left| S\right| }<\frac{1}{\left| S\right| +1}.\)
 
Literatur
Zurück zum Zitat Abreu D, Matsushima H (1992) Virtual implementation in iteratively undominated strategies: complete information. Econometrica 60:993–1008 CrossRef Abreu D, Matsushima H (1992) Virtual implementation in iteratively undominated strategies: complete information. Econometrica 60:993–1008 CrossRef
Zurück zum Zitat Barberà S, Berga D, Moreno B (2012) Domains ranges and strategy-proofness the case of single-dipped preferences. Soc Choice Welf 39:335–352 CrossRef Barberà S, Berga D, Moreno B (2012) Domains ranges and strategy-proofness the case of single-dipped preferences. Soc Choice Welf 39:335–352 CrossRef
Zurück zum Zitat Chen Y, Gazzale R (2004) When does learning in games generate convergence to Nash equilibria? The role of supermodularity in an experimental setting. Am Econ Rev 94:1505–1535 CrossRef Chen Y, Gazzale R (2004) When does learning in games generate convergence to Nash equilibria? The role of supermodularity in an experimental setting. Am Econ Rev 94:1505–1535 CrossRef
Zurück zum Zitat Doghmi A (2013a) Nash implementation in an allocation problem with single-dipped preferences. Games 4:38–49 CrossRef Doghmi A (2013a) Nash implementation in an allocation problem with single-dipped preferences. Games 4:38–49 CrossRef
Zurück zum Zitat Doghmi A (2013b) Nash implementation in private good economies when preferences are single-dipped with best indifferent allocations. Math Econ Lett 1:35–42 CrossRef Doghmi A (2013b) Nash implementation in private good economies when preferences are single-dipped with best indifferent allocations. Math Econ Lett 1:35–42 CrossRef
Zurück zum Zitat Doghmi A (2016) On Nash implementability in allotment economies under domain restrictions with indifference. BE J Theoret Econ 16:767–795 Doghmi A (2016) On Nash implementability in allotment economies under domain restrictions with indifference. BE J Theoret Econ 16:767–795
Zurück zum Zitat Doghmi A, Ziad A (2013) On partially honest Nash implementation in private good economies with restricted domains: a sufficient condition. BE J Theoret Econ 13:415–428 CrossRef Doghmi A, Ziad A (2013) On partially honest Nash implementation in private good economies with restricted domains: a sufficient condition. BE J Theoret Econ 13:415–428 CrossRef
Zurück zum Zitat Ehlers L (2002) Probabilistic allocation rules and single-dipped preferences. Soc Choice Welf 19:325–348 CrossRef Ehlers L (2002) Probabilistic allocation rules and single-dipped preferences. Soc Choice Welf 19:325–348 CrossRef
Zurück zum Zitat Healy PJ (2006) Learning dynamics for mechanism design: an experimental comparison of public goods mechanisms. J Econ Theory 129:114–149 CrossRef Healy PJ (2006) Learning dynamics for mechanism design: an experimental comparison of public goods mechanisms. J Econ Theory 129:114–149 CrossRef
Zurück zum Zitat Jackson M (1992) Implementation in undominated strategies: a look at bounded mechanisms. Rev Econ Stud 59:757–775 CrossRef Jackson M (1992) Implementation in undominated strategies: a look at bounded mechanisms. Rev Econ Stud 59:757–775 CrossRef
Zurück zum Zitat Jensen MK (2009) Stability of pure strategy Nash equilibrium and best-response potential games. Mimeo Jensen MK (2009) Stability of pure strategy Nash equilibrium and best-response potential games. Mimeo
Zurück zum Zitat Klaus B (2001) Coalitional strategy-proofness in economies with single-dipped preferences and the assignment of an indivisible object. Games Econ Behav 34:64–82 CrossRef Klaus B (2001) Coalitional strategy-proofness in economies with single-dipped preferences and the assignment of an indivisible object. Games Econ Behav 34:64–82 CrossRef
Zurück zum Zitat Klaus B, Peters H, Storcken T (1997) Strategy-proof division of a private good when preferences are single-dipped. Econ Lett 55:339–346 CrossRef Klaus B, Peters H, Storcken T (1997) Strategy-proof division of a private good when preferences are single-dipped. Econ Lett 55:339–346 CrossRef
Zurück zum Zitat Manjunath V (2014) Efficient and strategy-proof social choice when preferences single-dipped. Internat J Game Theory 43:579–597 CrossRef Manjunath V (2014) Efficient and strategy-proof social choice when preferences single-dipped. Internat J Game Theory 43:579–597 CrossRef
Zurück zum Zitat Maskin E (1999) Nash equilibrium and welfare optimality. Rev Econ Stud 66:23–38 CrossRef Maskin E (1999) Nash equilibrium and welfare optimality. Rev Econ Stud 66:23–38 CrossRef
Zurück zum Zitat Monderer D, Shapley LS (1996) Potential games. Games Econ Behav 14:124–143 CrossRef Monderer D, Shapley LS (1996) Potential games. Games Econ Behav 14:124–143 CrossRef
Zurück zum Zitat Moulin H (2003) Fair division and collective welfare. The MIT Press, Cambridge CrossRef Moulin H (2003) Fair division and collective welfare. The MIT Press, Cambridge CrossRef
Zurück zum Zitat Roemer JE (1989) Public ownership resolution of the tragedy of the commons. Soc Philos Policy 6:74–92 CrossRef Roemer JE (1989) Public ownership resolution of the tragedy of the commons. Soc Philos Policy 6:74–92 CrossRef
Zurück zum Zitat Roemer JE (1996) Theories of distributive justice. Harvard University Press, Cambridge Roemer JE (1996) Theories of distributive justice. Harvard University Press, Cambridge
Zurück zum Zitat Saijo T, Tatamitani Y, Yamato T (1996) Toward natural implementation. Int Econ Rev 37:949–980 CrossRef Saijo T, Tatamitani Y, Yamato T (1996) Toward natural implementation. Int Econ Rev 37:949–980 CrossRef
Zurück zum Zitat Saijo T, Tatamitani Y, Yamato T (1999) Characterizing natural implementability: the fair and Walrasian correspondences. Games Econ Behav 28:271–293 CrossRef Saijo T, Tatamitani Y, Yamato T (1999) Characterizing natural implementability: the fair and Walrasian correspondences. Games Econ Behav 28:271–293 CrossRef
Zurück zum Zitat Sandholm W (2002) Evolutionary implementation and congestion pricing. Rev Econ Stud 69:667–689 CrossRef Sandholm W (2002) Evolutionary implementation and congestion pricing. Rev Econ Stud 69:667–689 CrossRef
Zurück zum Zitat Sandholm W (2005) Negative externalities and evolutionary implementation. Rev Econ Stud 72:885–915 CrossRef Sandholm W (2005) Negative externalities and evolutionary implementation. Rev Econ Stud 72:885–915 CrossRef
Zurück zum Zitat Sandholm W (2007) Pigouvian pricing and stochastic evolutionary implementation. J Econ Theory 132:367–382 CrossRef Sandholm W (2007) Pigouvian pricing and stochastic evolutionary implementation. J Econ Theory 132:367–382 CrossRef
Zurück zum Zitat Thomson W (1993) The replacement principle in public good economies with single-peaked preferences. Econ Lett 42:31–36 CrossRef Thomson W (1993) The replacement principle in public good economies with single-peaked preferences. Econ Lett 42:31–36 CrossRef
Zurück zum Zitat Thomson W (1994) Consistent solutions to the problem of fair division when preferences are single-peaked. J Econ Theory 63:219–245 CrossRef Thomson W (1994) Consistent solutions to the problem of fair division when preferences are single-peaked. J Econ Theory 63:219–245 CrossRef
Zurück zum Zitat Thomson W (2011) Fair allocation rules. In: Arrow KJ, Sen AK, Suzumura K (eds) Handbook of social choice and welfare, vol 2. Elsevier, Amsterdam, pp 393–506 CrossRef Thomson W (2011) Fair allocation rules. In: Arrow KJ, Sen AK, Suzumura K (eds) Handbook of social choice and welfare, vol 2. Elsevier, Amsterdam, pp 393–506 CrossRef
Zurück zum Zitat Voorneveld M (2000) Best-response potential games. Econ Lett 66:289–295 CrossRef Voorneveld M (2000) Best-response potential games. Econ Lett 66:289–295 CrossRef
Zurück zum Zitat Yamamura H (2016) Coalitional stability in the location problem with single-dipped preferences: An application of the minimax theorem. J Math Econ 65:48–57 CrossRef Yamamura H (2016) Coalitional stability in the location problem with single-dipped preferences: An application of the minimax theorem. J Math Econ 65:48–57 CrossRef
Zurück zum Zitat Yamamura H, Kawasaki R (2013) Generalized average rule as stable Nash mechanisms to implement generalized median rules. Soc Choice Welf 40:815–832 CrossRef Yamamura H, Kawasaki R (2013) Generalized average rule as stable Nash mechanisms to implement generalized median rules. Soc Choice Welf 40:815–832 CrossRef
Zurück zum Zitat Young P (1995) Equity: in theory and practice. Princeton University Press, Princeton CrossRef Young P (1995) Equity: in theory and practice. Princeton University Press, Princeton CrossRef
Metadaten
Titel
Binary mechanism for the allocation problem with single-dipped preferences
verfasst von
Fumiya Inoue
Hirofumi Yamamura
Publikationsdatum
11.10.2022
Verlag
Springer Berlin Heidelberg
Erschienen in
Social Choice and Welfare
Print ISSN: 0176-1714
Elektronische ISSN: 1432-217X
DOI
https://doi.org/10.1007/s00355-022-01427-1

Premium Partner