nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources

verfasst von : George Christodoulou, Alkmini Sgouritsa, Bo Tang

Erschienen in: Algorithmic Game Theory

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We study the efficiency of the proportional allocation mechanism, that is widely used to allocate divisible resources. Each agent submits a bid for each divisible resource and receives a fraction proportional to her bids. We quantify the inefficiency of Nash equilibria by studying the Price of Anarchy (PoA) of the induced game under complete and incomplete information. When agents’ valuations are concave, we show that the Bayesian Nash equilibria can be arbitrarily inefficient, in contrast to the well-known 4 / 3 bound for pure equilibria [12]. Next, we upper bound the PoA over Bayesian equilibria by 2 when agents’ valuations are subadditive, generalizing and strengthening previous bounds on lattice submodular valuations. Furthermore, we show that this bound is tight and cannot be improved by any simple mechanism. Then we switch to settings with budget constraints, and we show an improved upper bound on the PoA over coarse-correlated equilibria. Finally, we prove that the PoA is exactly 2 for pure equilibria in the polyhedral environment.

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

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

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

Vorheriges Kapitel Algorithmic Signaling of Features in Auction Design

Nächstes Kapitel On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games

The expectation over \(\mathbf {v}\) is only needed for the definition of Bayesian PoA.

A bidding profile \(\mathbf {B}=\times _i B_i\) is called \(\epsilon \)-mixed Nash equilibrium if, for every agent i and all bids \(b'_i\), \(\mathbb {E}_{\mathbf {b}\sim \mathbf {B}}[u_i(\mathbf {b})]\ge \mathbb {E}_{\mathbf {b}\sim \mathbf {B}}[u_i(b'_i,\mathbf {b}_{-i})] - \epsilon \).

Bhawalkar, K., Roughgarden, T.: Welfare guarantees for combinatorial auctions with item bidding. In: SODA 2011. SIAM (2011)

Caragiannis, I., Voudouris, A.A.: Welfare guarantees for proportional allocations. In: Lavi, R. (ed.) SAGT 2014. LNCS, vol. 8768, pp. 206–217. Springer, Heidelberg (2014)

Christodoulou, G., Kovács, A., Schapira, M.: Bayesian combinatorial auctions. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 820–832. Springer, Heidelberg (2008) CrossRef

Christodoulou, G., Kovács, A., Sgouritsa, A., Tang, B.: Tight bounds for the price of anarchy of simultaneous first price auctions. CoRR abs/1312.2371 (2013)

Chun, B.N., Culler, D.E.: Market-based proportional resource sharing for clusters. Technical report, University of California at Berkeley, Berkeley (2000)

Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: The price of anarchy of the proportional allocation mechanism revisited. In: Chen, Y., Immorlica, N. (eds.) WINE 2013. LNCS, vol. 8289, pp. 109–120. Springer, Heidelberg (2013) CrossRef

Dobzinski, S., Nisan, N., Schapira, M.: Approximation algorithms for combinatorial auctions with complement-free bidders. Math. Oper. Res. 35(1), 1–13 (2010)MathSciNetCrossRefMATH

Evans, D.S., Heckman, J.J.: A test for subadditivity of the cost function with an application to the bell system. The American Economic Review pp. 615–623 (1984)

Feldman, M., Fu, H., Gravin, N., Lucier, B.: Simultaneous auctions are (almost) efficient. In: STOC 2013 (2012)

10.

Feldman, M., Lai, K., Zhang, L.: A price-anticipating resource allocation mechanism for distributed shared clusters. In: EC 2005, pp. 127–136. ACM (2005)

11.

Hassidim, A., Kaplan, H., Mansour, Y., Nisan, N.: Non-price equilibria in markets of discrete goods. In: EC 2011, pp. 295–296. ACM (2011)

12.

Johari, R., Tsitsiklis, J.N.: Efficiency loss in a network resource allocation game. Math. Oper. Res. 29(3), 407–435 (2004)MathSciNetCrossRefMATH

13.

Johari, R., Tsitsiklis, J.N.: Efficiency of scalar-parameterized mechanisms. Oper. Res. 57(4), 823–839 (2009)MathSciNetCrossRefMATH

14.

Kelly, F.: Charging and rate control for elastic traffic. Eur. Trans. Telecomm. 8(1), 33–37 (1997)CrossRef

15.

Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999) CrossRef

16.

Nguyen, T., Tardos, E.: Approximately maximizing efficiency and revenue in polyhedral environments. In: EC 2007. ACM (2007)

17.

Nisan, N.: The communication complexity of approximate set packing and covering. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 868–875. Springer, Heidelberg (2002) CrossRef

18.

Rosenbaum, R.A.: Sub-additive functions. Duke Math. J. 17(3), 227–247 (1950)MathSciNetCrossRefMATH

19.

Roughgarden, T.: Barriers to near-optimal equilibria. In: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2014)

20.

Syrgkanis, V., Tardos, E.: Composable and Efficient Mechanisms. In: STOC 2013 (2013)

21.

Zhang, L.: The efficiency and fairness of a fixed budget resource allocation game. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 485–496. Springer, Heidelberg (2005) CrossRef

Titel: On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources
verfasst von: George Christodoulou
Alkmini Sgouritsa
Bo Tang
Verlag: Springer Berlin Heidelberg
Buch: Algorithmic Game Theory
Print ISBN: 978-3-662-48432-6

Electronic ISBN: 978-3-662-48433-3

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-662-48433-3_13

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

Springer Professional "Wirtschaft"

Premium Partner