Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Ordinal Approximation for Social Choice, Matching, and Facility Location Problems Given Candidate Positions Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

A Simple Mechanism for a Budget-Constrained Buyer

verfasst von : Yu Cheng, Nick Gravin, Kamesh Munagala, Kangning Wang

Erschienen in: Web and Internet Economics

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We study a classic Bayesian mechanism design setting of monopoly problem for an additive buyer in the presence of budgets. In this setting a monopolist seller with m heterogeneous items faces a single buyer and seeks to maximize her revenue. The buyer has a budget and additive valuations drawn independently for each item from (non-identical) distributions. We show that when the buyer’s budget is publicly known, the better of selling each item separately and selling the grand bundle extracts a constant fraction of the optimal revenue. When the budget is private, we consider a standard Bayesian setting where buyer’s budget b is drawn from a known distribution B. We show that if b is independent of the valuations and distribution B satisfies monotone hazard rate condition, then selling items separately or in a grand bundle is still approximately optimal. We give a complementary example showing that no constant approximation simple mechanism is possible if budget b can be interdependent with valuations.

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 Timing Matters: Online Dynamics in Broadcast Games
Nächstes Kapitel The Communication Complexity of Graphical Games on Grid Graphs
Fußnoten
1
A buyer has additive valuations if his value for a set of items is equal to the sum of his values for the items in the set.
 
2
E.g., the classic VCG mechanism may not be implementable and social efficiency may not be achievable in the budgeted-setting [46].
 
3
In this paper, we mostly focus on the public budget case. So we define notations and discuss backgrounds assuming the buyer has a public budget.
 
4
Like previous work on simple and approximately optimal mechanisms, our results extend to continuous types as well (see, e.g., [16] for a more detailed discussion).
 
5
We use \(x^\top y = \sum _{i=1}^m x_i y_i\) to denote the inner product of two vectors x and y.
 
6
We do not optimize the constants in our proofs. In Sect. 4, we will give an alternative proof of Theorem 1 that shows \({{ \textsc {Rev}}^{b}}(V) \le 5 {{ \textsc {SRev}}^{b}}(V) + 6 {{ \textsc {BRev}}^{b}}(V)\), thus improving this constant from 32 to 11.
 
7
Throughout the paper, when we consider the conditional distribution \({\widehat{V}} := V_{|({||v{||}}_1 \le {c})}\), we will always have \({c}> \min _{v \in {\mathrm {supp}}(V)} {||v{||}}_1\), so that the event we condition on happens with non-zero probability.
 
8
If the distribution is a discrete MHR distribution, similar results still hold. For discrete distributions we have \(\Pr _{b \sim B}[b \ge \lfloor b^* \rfloor ] \ge e^{-1}\) instead of \(\Pr _{b \sim B}[b \ge b^*] \ge e^{-1}\).
 
