nach oben

Tipp

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

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.

Nur mit Berechtigung zugänglich

See, for example, Roemer (1989) and Moulin (2003).

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

Doghmi (2013b, 2016) and Doghmi and Ziad (2013) investigated Nash implementation in the allocation problem in more general preference domains.

Abreu and Matsushima (1992) and Jackson (1992) pointed out some drawbacks of Maskin’s (1999) canonical mechanism .

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

For surveys on several criteria for fair allocation, see Young (1995), Roemer (1996), Moulin (2003) and Thomson (2011).

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}.$

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

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.

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

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.

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}.$

Abreu D, Matsushima H (1992) Virtual implementation in iteratively undominated strategies: complete information. Econometrica 60:993–1008 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

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

Doghmi A (2013a) Nash implementation in an allocation problem with single-dipped preferences. Games 4:38–49 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

Doghmi A (2016) On Nash implementability in allotment economies under domain restrictions with indifference. BE J Theoret Econ 16:767–795

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

Ehlers L (2002) Probabilistic allocation rules and single-dipped preferences. Soc Choice Welf 19:325–348 CrossRef

Healy PJ (2006) Learning dynamics for mechanism design: an experimental comparison of public goods mechanisms. J Econ Theory 129:114–149 CrossRef

Jackson M (1992) Implementation in undominated strategies: a look at bounded mechanisms. Rev Econ Stud 59:757–775 CrossRef

Jensen MK (2009) Stability of pure strategy Nash equilibrium and best-response potential games. Mimeo

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, Peters H, Storcken T (1997) Strategy-proof division of a private good when preferences are single-dipped. Econ Lett 55:339–346 CrossRef

Manjunath V (2014) Efficient and strategy-proof social choice when preferences single-dipped. Internat J Game Theory 43:579–597 CrossRef

Maskin E (1999) Nash equilibrium and welfare optimality. Rev Econ Stud 66:23–38 CrossRef

Monderer D, Shapley LS (1996) Potential games. Games Econ Behav 14:124–143 CrossRef

Moulin H (2003) Fair division and collective welfare. The MIT Press, Cambridge CrossRef

Roemer JE (1989) Public ownership resolution of the tragedy of the commons. Soc Philos Policy 6:74–92 CrossRef

Roemer JE (1996) Theories of distributive justice. Harvard University Press, Cambridge

Saijo T, Tatamitani Y, Yamato T (1996) Toward natural implementation. Int Econ Rev 37:949–980 CrossRef

Saijo T, Tatamitani Y, Yamato T (1999) Characterizing natural implementability: the fair and Walrasian correspondences. Games Econ Behav 28:271–293 CrossRef

Sandholm W (2002) Evolutionary implementation and congestion pricing. Rev Econ Stud 69:667–689 CrossRef

Sandholm W (2005) Negative externalities and evolutionary implementation. Rev Econ Stud 72:885–915 CrossRef

Sandholm W (2007) Pigouvian pricing and stochastic evolutionary implementation. J Econ Theory 132:367–382 CrossRef

Thomson W (1993) The replacement principle in public good economies with single-peaked preferences. Econ Lett 42:31–36 CrossRef

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 (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 (2016) Non-bossiness. Soc Choice Welf 47:665–696 CrossRef

Voorneveld M (2000) Best-response potential games. Econ Lett 66:289–295 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

Yamamura H, Kawasaki R (2013) Generalized average rule as stable Nash mechanisms to implement generalized median rules. Soc Choice Welf 40:815–832 CrossRef

Young P (1995) Equity: in theory and practice. Princeton University Press, Princeton CrossRef

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

Springer Professional

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Binary mechanism for the allocation problem with single-dipped preferences

Abstract

Premium Partner

Springer Professional

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Abstract

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Premium Partner