{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:49:05Z","timestamp":1778496545099,"version":"3.51.4"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2-3","license":[{"start":{"date-parts":[[2014,10,28]],"date-time":"2014-10-28T00:00:00Z","timestamp":1414454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Social Fund and Greek national funds through the research funding program Thales on \u201cAlgorithmic Game Theory\u201d"},{"DOI":"10.13039\/501100004895","name":"European Social Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004895","id-type":"DOI","asserted-by":"publisher"}]},{"name":"\u201cCaratheodory\u201d research grant from the University of Patras"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Internet Technol."],"published-print":{"date-parts":[[2014,10,28]]},"abstract":"<jats:p>Sponsored search auctions are the main source of revenue for search engines. In such an auction, a set of utility maximizing advertisers competes for a set of ad slots. The assignment of advertisers to slots depends on the bids they submit; these bids may be different than the true valuations of the advertisers for the slots. Variants of the celebrated VCG auction mechanism guarantee that advertisers act truthfully and, under some assumptions, lead to revenue or social welfare maximization. Still, the sponsored search industry mostly uses generalized second price (GSP) auctions; these auctions are known to be nontruthful and suboptimal in terms of social welfare and revenue. In an attempt to explain this tradition, we study a Bayesian setting wherein the valuations of advertisers are drawn independently from a common regular probability distribution. In this setting, it is well known from the work of Myerson [1981] that the optimal revenue is obtained by the VCG mechanism with a particular reserve price that depends on the probability distribution. We show that, by appropriately setting the reserve price, the revenue over any Bayes-Nash equilibrium of the game induced by the GSP auction is at most a small constant factor away from the optimal revenue, improving previous results of Lucier et al. [2012]. Our analysis is based on the Bayes-Nash equilibrium conditions and the improved results are obtained by bounding the utility of each player at equilibrium using infinitely many deviating bids and also by developing novel prophet-like inequalities.<\/jats:p>","DOI":"10.1145\/2663497","type":"journal-article","created":{"date-parts":[[2014,10,28]],"date-time":"2014-10-28T12:40:29Z","timestamp":1414500029000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Revenue Guarantees in the Generalized Second Price Auction"],"prefix":"10.1145","volume":"14","author":[{"given":"Ioannis","family":"Caragiannis","sequence":"first","affiliation":[{"name":"University of Patras and CTI, Rio, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Kaklamanis","sequence":"additional","affiliation":[{"name":"University of Patras and CTI, Rio, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panagiotis","family":"Kanellopoulos","sequence":"additional","affiliation":[{"name":"University of Patras and CTI, Rio, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Kyropoulou","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,10,28]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177703282"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993588"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"I. Caragiannis C. Kaklamanis P. Kanellopoulos M. Kyropoulou B. Lucier R. Paes Leme and E. Tardos. 2014. Bounding the inefficiency of outcomes in generalized second price auctions. J. Econ. Theory (to appear).  I. Caragiannis C. Kaklamanis P. Kanellopoulos M. Kyropoulou B. Lucier R. Paes Leme and E. Tardos. 2014. Bounding the inefficiency of outcomes in generalized second price auctions. J. Econ. Theory (to appear).","DOI":"10.1016\/j.jet.2014.04.010"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2483188"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250946"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806733"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"e_1_2_2_8_1","unstructured":"P. Dutting and R. Kleinberg. 2013. Polymatroid prophet inequalities. http:\/\/arxiv.org\/abs\/1307.5299.  P. Dutting and R. Kleinberg. 2013. Polymatroid prophet inequalities. http:\/\/arxiv.org\/abs\/1307.5299."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.97.1.242"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2012.09.001"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_2_2_12_1","volume-title":"Proceedings of the 22nd National Conference on Artificial Intelligence (AAAI'07)","volume":"1","author":"Hajiaghayi M. T."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.14.3.159"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000045"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213991"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"e_1_2_2_17_1","unstructured":"V. Krishna. 2002. Auction Theory. Academic Press.  V. Krishna. 2002. Auction Theory. Academic Press."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134731"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993587"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187886"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993585"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.75"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482568"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482612"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijindorg.2006.10.002"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"}],"container-title":["ACM Transactions on Internet Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2663497","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2663497","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:12:48Z","timestamp":1750227168000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2663497"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,28]]},"references-count":27,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2014,10,28]]}},"alternative-id":["10.1145\/2663497"],"URL":"https:\/\/doi.org\/10.1145\/2663497","relation":{},"ISSN":["1533-5399","1557-6051"],"issn-type":[{"value":"1533-5399","type":"print"},{"value":"1557-6051","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,28]]},"assertion":[{"value":"2013-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}