Literatur
1.
Abrams, Z.: Revenue maximization when bidders have budgets. In: Proceedings of 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 1074–1082 (2006)
2.
Alaei, S., Fu, H., Haghpanah, N., Hartline, J.D., Malekian, A.: Bayesian optimal auctions via multi- to single-agent reduction. In: Proceedings of 13th ACM Conference on Electronic Commerce, p. 17 (2012)
3.
Babaioff, M., Gonczarowski, Y.A., Nisan, N.: The menu-size complexity of revenue approximation. In: Proceedings of 49th ACM Symposium on Theory of Computing, pp. 869–877 (2017)
4.
Babaioff, M., Immorlica, N., Lucier, B., Weinberg, S.M.: A simple and approximately optimal mechanism for an additive buyer. In: Proceedings of 55th IEEE Symposium on Foundations of Computer Science, pp. 21–30 (2014)
5.
Barlow, R.E., Marshall, A.W.: Tables of bounds for distributions with monotone hazard rate. J. Am. Stat. Assoc. 60(311), 872–890 (1965)MathSciNetCrossRef
6.
7.
Bei, X., Chen, N., Gravin, N., Lu, P.: Budget feasible mechanism design: from prior-free to Bayesian. In: Proceedings of 44th ACM Symposium on Theory of Computing, pp. 449–458 (2012)
8.
Bhattacharya, S., Conitzer, V., Munagala, K., Xia, L.: Incentive compatible budget elicitation in multi-unit auctions. In: Proceedings of 21st ACM-SIAM Symposium on Discrete Algorithms, pp. 554–572 (2010)CrossRef
9.
Bhattacharya, S., Goel, G., Gollapudi, S., Munagala, K.: Budget constrained auctions with heterogeneous items. In: Proceedings of 42nd ACM Symposium on Theory of Computing, pp. 379–388 (2010)
10.
Borgs, C., Chayes, J.T., Immorlica, N., Mahdian, M., Saberi, A.: Multi-unit auctions with budget-constrained bidders. In: Proceedings of 6th ACM Conference on Electronic Commerce, pp. 44–51 (2005)
11.
Briest, P., Chawla, S., Kleinberg, R., Weinberg, S.M.: Pricing randomized allocations. In: Proceedings of 21st ACM-SIAM Symposium on Discrete Algorithms, pp. 585–597 (2010)CrossRef
12.
Cai, Y., Daskalakis, C., Weinberg, S.M.: An algorithmic characterization of multi-dimensional mechanisms. In: Proceedings of 44th ACM Symposium on Theory of Computing, pp. 459–478 (2012)
13.
Cai, Y., Daskalakis, C., Weinberg, S.M.: Optimal multi-dimensional mechanism design: reducing revenue to welfare maximization. In: Proceedings of 53rd IEEE Symposium on Foundations of Computer Science, pp. 130–139 (2012)
14.
Cai, Y., Daskalakis, C., Weinberg, S.M.: Reducing revenue to welfare maximization: approximation algorithms and other generalizations. In: Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, pp. 578–595 (2013)CrossRef
15.
Cai, Y., Daskalakis, C., Weinberg, S.M.: Understanding incentives: mechanism design becomes algorithm design. In: Proceedings of 54th IEEE Symposium on Foundations of Computer Science, pp. 618–627 (2013)
16.
Cai, Y., Devanur, N.R., Weinberg, S.M.: A duality based unified approach to Bayesian mechanism design. In: Proceedings of 48th ACM Symposium on Theory of Computing, pp. 926–939 (2016)
17.
18.
Chakrabarty, D., Goel, G.: On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP. SIAM J. Comput. 39(6), 2189–2211 (2010)MathSciNetCrossRef
19.
Chawla, S., Hartline, J.D., Kleinberg, R.D.: Algorithmic pricing via virtual valuations. In: Proceedings of 8th ACM Conference on Electronic Commerce, pp. 243–251 (2007)
20.
Chawla, S., Hartline, J.D., Malec, D.L., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: Proceedings of 42nd ACM Symposium on Theory of Computing, pp. 311–320 (2010)
21.
Chawla, S., Malec, D.L., Malekian, A.: Bayesian mechanism design for budget-constrained agents. In: Proceedings of 12th ACM Conference on Electronic Commerce, pp. 253–262 (2011)
22.
Chawla, S., Malec, D.L., Sivan, B.: The power of randomness in Bayesian optimal mechanism design. Games Econ. Behav. 91, 297–317 (2015)MathSciNetCrossRef
23.
Che, Y., Gale, I.L.: The optimal mechanism for selling to a budget-constrained buyer. J. Econ. Theory 92(2), 198–233 (2000)CrossRef
24.
Chen, N., Gravin, N., Lu, P.: On the approximability of budget feasible mechanisms. In: Proceedings of 22nd ACM-SIAM Symposium on Discrete Algorithms, pp. 685–699 (2011)CrossRef
25.
Cheng, Y., Cheung, H.Y., Dughmi, S., Emamjomeh-Zadeh, E., Han, L., Teng, S.: Mixture selection, mechanism design, and signaling. In: Proceedings of 56th IEEE Symposium on Foundations of Computer Science, pp. 1426–1445 (2015)
26.
Daskalakis, C.: Multi-item auctions defying intuition? SIGecom Exch. 14(1), 41–75 (2015)CrossRef
27.
Daskalakis, C., Deckelbaum, A., Tzamos, C.: Mechanism design via optimal transport. In: Proceedings of 14th ACM Conference on Electronic Commerce, pp. 269–286 (2013)
28.
Daskalakis, C., Devanur, N.R., Weinberg, S.M.: Revenue maximization and ex-post budget constraints. In: Proceedings of 16th ACM Conference on Economics and Computation, pp. 433–447 (2015)
29.
Devanur, N.R., Ha, B.Q., Hartline, J.D.: Prior-free auctions for budgeted agents. In: Proceedings of 14th ACM Conference on Electronic Commerce, pp. 287–304 (2013)
30.
Devanur, N.R., Weinberg, S.M.: The optimal mechanism for selling to a budget constrained buyer: the general case. In: Proceedings of 18th ACM Conference on Economics and Computation, pp. 39–40 (2017)
31.
Dobzinski, S., Lavi, R., Nisan, N.: Multi-unit auctions with budget limits. Games Econ. Behav. 74(2), 486–503 (2012)MathSciNetCrossRef
32.
33.
Eden, A., Feldman, M., Friedler, O., Talgam-Cohen, I., Weinberg, S.M.: A simple and approximately optimal mechanism for a buyer with complements. In: Proceedings of 18th ACM Conference on Economics and Computation, p. 323 (2017)
34.
Goel, G., Mirrokni, V.S., Leme, R.P.: Polyhedral clinching auctions and the adwords polytope. J. ACM 62(3), 18:1–18:27 (2015)MathSciNetCrossRef
35.
Goldberg, A.V., Hartline, J.D., Wright, A.: Competitive auctions and digital goods. In: Proceedings of 12th ACM-SIAM Symposium on Discrete Algorithms, pp. 735–744 (2001)
36.
Gravin, N., Lu, P.: Separation in correlation-robust monopolist problem with budget. In: Proceedings of 29th ACM-SIAM Symposium on Discrete Algorithms, pp. 2069–2080 (2018)CrossRef
37.
Hart, S., Nisan, N.: Approximate revenue maximization with multiple items. In: Proceedings of 13th ACM Conference on Electronic Commerce, p. 656 (2012)
38.
Hart, S., Nisan, N.: The menu-size complexity of auctions. In: Proceedings of 14th ACM Conference on Electronic Commerce, pp. 565–566 (2013)
39.
Hart, S., Nisan, N.: Approximate revenue maximization with multiple items. J. Econ. Theory 172, 313–347 (2017)MathSciNetCrossRef
40.
Laffont, J.-J., Robert, J.: Optimal auction with financially constrained buyers. Econ. Lett. 52(2), 181–186 (1996)CrossRef
41.
Li, X., Yao, A.C.: On revenue maximization for selling multiple independently distributed items. Proc. Natl. Acad. Sci. 110(28), 11232–11237 (2013)MathSciNetCrossRef
42.
Manelli, A.M., Vincent, D.R.: Multidimensional mechanism design: revenue maximization and the multiple-good monopoly. J. Econ. Theory 137(1), 153–185 (2007)MathSciNetCrossRef
43.
44.
Pai, M.M., Vohra, R.: Optimal auctions with financially constrained buyers. J. Econ. Theory 150, 383–425 (2014)MathSciNetCrossRef
45.
Rubinstein, A., Weinberg, S.M.: Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. In: Proceedings of 16th ACM Conference on Economics and Computation, pp. 377–394 (2015)
46.
Singer, Y.: Budget feasible mechanisms. In: Proceedings of 51st IEEE Symposium on Foundations of Computer Science, pp. 765–774 (2010)
47.
Singla, A., Krause, A.: Truthful incentives in crowdsourcing tasks using regret minimization mechanisms. In: WWW, pp. 1167–1178 (2013)
48.
49.
Yao, A.C.: An n-to-1 bidder reduction for multi-item auctions and its applications. In: Proceedings of 26th ACM-SIAM Symposium on Discrete Algorithms, pp. 92–109 (2015)
Metadaten
Titel
A Simple Mechanism for a Budget-Constrained Buyer
verfasst von
Yu Cheng
Nick Gravin
Kamesh Munagala
Kangning Wang
Copyright-Jahr
2018
Buch
Web and Internet Economics

Print ISBN: 978-3-030-04611-8

Electronic ISBN: 978-3-030-04612-5

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-030-04612-5_7

Premium Partner

    Bildnachweise