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

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