Top

Social Choice and Welfare

Published in:

11-10-2022 | Original Paper

Binary mechanism for the allocation problem with single-dipped preferences

Authors: Fumiya Inoue, Hirofumi Yamamura

Published in: Social Choice and Welfare | Issue 4/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Does allowing private communication lead to less prosocial collective choice?

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

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–1008CrossRef

Barberà S, Berga D, Moreno B (2012) Domains ranges and strategy-proofness the case of single-dipped preferences. Soc Choice Welf 39:335–352CrossRef

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–1535CrossRef

Doghmi A (2013a) Nash implementation in an allocation problem with single-dipped preferences. Games 4:38–49CrossRef

Doghmi A (2013b) Nash implementation in private good economies when preferences are single-dipped with best indifferent allocations. Math Econ Lett 1:35–42CrossRef

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–428CrossRef

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

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

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

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–82CrossRef

Klaus B, Peters H, Storcken T (1997) Strategy-proof division of a private good when preferences are single-dipped. Econ Lett 55:339–346CrossRef

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

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

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

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

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

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–980CrossRef

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

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

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

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

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

Thomson W (1994) Consistent solutions to the problem of fair division when preferences are single-peaked. J Econ Theory 63:219–245CrossRef

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–506CrossRef

Thomson W (2016) Non-bossiness. Soc Choice Welf 47:665–696CrossRef

Voorneveld M (2000) Best-response potential games. Econ Lett 66:289–295CrossRef

Yamamura H (2016) Coalitional stability in the location problem with single-dipped preferences: An application of the minimax theorem. J Math Econ 65:48–57CrossRef

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

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

Title: Binary mechanism for the allocation problem with single-dipped preferences
Authors: Fumiya Inoue
Hirofumi Yamamura
Publication date: 11-10-2022
Publisher: Springer Berlin Heidelberg
Published in: Social Choice and Welfare / Issue 4/2023
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-022-01427-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2023

Does allowing private communication lead to less prosocial collective choice?

On Sugden’s normative economics and the comparison of non-nested opportunity sets

Single-peaked domains with designer uncertainty

The blocker postulates for measures of voting power

Core stability of the Shapley value for cooperative games

Universalization and altruism