Skip to main content
Top
Published in: Social Choice and Welfare 1/2024

30-08-2023 | Original Paper

Worst-case efficient and budget-balanced mechanism for single-object allocation with interdependent values

Author: Aditya Vikram

Published in: Social Choice and Welfare | Issue 1/2024

Log in

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

search-config
loading …

Abstract

We study a model in which a single object is to be allocated among a set of agents whose valuations are interdependent. We define signal-ranking mechanisms and show that if the signal-ranking allocation rule satisfies a combinatorial condition and the valuation functions are additively separable, there exist budget-balanced and ex-post incentive compatible signal-ranking mechanisms. For a restricted setting, we show that the worst-case efficient mechanism of Long et al. (Games Econ Behav 105:9–39, 2017) continues to be worst-case efficient. We also give an example to show that their mechanism is no longer optimal when restrictions are relaxed.

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!

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!

Appendix
Available only for authorised users
Footnotes
1
In some special cases like the sequencing problem it might be possible to reconcile the three properties e.g. Hain and Mitra (2004). Also, Kosenok and Severinov (2008) show that there exists an ex-post efficient mechanism that is interim incentive-compatible, interim individually-rational and ex-post budget balanced when the joint distribution of the values is known and which satisfies Cremer and McLean (1988) conditions and the identifiability condition.
 
2
Long et al. (2017) show that this combinatorial condition is a necessary and sufficient condition for a ranking mechanism to be budget-balanced and strategy-proof in private-value setting. For the exact condition, see Theorem 2 in Sect. 4.
 
3
We suppress the dependence of L on s for notational convenience.
 
