nach oben

Theory of Computing Systems

Erschienen in:

01.04.2014

Repeated Budgeted Second Price Ad Auction

verfasst von: Asaph Arnon, Yishay Mansour

Erschienen in: Theory of Computing Systems | Ausgabe 3/2014

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Our main goal is to abstract existing repeated sponsored search ad auction mechanisms which incorporate budgets, and study their equilibrium and dynamics. Our abstraction has multiple agents bidding repeatedly for multiple identical items (such as impressions in an ad auction). The agents are budget limited and have a value per item. We abstract this repeated interaction as a one-shot game, which we call budget auction, where agents submit a bid and a budget, and then items are sold by a sequential second price auction. Once an agent exhausts its budget it does not participate in the proceeding auctions.

Our main result shows that if agents bid conservatively (never bid above their value) then there always exists a pure Nash equilibrium. We also study simple dynamics of repeated budget auctions, showing their convergence to a Nash equilibrium for two agents and for multiple agents with identical budgets.

Vorheriger Artikel Weakly-Acyclic (Internet) Routing Games

Nächster Artikel Random Bimatrix Games Are Asymptotically Easy to Solve (A Simple Proof)

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

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

Nur mit Berechtigung zugänglich

In real applications, even the second price auction does not have truth-telling as a dominant strategy, due to their repeated nature, bidders’ budgets, externalities, and more.

A similar conceptual abstraction to a one-shot game was done for studying the truthfulness of click through rates [5, 10].

While technically, advertisement impressions are clearly not divisible, due to the large volume of impressions, this is a very reasonable abstraction. Although using a single divisible item is equivalent, we found it less ‘natural’ for modeling ad auctions.

This hard budget approach is used also in [11]. Another way to ensure agents do not exceed their budget is if agents deposit their budget to the auctioneer (instead of just reporting it), and the auctioneer returns any unused budget at the end of the auction.

Theoretically, agent i might profit by overbidding his value, since it increases the price of the agent i−1 who ranked above him and therefore, decreases agent i−1 allocation, i.e., x _i−1. This will result in more items left for agent i and might increase agent i allocation, i.e., x _i. Nevertheless, such bidding might expose the agent to negative utility, since he might pay more than his value.

We assume that agent 2 slightly overbids c ₁, and we ignore this small perturbation.

We assume that agent j slightly underbids c _j, and we ignore this small perturbation.

Note that there is a small difference in the starting price. At this point not necessarily all agents starting price is the new reserved price: agents 1,…,j−1 bid p _min=c _j, while agents j=1,…,k bid p _min+ϵ=c _j+ϵ. We can now recalculate the new critical bids for the remaining agents, taking under consideration that agent j is not participating, and the new reserved price is c _j. From Lemma 13 we know the new lowest critical bid is at least ϵ higher than c _j, so agents 1,…,j−1 increase their bid to p _min+ϵ when it is their turn to move, and all ‘starting prices’ are equal again.

Andelman, N., Mansour, Y.: Auctions with budget constraints. In: SWAT, pp. 26–38 (2004)

Asdemir, K.: Bidding patterns in search engine auctions. In: Second Workshop on Sponsored Search Auctions, ACM Conference on Electronic Commerce (2006)

Azar, Y., Birnbaum, B.E., Karlin, A.R., Mathieu, C., Nguyen, C.T.: Improved approximation algorithms for budgeted allocations. In: ICALP, pp. 186–197 (2008)

Azar, Y., Birnbaum, B.E., Karlin, A.R., Nguyen, C.T.: On revenue maximization in second-price ad auctions. In: ESA, pp. 155–166 (2009)

Babaioff, M., Sharma, Y., Slivkins, A.: Characterizing truthful multi-armed bandit mechanisms. In: ACM Conference on Electronic Commerce, pp. 79–88 (2009)

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

Borgs, C., Chayes, J., Immorlica, N., Mahdian, M., Saberi, A.: Multi-unit auctions with budget-constrained bidders. In: ACM Conference on Electronic Commerce, pp. 44–51 (2005)

Borgs, C., Immorlica, N., Chayes, J., Jain, K.: Dynamics of bid optimization in online advertisement auctions. In: Proceedings of the 16th International World Wide Web Conference, pp. 13–723 (2007)

Cary, M., Das, A., Edelman, B., Giotis, I., Heimerl, K., Karlin, A.R., Mathieu, C., Schwarz, M.: Greedy bidding strategies for keyword auctions. In: ACM Conference on Electronic Commerce, pp. 262–271 (2007)

10.

Devanur, N.R., Kakade, S.M.: The price of truthfulness for pay-per-click auctions. In: ACM Conference on Electronic Commerce, pp. 99–106 (2009)

11.

Dobzinski, S., Nisan, N., Lavi, R.: Multi-unit auctions with budget limits. In: FOCS (2008)

12.

Edelman, B., Ostrovsky, M.: Strategic bidder behavior in sponsored search auctions. In: Workshop on Sponsored Search Auctions, ACM Conference on Electronic Commerce, pp. 192–198 (2005)

13.

Edelman, B., Ostrovsky, M., Schwarz, M.: Internet advertising and the generalized second price auction: selling billions of dollars worth of keywords. Am. Econ. Rev. 97 (2005)

14.

Fiat, A., Leonardi, S., Saia, J., Sankowski, P.: Single valued combinatorial auctions with budgets. In: ACM Conference on Electronic Commerce, pp. 223–232 (2011)

15.

Kitts, B., LeBlanc, B.J.: Optimal bidding on keyword auctions. EM 14(3), 186–201 (2004)

16.

Lehmann, B., Lehmann, D.J., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55(2), 270–296 (2006) CrossRefMATHMathSciNet

17.

Leme, R.P., Tardos, É.: Pure and Bayes-Nash price of anarchy for generalized second price auction. In: FOCS, pp. 735–744 (2010)

18.

Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. J. ACM 54(5), 22 (2007) CrossRefMathSciNet

19.

Muthukrishnan, S.: Ad exchanges: research issues. In: WINE, pp. 1–12. Springer, Berlin (2009)

20.

Nisan, N.: Google’s auction for TV ads. In: ESA, p. 553 (2009)

21.

Nisan, N., Rougarden, T., Tardos, E., Vazirani, V. (eds.): Algorithmic Game Theory. Cambridge University Press, Cambridge (2007) MATH

22.

Orda, A., Rom, R., Shimkin, N.: Competitive routing in multiuser communication networks. IEEE/ACM Trans. Netw. 1(5), 510–521 (1993) CrossRef

23.

Varian, H.R.: Position auctions. Int. J. Ind. Organ. (2006)

Titel: Repeated Budgeted Second Price Ad Auction
verfasst von: Asaph Arnon
Yishay Mansour
Publikationsdatum: 01.04.2014
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 3/2014
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-013-9472-1

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"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2014

Weakly-Acyclic (Internet) Routing Games

Strategic Pricing in Next-Hop Routing with Elastic Demands

Special Issue on Algorithmic Game Theory

A Truthful Mechanism for Value-Based Scheduling in Cloud Computing

Complexity of Rational and Irrational Nash Equilibria

Scheduling Without Payments