research-article

Mechanism Design for Mixed Bidders

Authors:

Yoram Bachrach,

Mohammad Reza KhaniAuthors Info & Claims

WWW '16: Proceedings of the 25th International Conference on World Wide Web

Pages 215 - 225

https://doi.org/10.1145/2872427.2882983

Published: 11 April 2016 Publication History

Abstract

The Generalized Second Price (GSP) auction has appealing properties when ads are simple (text based and identical in size), but does not generalize to richer ad settings, whereas truthful mechanisms such as VCG do. However, a straight switch from GSP to VCG incurs significant revenue loss for the search engine. We introduce a transitional mechanism which encourages advertisers to update their bids to their valuations, while mitigating revenue loss. In this setting, it is easier to propose first a payment function rather than an allocation function, so we give a general framework which guarantees incentive compatibility by requiring that the payment functions satisfy two specific properties. Finally, we analyze the revenue impacts of our mechanism on a sample of Bing data.

References

[1]

G. Aggarwal, J. Feldman, and S. Muthukrishnan. Bidding to the top: Vcg and equilibria of position-based auctions. In Approximation and Online Algorithms, pages 15--28. Springer, 2007.

Digital Library

[2]

G. Aggarwal, A. Goel, and R. Motwani. Truthful auctions for pricing search keywords. In Proceedings of the 7th ACM conference on Electronic commerce, pages 1--7. ACM, 2006.

Digital Library

[3]

G. Aggarwal, S. Muthukrishnan, D. Pál, and M. Pál. General auction mechanism for search advertising. In Proceedings of the 18th international conference on World wide web (WWW), pages 241--250. ACM, 2009.

Digital Library

[4]

A. Archer and R. Kleinberg. Truthful germs are contagious: a local to global characterization of truthfulness. In Proceedings of the 9th ACM Conference on Electronic Commerce, pages 21--30, 2008.

Digital Library

[5]

I. Ashlagi, M. Braverman, A. Hassidim, and D. Monderer. Monotonicity and implementability. Econometrica, 78(5):1749--1772, 2010.

[6]

I. Ashlagi, D. Monderer, and M. Tennenholtz. Mediators in position auctions. In Proceedings of the 8th ACM conference on Electronic commerce, pages 279--287. ACM, 2007.

Digital Library

[7]

S. Athey and D. Nekipelov. A structural model of sponsored search advertising auctions. In Sixth ad auctions workshop, 2010.

[8]

Y. Bachrach, S. Ceppi, I. A. Kash, P. Key, and D. Kurokawa. Optimising trade-offs among stakeholders in ad auctions. In ACM Conference on Economics and Computation, EC '14, Stanford, CA, USA, June 8--12, 2014, pages 75--92, 2014.

Digital Library

[9]

I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, and M. Kyropoulou. On the efficiency of equilibria in generalized second price auctions. In Proceedings of the 12th ACM conference on Electronic commerce, pages 81--90. ACM, 2011.

Digital Library

[10]

M. Cary, A. Das, B. Edelman, I. Giotis, K. Heimerl, A. R. Karlin, C. Mathieu, and M. Schwarz. Greedy bidding strategies for keyword auctions. In Proceedings of the 8th ACM conference on Electronic commerce, pages 262--271. ACM, 2007.

Digital Library

[11]

B. Edelman, M. Ostrovsky, and M. Schwarz. Internet Advertising and the Generalized Second Price Auction: Selling Billions of Dollars Worth of Keywords. 2005.

[12]

B. Edelman and M. Schwarz. Optimal auction design and equilibrium selection in sponsored search auctions. The American Economic Review, pages 597--602, 2010.

[13]

R. M. Frongillo and I. A. K. and. General truthfulness characterizations via convex analysis. In 10th Conference on Web and Internet Economics (WINE), 2014. To Appear.

[14]

R. Gomes and K. Sweeney. Bayes--nash equilibria of the generalized second-price auction. Games and Economic Behavior, 86:421--437, 2014.

[15]

R. P. Leme and É. Tardos. Sponsored search equilibria for conservative bidders. In Fifth Workshop on Ad Auctions, 2009.

[16]

B. Lucier, R. Paes Leme, and E. Tardos. On revenue in the generalized second price auction. In Proceedings of the 21st international conference on World Wide Web, pages 361--370. ACM, 2012.

Digital Library

[17]

R. B. Myerson. Optimal Auction Design. Mathematics of Operations Research, 6:58--73, 1981.

Digital Library

[18]

