Journal Home > Volume 2
CAAI Artificial Intelligence Research 2023, 2: 9150024 https://doi.org/10.26599/AIR.2023.9150024
Article | Open Access | Issue | Published: 09 January 2024

Private Data Manipulation in Sponsored Search Auctions

Show Author's Information Xiaotie Deng1( ),  Tao Lin2,  Tao Xiao3
Center on Frontiers of Computing Studies, Department of Computer Science, Peking University, Beijing 100871, China
School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA
Huawei TCS Lab, Shanghai 201206, China
Keywords:
Internet economics, sponsored search auction, Myerson’s auction, generalized first-price auction, data-driven decision making
Cite this article:
Deng X, Lin T, Xiao T. Private Data Manipulation in Sponsored Search Auctions. CAAI Artificial Intelligence Research, 2023, 2: 9150024. https://doi.org/10.26599/AIR.2023.9150024
Download citation
EndNote(RIS)
BibTeX

368

Views

43

Downloads

Citations

0

Crossref

N/A

WoS

N/A

Scopus

N/A

CSCD

Abstract Full text About this article

The repeated nature of sponsored search auctions allows the seller to implement Myerson’s auction to maximize revenue using past data. But since these data are provided by strategic buyers in the auctions, they can be manipulated, which may hurt the seller’s revenue. We model this problem as a Private Data Manipulation (PDM) game: the seller first announces an auction (such as Myerson’s) whose allocation and payment rules depend on the value distributions of buyers; the buyers then submit fake value distributions to the seller to implement the auction. The seller’s expected revenue and the buyers’ expected utilities depend on the auction rule and the game played among the buyers in their choices of the submitted distributions. Under the PDM game, we show that Myerson’s auction is equivalent to the generalized first-price auction, and under further assumptions equivalent to the Vickrey–Clarke–Groves (VCG) auction and the generalized second-price auction. Our results partially explain why Myerson’s auction is not as popular as the generalized second-price auction in the practice of sponsored search auctions, and provide new perspectives into data-driven decision making in mechanism design.


menu
Abstract
Full text
Outline
About this article

Private Data Manipulation in Sponsored Search Auctions

Show Author's information Xiaotie Deng1( ), Tao Lin2, Tao Xiao3
Center on Frontiers of Computing Studies, Department of Computer Science, Peking University, Beijing 100871, China
School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA
Huawei TCS Lab, Shanghai 201206, China

Abstract

The repeated nature of sponsored search auctions allows the seller to implement Myerson’s auction to maximize revenue using past data. But since these data are provided by strategic buyers in the auctions, they can be manipulated, which may hurt the seller’s revenue. We model this problem as a Private Data Manipulation (PDM) game: the seller first announces an auction (such as Myerson’s) whose allocation and payment rules depend on the value distributions of buyers; the buyers then submit fake value distributions to the seller to implement the auction. The seller’s expected revenue and the buyers’ expected utilities depend on the auction rule and the game played among the buyers in their choices of the submitted distributions. Under the PDM game, we show that Myerson’s auction is equivalent to the generalized first-price auction, and under further assumptions equivalent to the Vickrey–Clarke–Groves (VCG) auction and the generalized second-price auction. Our results partially explain why Myerson’s auction is not as popular as the generalized second-price auction in the practice of sponsored search auctions, and provide new perspectives into data-driven decision making in mechanism design.

Keywords: Internet economics, sponsored search auction, Myerson’s auction, generalized first-price auction, data-driven decision making

References(53)

[1]

B. Edelman, M. Ostrovsky, and M. Schwarz, Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords, Am. Econ. Rev., vol. 97, no. 1, pp. 242–259, 2007.
DOI Google Scholar
[2]

H. R. Varian, Position auctions, Int. J. Ind. Organ., vol. 25, no. 6, pp. 1163–1178, 2007.
DOI Google Scholar
[3]

B. Edelman and M. Ostrovsky, Strategic bidder behavior in sponsored search auctions, Decis. Support. Syst., vol. 43, no. 1, pp. 192–198, 2007.
DOI Google Scholar
[4]

W. Vickrey, Counterspeculation, auctions, and competitive sealed tenders, J. Finance, vol. 16, no. 1, pp. 8–37, 1961.
DOI Google Scholar
[5]

E. H. Clarke, Multipart pricing of public goods, Public Choice, vol. 11, no. 1, pp. 17–33, 1971.
DOI Google Scholar
[6]

T. Groves, Incentives in teams, Econometrica, vol. 41, no. 4, p. 617, 1973.
DOI Google Scholar
[7]
A. Beattiea, The story behind Google’s success, https://www.investopedia.com/articles/personal-finance/042415/story-behind-googles-success.asp, 2018.
[8]

R. B. Myerson, Optimal auction design, Math. Oper. Res., vol. 6, no. 1, pp. 58–73, 1981.
DOI Google Scholar
[9]
C. Guo, Z. Huang, and X. Zhang, Settling the sample complexity of single-parameter revenue maximization, in Proc. 51st Annu. ACM SIGACT Symp. Theory of Computing, Phoenix, AZ, USA, 2019, pp. 662–673.
DOI
[10]
C. Guo, Z. Huang, Z. G. Tang, and X. Zhang, Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and Pandora’s problem, in Proc. 34th Annu. Conf. Learning Theory, Boulder, CO, USA, 2019, pp. 2248–2288.
[11]
M. Ostrovsky and M. Schwarz, Reserve prices in Internet advertising auctions: A field experiment, SSRN Electron. J., DOI: 10.2139/ssrn.1573947.
DOI
[12]
P. Tang and Y. Zeng, The price of prior dependence in auctions, in Proc. 2018 ACM Conf. Economics and Computation, Ithaca, NY, USA, 2018, pp. 485–502.
DOI
[13]
S. Lahaie, D. Pennock, A. Saberi, and R. Vohra, Sponsored search auctions, in Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani Eds. Cambridge, UK: Cambridge University Press, 2007, pp. 699–716.
DOI
[14]

T. M. Bu, X. Deng, and Q. Qi, Multi-bidding strategy in sponsored search auctions, J. Comb. Optim., vol. 23, no. 3, pp. 356–372, 2012.
DOI Google Scholar
[15]

R. Gomes and K. Sweeney, Bayes–Nash equilibria of the generalized second-price auction, Games Econ. Behav., vol. 86, pp. 421–437, 2014.
DOI Google Scholar
[16]
R. P. Leme and E. Tardos, Pure and Bayes–Nash price of anarchy for generalized second price auction, in Proc. 2010 IEEE 51st Ann. Symp. Foundations of Computer Science, Las Vegas, NV, USA, 2010, pp. 735–744.
DOI
[17]
B. Lucier and R. P. Leme, GSP auctions with correlated types, in Proc. 12th ACM Conf. Electronic Commerce, San Jose, CA, USA, 2011, pp. 71–80.
DOI
[18]
I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, and M. Kyropoulou, On the efficiency of equilibria in generalized second price auctions, in Proc. 12th ACM Conf. Electronic Commerce, San Jose, CA, USA, 2011, pp. 81–90.
DOI
[19]

B. Edelman and M. Schwarz, Optimal auction design and equilibrium selection in sponsored search auctions, Am. Econ. Rev., vol. 100, no. 2, pp. 597–602, 2010.
DOI Google Scholar
[20]

H. R. Varian, Online ad auctions, Am. Econ. Rev., vol. 99, no. 2, pp. 430–434, 2009.
DOI Google Scholar
[21]
B. Lucier, R. P. Leme, and E. Tardos, On revenue in the generalized second price auction, in Proc. 21st Int. Conf. World Wide Web, Lyon, France, 2012, pp. 361–370.
DOI
[22]
R. Cole and T. Roughgarden, The sample complexity of revenue maximization, in Proc. forty-sixth annual ACM Symp. Theory of Computing, New York, New York, 2014, pp. 243–252.
DOI
[23]
V. Syrgkanis, A sample complexity measure with applications to learning optimal auctions, in Proc. 31st Int. Conf. Neural Information Processing Systems, Long Beach, CA, USA, 2017, pp. 5358–5365.
[24]

Z. Huang, Y. Mansour, and T. Roughgarden, Making the most of your samples, SIAM J. Comput., vol. 47, no. 3, pp. 651–674, 2018.
DOI Google Scholar
[25]
M. F. F. Balcan, T. Sandholm, and E. Vitercik, Sample complexity of automated mechanism design, in Proc. 30th Conf. Neural Information Processing Systems (NIPS 2016), Barcelona, Spain, 2016, pp. 2083–2091.
[26]
Y. Cai and C. Daskalakis, Learning multi-item auctions with (or without) samples, in Proc. 2017 IEEE 58th Annu. Symp. Foundations of Computer Science (FOCS), Berkeley, CA, USA, 2017, pp. 516–527.
DOI
[27]
M. F. Balcan, T. Sandholm, and E. Vitercik, A general theory of sample complexity for multi-item profit maximization, in Proc. 2018 ACM Conf. Economics and Computation, Ithaca, NY, USA, 2018, pp. 173–174.
DOI
[28]

S. They and I. Segal, An efficient dynamic mechanism, Econometrica, vol. 81, no. 6, pp. 2463–2485, 2013.
DOI Google Scholar
[29]
D. Bergemann and J. Valimaki, The dynamic pivot mechanism, SSRN Electron. J., DOI: 10.2139/ssrn.1521685.
DOI
[30]
H. Nazerzadeh, A. Saberi, and R. Vohra, Dynamic cost-per-action mechanisms and applications to online advertising, in Proc. 17th Int. Conf. World Wide Web, Beijing, China, 2008, pp. 179–188.
DOI
[31]