4
The valuation functions \(v_i:[0,1]^n \rightarrow \mathbb {R_+}\), \(i \in N\) satisfy single-crossing if for every \(i, j \in N\), every \(s_{-i} \in S_{-i}\) and every \(s_i > s'_i\),
$$\begin{aligned} v_i (s_i, s_{-i}) - v_i (s'_i , s_{-i}) > v_j (s_i, s_{-i}) - v_j (s'_i , s_{-i}) \end{aligned}$$
 
5
The valuation functions satisfy the SAS condition. Notice that for any two agents i and j, if \(s_i > s_j\) then \(v_i (s) > v_j(s)\) and vice versa. Also, \(s_i = s_j\) implies \(v_i (s) = v_j (s)\) and vice versa.
 
6
See Krishna (2009) where it is shown that single-crossing condition is sufficient for ex-post incentive compatibility of generalized Vickrey auction.
 
7
The literature of mechanism design in interdependent-value setting emphasizes the importance of single-crossing for efficient mechanisms to be EPIC (see d’Aspremont and Gerard-Varet (1982) and Dasgupta and Maskin (2000) for example).
 
Literature
go back to reference Bergemann D, Morris S (2005) Robust mechanism design. Econometrica 73(6):1771–1813CrossRef Bergemann D, Morris S (2005) Robust mechanism design. Econometrica 73(6):1771–1813CrossRef
go back to reference Cremer J, McLean R (1988) Full extraction of the surplus in bayesian and dominant strategy auctions. Econometrica 56:1247–1258CrossRef Cremer J, McLean R (1988) Full extraction of the surplus in bayesian and dominant strategy auctions. Econometrica 56:1247–1258CrossRef
go back to reference Dasgupta P, Maskin E (2000) Efficient auctions. Quart J Econ 115(2):341–388CrossRef Dasgupta P, Maskin E (2000) Efficient auctions. Quart J Econ 115(2):341–388CrossRef
go back to reference d’Aspremont C, Gerard-Varet L (1982) Bayesian incentive compatible beliefs. J Math Econ 10(1):83–103CrossRef d’Aspremont C, Gerard-Varet L (1982) Bayesian incentive compatible beliefs. J Math Econ 10(1):83–103CrossRef
go back to reference Eden A, Feldman M, Fiat A, Goldner K (2018) Interdependent values without single-crossing. Proceedings of the 2018 ACM Conference on Economics and Computation (EC’18). ACM, New York, NY, USA, pp 369–369 Eden A, Feldman M, Fiat A, Goldner K (2018) Interdependent values without single-crossing. Proceedings of the 2018 ACM Conference on Economics and Computation (EC’18). ACM, New York, NY, USA, pp 369–369
go back to reference Green J, Laffont J (1979) Incentives in public decision-making. Elsevier, Amsterdam Green J, Laffont J (1979) Incentives in public decision-making. Elsevier, Amsterdam
go back to reference Hain D, Mitra M (2004) Simple sequencing problems with interdependent costs. Games Econom Behav 48:271–291CrossRef Hain D, Mitra M (2004) Simple sequencing problems with interdependent costs. Games Econom Behav 48:271–291CrossRef
go back to reference Jehiel P, Moldovanu B (2001) Efficient design with interdependent valuations. Econometrica 69(5):1237–1259CrossRef Jehiel P, Moldovanu B (2001) Efficient design with interdependent valuations. Econometrica 69(5):1237–1259CrossRef
go back to reference Kosenok G, Severinov S (2008) Individually rational, budget-balanced mechanisms and allocation of surplus. J Econ Theory 140:126–161CrossRef Kosenok G, Severinov S (2008) Individually rational, budget-balanced mechanisms and allocation of surplus. J Econ Theory 140:126–161CrossRef
go back to reference Krishna V (2009) Auction theory. Academic Press, Cambridge Krishna V (2009) Auction theory. Academic Press, Cambridge
go back to reference Long Y (2019) Optimal budget-balanced ranking mechanisms to assign identical objects. Econ Theor 70:467–502CrossRef Long Y (2019) Optimal budget-balanced ranking mechanisms to assign identical objects. Econ Theor 70:467–502CrossRef
go back to reference Long Y, Mishra D, Sharma T (2017) Balanced ranking mechanisms. Games Econom Behav 105:9–39CrossRef Long Y, Mishra D, Sharma T (2017) Balanced ranking mechanisms. Games Econom Behav 105:9–39CrossRef
go back to reference Milgrom P, Weber R (1982) A theory of auctions and competitive bidding. Econometrica 50(5):1089–1122CrossRef Milgrom P, Weber R (1982) A theory of auctions and competitive bidding. Econometrica 50(5):1089–1122CrossRef
go back to reference Mishra D, Sharma T (2018) A simple budget balanced mechanism. Soc Choice Welfare 169:218–233 Mishra D, Sharma T (2018) A simple budget balanced mechanism. Soc Choice Welfare 169:218–233
go back to reference Nath S, Zoeter O, Narahari Y, Dance C (2015) Dynamic mechanism design with interdependent valuations. Rev Econ Design 19(3):211–228CrossRef Nath S, Zoeter O, Narahari Y, Dance C (2015) Dynamic mechanism design with interdependent valuations. Rev Econ Design 19(3):211–228CrossRef
go back to reference Perry M, Reny P (1999) An ex-post efficient auction. Working paper, Hebrew University and University of Chicago Perry M, Reny P (1999) An ex-post efficient auction. Working paper, Hebrew University and University of Chicago
go back to reference Roughgarden T, Talgam-Cohen I (2016) Optimal and robust mechanism design with interdependent values. ACM Trans Econ Comput 4(3):18:1-18:34CrossRef Roughgarden T, Talgam-Cohen I (2016) Optimal and robust mechanism design with interdependent values. ACM Trans Econ Comput 4(3):18:1-18:34CrossRef
go back to reference Yenmez M (2015) Incentive compatible market design with applications. Internat J Game Theory 44:543–569CrossRef Yenmez M (2015) Incentive compatible market design with applications. Internat J Game Theory 44:543–569CrossRef
Metadata
Title
Worst-case efficient and budget-balanced mechanism for single-object allocation with interdependent values
Author
Aditya Vikram
Publication date
30-08-2023
Publisher
Springer Berlin Heidelberg
Published in
Social Choice and Welfare / Issue 1/2024
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI
https://doi.org/10.1007/s00355-023-01479-x

Other articles of this Issue 1/2024

Social Choice and Welfare 1/2024 Go to the issue

Original Paper

Ties

Premium Partner