AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home CAAI Artificial Intelligence Research Article
PDF (667.5 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Article | Open Access

Private Data Manipulation in Sponsored Search Auctions

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
Show Author Information

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 economicssponsored search auctionMyerson’s auctiongeneralized first-price auctiondata-driven decision making

References

[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.
Crossref Google Scholar
[2]

H. R. Varian, Position auctions, Int. J. Ind. Organ., vol. 25, no. 6, pp. 1163–1178, 2007.
Crossref 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.
Crossref Google Scholar
[4]

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

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

T. Groves, Incentives in teams, Econometrica, vol. 41, no. 4, p. 617, 1973.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref Google Scholar
[20]

H. R. Varian, Online ad auctions, Am. Econ. Rev., vol. 99, no. 2, pp. 430–434, 2009.
Crossref 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.
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref
[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.
Crossref
[28]

S. They and I. Segal, An efficient dynamic mechanism, Econometrica, vol. 81, no. 6, pp. 2463–2485, 2013.
Crossref Google Scholar
[29]
D. Bergemann and J. Valimaki, The dynamic pivot mechanism, SSRN Electron. J., DOI: 10.2139/ssrn.1521685.
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref
[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.
Crossref
[46]

H. Zhang and V. Conitzer, Incentive-aware PAC learning, Proc. AAAI Conf. Artif. Intell., vol. 35, no. 6, pp. 5797–5804, 2021.
Crossref Google Scholar
[47]
J. D. Hartline, Optimal mechanisms, in Mechanism Design and Approximation, https://jasonhartline.com/MDnA/, 2013.
Crossref
[48]
S. Chawla and J. D. Hartline, Auctions with unique equilibria, in Proc. fourteenth ACM Conf. Electronic Commerce, 2013, pp. 181–196.
Crossref
[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.
Crossref
[50]

E. Maskin and J. Riley, Asymmetric auctions, Rev. Econ. Stud., vol. 67, no. 3, pp. 413–438, 2000.
Crossref 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.
Crossref 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.
Crossref
[53]
Y. Chen, X. Deng, and Y. Li, Optimal private payoff manipulation against commitment in extensive-form games, arXiv preprint arXiv: 2206.13119, 2022.
Crossref
CAAI Artificial Intelligence Research
Volume 2,
2023
Article number: 9150024
DOI: 10.26599/AIR.2023.9150024
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
Part of a topical collection:
Decision Intelligence

631

Views

55

Downloads

0

Crossref

Altmetrics
Received: 03 August 2023
Revised: 09 October 2023
Accepted: 03 November 2023
Published: 09 January 2024
© The author(s) 2023.

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