F. Pin and P. Key. Stochastic variability in sponsored search auctions: observations and models. In Proceedings of the 12th ACM conference on Electronic commerce, pages 61--70. ACM, 2011.

Digital Library

[19]

B. Roberts, D. Gunawardena, I. A. Kash, and P. Key. Ranking and tradeoffs in sponsored search auctions. In Proc. of the Fourteenth ACM Conf. on Electronic Commerce, EC '13, pages 751--766, 2013.

Digital Library

[20]

D. R. Thompson and K. Leyton-Brown. Revenue optimization in the generalized second-price auction. In Proceedings of the Fourteenth ACM Conference on Electronic Commerce, EC '13, pages 837--852, New York, NY, USA, 2013. ACM.

Digital Library

[21]

H. R. Varian. Position auctions. international Journal of industrial Organization, 25(6):1163--1178, 2007.

[22]

H. R. Varian and C. Harris. The VCG auction in theory and practice. The American Economic Review, 104(5):442--445, 2014.

[23]

Y. Vorobeychik. Simulation-based game theoretic analysis of keyword auctions with low-dimensional bidding strategies. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 583--590. AUAI Press, 2009.

Digital Library

Cited By

Tang XLv HGao YWu FLiu LCui LDastani MSichman JAlechina NDignum V(2024)Towards Efficient Auction Design with ROI ConstraintsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663044(1818-1826)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663044
Maillé PTuffin B(2018)Auctions for online ad space among advertisers sensitive to both views and clicksElectronic Commerce Research10.1007/s10660-017-9267-618:3(485-506)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s10660-017-9267-6
Hummel P(2018)Hybrid mechanisms for Vickrey–Clarke–Groves and generalized second-price bidsInternational Journal of Game Theory10.1007/s00182-017-0591-947:1(331-350)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1007/s00182-017-0591-9

Index Terms

Mechanism Design for Mixed Bidders
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Algorithmic mechanism design

Recommendations

Core-competitive Auctions
EC '15: Proceedings of the Sixteenth ACM Conference on Economics and Computation

One of the major drawbacks of the celebrated VCG auction is its low (or zero) revenue even when the agents have high value for the goods and a competitive outcome would have generated a significant revenue. A competitive outcome is one for which it is ...
Diffusion auction design
Abstract
This paper studies an auction design problem for a seller to sell a single commodity in a social network, where each individual (the seller or a buyer) can only communicate with her neighbors. The challenge is to design a mechanism to incentivize ...
Multi-Unit Bayesian Auction with Demand or Budget Constraints

We consider the problem of revenue maximization on multi-unit auctions where items are distinguished by their relative values; any pair of items has the same ratio of values to all buyers. As is common in the study of revenue maximizing problems, we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

WWW '16: Proceedings of the 25th International Conference on World Wide Web

April 2016

1482 pages

ISBN:9781450341431

General Chairs:
Jacqueline Bourdeau
Tele-university (TELUQ), Montreal, QC, Canada
,
Jim A. Hendler
Rensselaer Polytechnic Institute, Troy, NY, USA
,
Roger Nkambou Nkambou
Université du Québec à Montréal, Montreal, QC, Canada
,
Program Chairs:
Ian Horrocks
University of Oxford, UK
,
Ben Y. Zhao
University of California at Santa Barbara, CA, USA

Copyright © 2016 Copyright is held by the International World Wide Web Conference Committee (IW3C2).

Sponsors

IW3C2: International World Wide Web Conference Committee

In-Cooperation

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

International World Wide Web Conferences Steering Committee

Republic and Canton of Geneva, Switzerland

Publication History

Published: 11 April 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

WWW '16

Sponsor:

IW3C2

WWW '16: 25th International World Wide Web Conference

April 11 - 15, 2016

Québec, Montréal, Canada

Acceptance Rates

WWW '16 Paper Acceptance Rate 115 of 727 submissions, 16%;

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
157
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tang XLv HGao YWu FLiu LCui LDastani MSichman JAlechina NDignum V(2024)Towards Efficient Auction Design with ROI ConstraintsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663044(1818-1826)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663044
Maillé PTuffin B(2018)Auctions for online ad space among advertisers sensitive to both views and clicksElectronic Commerce Research10.1007/s10660-017-9267-618:3(485-506)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s10660-017-9267-6
Hummel P(2018)Hybrid mechanisms for Vickrey–Clarke–Groves and generalized second-price bidsInternational Journal of Game Theory10.1007/s00182-017-0591-947:1(331-350)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1007/s00182-017-0591-9

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents