nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

On Revenue-Maximizing Mechanisms Assuming Convex Costs

verfasst von : Amy Greenwald, Takehiro Oyakawa, Vasilis Syrgkanis

Erschienen in: Algorithmic Game Theory

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We investigate revenue-maximizing mechanisms in settings where bidders’ utility functions are characterized by convex costs. Such costs arise, for instance, in procurement auctions for energy, and when bidders borrow money at non-linear interest rates. We provide a 1 / 16e approximation guarantee for a prior-free randomized mechanism when bidders’ values are drawn from MHR distributions, and their costs are polynomial. Additionally, we propose two heuristics that allocate proportionally, using either bidders’ values or virtual values. Perhaps surprisingly, in the convex cost setting, it is preferable to allocate to multiple relatively high bidders, rather than only to bidders with the highest (virtual) value, as is optimal in the traditional quasi-linear utility setting.

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 A Truthful Mechanism for Interval Scheduling

Nächstes Kapitel On the Price of Stability of Social Distance Games

A notable exception is [8], who study prior-free auctions for risk-averse agents, which are modelled by a very specific form of capped quasi-linear utilities.

Multiplying \(\mathfrak {u_{}}_{i}\) by \(v_{i}\) yields a familiar utility function, that of the forward setting, with utility measured in units of power, rather than money: \(v_{i} \mathfrak {u_{}}_{i} = u_{i} = v_{i} x_{i} - c_{i}(p_{i})\).

For example, it is more expensive to convert bitumen into synthetic crude oil than it is to drill and pump conventional crude oil.

In the convex cost setting, if we interpret \(v_{}(q_{})\) as a posted cost, rather than a posted price (i.e., payment) then \(R(q_{})\) can be wrongly interpreted as an expected cost function.

Alaei, S., Fu, H., Haghpanah, N., Hartline, J.: The simple economics of approximately optimal auctions. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 628–637. IEEE (2013)

Border, K.C.: Implementation of reduced form auctions: a geometric approach. Econometrica 59(4), 1175–1187 (1991). http://www.jstor.org/stable/2938181MathSciNetCrossRef

Bulow, J., Klemperer, P.: Auctions versus negotiations. Am. Econ. Rev. 86(1), 180–194 (1996)

Cai, Y., Daskalakis, C., Weinberg, S.M.: Understanding incentives: mechanism design becomes algorithm design. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 618–627, October (2013). https://doi.org/10.1109/FOCS.2013.72

Chawla, S., Hartline, J.D., Sivan, B.: Optimal crowdsourcing contests. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 856–868. SIAM (2012)

Dhangwatnotai, P., Roughgarden, T., Yan, Q.: Revenue maximization with a single sample. Games Econ. Behav. 91, 318–333 (2015)MathSciNetCrossRef

DiPalantino, D., Vojnovic, M.: Crowdsourcing and all-pay auctions. In: Proceedings of the 10th ACM Conference on Electronic Commerce, pp. 119–128. ACM (2009)

Fu, H., Hartline, J., Hoy, D.: Prior-independent auctions for risk-averse agents. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pp. 471–488. EC ’13, ACM, New York, NY, USA (2013). http://doi.acm.org/10.1145/2482540.2482551

Gossen, H.H.: Entwickelung der gesetze des menschlichen verkehrs, und der daraus fliessenden regeln für menschliche handeln. F. Vieweg (1854)

10.

Greenwald, A., Oyakawa, T., Syrgkanis, V.: Simple vs optimal contests with convex costs. In: Champin, P., Gandon, F.L., Lalmas, M., Ipeirotis, P.G. (eds.) Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, 23–27 April 2018, pp. 1429–1438. ACM (2018). http://doi.acm.org/10.1145/3178876.3186048

11.

Hartline, J.D.: Mechanism design and approximation. Book draft. October (2015)

12.

Hartline, J.D., Roughgarden, T.: Simple versus optimal mechanisms. In: Proceedings of the 10th ACM Conference on Electronic Commerce, pp. 225–234. EC ’09, ACM, New York, NY, USA (2009). http://doi.acm.org/10.1145/1566374.1566407

13.

Maskin, E., Riley, J.: Optimal auctions with risk averse buyers. Econometrica 52(6), 1473–1518 (1984). http://www.jstor.org/stable/1913516MathSciNetCrossRef

14.

Myerson, R.B.: Optimal auction design. Math. Oper. Res. 6(1), 58–73 (1981)MathSciNetCrossRef

15.

Pai, M.M., Vohra, R.: Optimal auctions with financially constrained buyers. J. Econ. Theory 150, 383–425 (2014). https://doi.org/10.1016/j.jet.2013.09.015. http://www.sciencedirect.com/science/article/pii/S0022053113001701MathSciNetCrossRefMATH

16.

Roughgarden, T., Talgam-cohen, I., Yan, Q.: Robust auctions for revenue via enhanced competition (2016)

17.

Sakurai, Y., Saito, Y., Iwasaki, A., Yokoo, M.: Beyond quasi-linear utility: strategy/false-name-proof multi-unit auction protocols. In: IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, 2008. WI-IAT’08, vol. 2, pp. 417–423. IEEE (2008)

18.

Samuel-Cahn, E.: Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4), 1213–1216 (1984)MathSciNetCrossRef

19.

Singer, Y.: Budget feasible mechanism design. SIGecom Exch. 12(2), 24–31 (2014). http://doi.acm.org/10.1145/2692359.2692366CrossRef

20.

Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. J. Financ. 16(1), 8–37 (1961)MathSciNetCrossRef

21.

Wilson, R.: Incentive efficiency of double auctions. Econometrica J. Econ. Soc. 53, 1101–1115 (1985)MathSciNetCrossRef

22.

Wilson, R.: Game-theoretic approaches to trading processes. In: Advances in Economic Theory: Fifth World Congress, pp. 33–77 (1987)

Titel: On Revenue-Maximizing Mechanisms Assuming Convex Costs
verfasst von: Amy Greenwald
Takehiro Oyakawa
Vasilis Syrgkanis
Verlag: Springer International Publishing
Buch: Algorithmic Game Theory
Print ISBN: 978-3-319-99659-2

Electronic ISBN: 978-3-319-99660-8

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-99660-8_11

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"