nach oben

Social Choice and Welfare

Erschienen in:

08.10.2015 | Original Paper

Convex strategyproofness with an application to the probabilistic serial mechanism

verfasst von: Ivan Balbuzanov

Erschienen in: Social Choice and Welfare | Ausgabe 3/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider two natural notions of strategyproofness in random object-assignment mechanisms based on ordinal preferences. The two notions are stronger than weak strategyproofness but weaker than strategyproofness. We demonstrate that the two notions are equivalent, provide a geometric characterization of the new intermediate property which we call convex strategyproofness, and then show that the (generalized) probabilistic serial mechanism is, in fact, convexly strategyproof. We finish by showing that the property of weak envy-freeness of the random serial dictatorship can be strengthened in an analogous manner.

Vorheriger Artikel On avoiding vote swapping

Nächster Artikel Empirical welfare analysis: when preferences matter

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

First-order stochastic dominance here is defined with respect to the agent’s true preferences.

See also Lubin and Parkes (2012) for a survey of other ways of relaxing strategyproofness.

We restrict our attention to strict preference orders. The main reason for that is that the version of the (generalized) PS mechanism which allows for indifferences (Katta and Sethuraman 2006; Budish et al. 2013) fails to even be weakly strategyproof. However, the strictness assumption is not crucial. A result essentially identical to our Proposition 1 can be derived for non-strict preference orders, as well.

We allow there to be more than one copy of each object.

That is to say, whenever \(x\succsim y\) for some \(x,y\in \mathbb {R}^n\) then \(\alpha x+z\succsim \alpha y+z\) for all \(z\in \mathbb {R}^n\) and \(\alpha \ge 0\).

The reason we use the Polyhedral Separating Hyperplane Theorem, as opposed to a weaker separating result, is that it gives us the strict inequality in this sentence. In the next paragraph, it becomes apparent that the strict inequality is crucial in showing that \(\overline{u}\) is compatible with the preference order.

Budish et al. (2013) generalize the mechanism by adding group-specific quotas and show that it remains weakly strategyproof. The results in this paper hold for their Generalized Probabilistic Serial mechanism as well.

Budish et al. (2013) use a similar arguments so the following Lemma would hold in their setting as well.

Note that Example 1 can be used to show that convex envy-freeness is strictly stronger than weak envy-freeness. Namely, let \(g(a),g(b^1),\) and \(g(b^2)\) instead refer to the probability-share distributions of three agents dividing three objects among themselves (note that the probability shares for each object sum up to 1), and let their preferences be identical: they all prefer objects with smaller indices over objects with larger indices. Then that allocation would satisfy weak envy-freeness. However, it would not satisfy convex envy-freeness since the agent corresponding to g(a) would envy a convex combination of the other two agents’ allocations as shown in the example.

Abdulkadiroğlu A, Sönmez T (1998) Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66(3):689–701CrossRef

Aliprantis C, Border K (2006) Infinite dimensional analysis: a Hitchhiker’s guide. Springer, Berlin Heidelberg

Bogomolnaia A, Moulin H (2001) A new solution to the random assignment problem. J Econ Theory 100(2):295–328CrossRef

Budish E, Che YK, Kojima F, Milgrom P (2013) Designing random allocation mechanisms: theory and application. Am Econ Rev 103(2):585–623CrossRef

Hadar J, Russell W (1969) Rules for ordering uncertain prospects. Am Econ Rev 59(1):25–34

Katta AK, Sethuraman J (2006) A solution to the random assignment problem on the full preference domain. J Econ Theory 131(1):231–250CrossRef

Kojima F, Manea M (2010) Incentives in the probabilistic serial mechanism. J Econ Theory 145(1):106–123CrossRef

Lubin B, Parkes D (2012) Approximate strategyproofness. Curr Sci India 103(9):1021–1032

McLennan A (2002) Ordinal efficiency and the polyhedral separating hyperplane theorem. J Econ Theory 105(2):435–449CrossRef

Mennle T, Seuken S (2013) Partially strategyproof mechanisms for the assignment problem Mimeo. University of Zurich, Zurich

Titel: Convex strategyproofness with an application to the probabilistic serial mechanism
verfasst von: Ivan Balbuzanov
Publikationsdatum: 08.10.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Social Choice and Welfare / Ausgabe 3/2016
Print ISSN: 0176-1714
Elektronische ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-015-0926-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2016

The difference between manipulability indices in the IC and IANC models

A characterization of the n-agent Pareto dominance relation

Empirical welfare analysis: when preferences matter

Representative democracy and the implementation of majority-preferred alternatives

Consistent updating of social welfare functions

Fair social orderings with other-regarding preferences