M. Babaioff, Y. Sharma, and A. Slivkins, Characterizing truthful multi-armed bandit mechanisms, SIAM J. Comput., vol. 43, no. 1, pp. 194–230, 2014.
DOI Google Scholar
[32]
N. R. Devanur and S. M. Kakade, The price of truthfulness for pay-per-click auctions, in Proc. 10th ACM Conf. Electronic Commerce, Stanford, CA, USA, 2009, pp. 99–106.
DOI
[33]
M. Babaioff, R. D. Kleinberg, and A. Slivkins, Truthful mechanisms with implicit payment computation, in Proc. 11th ACM Conf. Electronic Commerce, New York, NY, USA, 2010, pp. 43–52.
DOI
[34]
K. Amin, A. Rostamizadeh, and U. Syed, Learning prices for repeated auctions with strategic buyers, in Proc. 26th Int. Conf. Neural Information Processing Systems, Lake Tahoe, NV, USA, 2013, pp. 1169–1177.
[35]
K. Amin, A. Rostamizadeh, and U. Syed, Repeated contextual auctions with strategic buyers, in Proc. 27th Int. Conf. Neural Information Processing Systems, Montreal, Canada, 2014, pp. 622–630.
[36]
M. Braverman, J. Mao, J. Schneider, and M. Weinberg, Selling to a no-regret buyer, in Proc. 2018 ACM Conf. Economics and Computation, Ithaca, NY, USA, 2018, pp. 523–538.
DOI
[37]
Z. Huang, J. Liu, and X. Wang, Learning optimal reserve price against non-myopic bidders, in Proc. 32nd Conf. Neural Information Processing Systems (NIPS 2018), Montreal, Canada, 2018, pp. 2042–2052.
[38]
J. D. Abernethy, R. Cummings, B. Kumar, S. Taggart, and J. H. Morgenstern, Learning auctions with robust incentive guarantees, in Proc. 33rd Conf. Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada, 2019, pp. 11587–11597.
[39]
X. Deng, R. Lavi, T. Lin, Q. Qi, W. Wang, and X. Yan, A game-theoretic analysis of the empirical revenue maximization algorithm with endogenous sampling, in Proc. 34th Conf. Neural Information Processing Systems (NeurIPS 2020) virtual, 2020.
[40]

X. Deng, T. Xiao, and K. Zhu, Learn to play maximum revenue auction, IEEE Trans. Cloud Comput., vol. 7, no. 4, pp. 1057–1067, 2019.
DOI Google Scholar
[41]

X. Deng and K. Zhu, On Bayesian epistemology of myerson auction, IEEE Trans. Cloud Comput., vol. 9, no. 3, pp. 1172–1179, 2021.
DOI Google Scholar
[42]
T. Nedelec, N. El Karoui, and V. Perchet, Learning to bid in revenue maximizing auction, in Proc. The 2019 World Wide Web Conference, San Francisco, USA, 2019, pp. 934–935.
DOI
[43]

O. Dekel, F. Fischer, and A. D. Procaccia, Incentive compatible regression learning, J. Comput. Syst. Sci., vol. 76, no. 8, pp. 759–777, 2010.
DOI Google Scholar
[44]
M. Hardt, N. Megiddo, C. Papadimitriou, and M. Wootters, Strategic classification, in Proc. 2016 ACM Conf. Innovations in Theoretical Computer Science, Cambridge, MA, USA, 2016, pp. 111–122.
DOI
[45]
Y. Chen, C. Podimata, A. D. Procaccia, and N. Shah, Strategyproof linear regression in high dimensions, in Proc. 2018 ACM Conf. Economics and Computation, New York, NY, USA, 2018, pp. 9–26.
DOI
[46]

H. Zhang and V. Conitzer, Incentive-aware PAC learning, Proc. AAAI Conf. Artif. Intell., vol. 35, no. 6, pp. 5797–5804, 2021.
DOI Google Scholar
[47]
J. D. Hartline, Optimal mechanisms, in Mechanism Design and Approximation, https://jasonhartline.com/MDnA/, 2013.
DOI
[48]
S. Chawla and J. D. Hartline, Auctions with unique equilibria, in Proc. fourteenth ACM Conf. Electronic Commerce, 2013, pp. 181–196.
DOI
[49]
N. Nisan, Introduction to mechanism design (for computer scientists), in Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani Eds. Cambridge, UK: Cambridge University Press, 2007, pp. 209–242.
DOI
[50]

E. Maskin and J. Riley, Asymmetric auctions, Rev. Econ. Stud., vol. 67, no. 3, pp. 413–438, 2000.
DOI Google Scholar
[51]

J. Cremer and R. P. McLean, Optimal selling strategies under uncertainty for a discriminating monopolist when demands are interdependent, Econometrica, vol. 53, no. 2, p. 345, 1985.
DOI Google Scholar
[52]
Z. Chen, X. Deng, J. Li, C. Wang, and M. Yang, Budget-constrained auctions with unassured priors, arXiv preprint arXiv: 2203.16816, 2022.
DOI
[53]
Y. Chen, X. Deng, and Y. Li, Optimal private payoff manipulation against commitment in extensive-form games, arXiv preprint arXiv: 2206.13119, 2022.
DOI
Publication history
Copyright
Rights and permissions

Publication history

Received: 03 August 2023
Revised: 09 October 2023
Accepted: 03 November 2023
Published: 09 January 2024
Issue date: December 2023

Copyright

© The author(s) 2023.

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return