Abstract
The paper designs revenue-maximizing auction mechanisms for agents who aim to maximize their total obtained values rather than the classical quasi-linear utilities. Several models have been proposed to capture the behaviors of such agents in the literature. In the paper, we consider the model where agents are subject to budget and return-on-spend constraints. The budget constraint of an agent limits the maximum payment she can afford, while the return-on-spend constraint means that the ratio of the total obtained value (return) to the total payment (spend) cannot be lower than the targeted bar set by the agent. The problem was first coined by [5]. In their work, only Bayesian mechanisms were considered. We initiate the study of the problem in the worst-case model and compare the revenue of our mechanisms to an offline optimal solution, the most ambitious benchmark. The paper distinguishes two main auction settings based on the accessibility of agents’ information: fully private and partially private. In the fully private setting, an agent’s valuation, budget, and target bar are all private. We show that if agents are unit-demand, constant approximation mechanisms can be obtained; while for additive agents, there exists a mechanism that achieves a constant approximation ratio under a large market assumption. The partially private setting is the setting considered in the previous work [5] where only the agents’ target bars are private. We show that in this setting, the approximation ratio of the single-item auction can be further improved, and a \(\mathrm {\Omega }(1/\sqrt{n})\)-approximation mechanism can be derived for additive agents.
All authors (ordered alphabetically) have equal contributions. The full version is available at https://arxiv.org/abs/2307.04302.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
A mechanism is truthful if for any agent i, reporting the true private information always maximizes the utility regardless of other agents’ reported profiles, and the utility of any truthtelling agent is non-negative.
References
Aggarwal, G., Badanidiyuru, A., Mehta, A.: Autobidding with constraints. In: Caragiannis, I., Mirrokni, V., Nikolova, E. (eds.) WINE 2019. LNCS, vol. 11920, pp. 17–30. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-35389-6_2
Babaioff, M., Cole, R., Hartline, J.D., Immorlica, N., Lucier, B.: Non-quasi-linear agents in quasi-linear mechanisms (extended abstract). In: ITCS. LIPIcs, vol. 185, pp. 84:1–84:1. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
Baisa, B.: Auction design without quasilinear preferences. Theor. Econ. 12(1), 53–78 (2017)
Balseiro, S.R., Deng, Y., Mao, J., Mirrokni, V.S., Zuo, S.: Robust auction design in the auto-bidding world. In: NeurIPS, pp. 17777–17788 (2021)
Balseiro, S.R., Deng, Y., Mao, J., Mirrokni, V.S., Zuo, S.: Optimal mechanisms for value maximizers with budget constraints via target clipping. In: EC, p. 475. ACM (2022)
Balseiro, S.R., Kim, A., Mahdian, M., Mirrokni, V.S.: Budget-constrained incentive compatibility for stationary mechanisms. In: EC, pp. 607–608. ACM (2020)
Bei, X., Chen, N., Gravin, N., Lu, P.: Budget feasible mechanism design: from prior-free to Bayesian. In: STOC, pp. 449–458. ACM (2012)
Borgs, C., Chayes, J.T., Immorlica, N., Mahdian, M., Saberi, A.: Multi-unit auctions with budget-constrained bidders. In: EC, pp. 44–51. ACM (2005)
Caragiannis, I., Voudouris, A.A.: The efficiency of resource allocation mechanisms for budget-constrained users. Math. Oper. Res. 46(2), 503–523 (2021)
Cavallo, R., Krishnamurthy, P., Sviridenko, M., Wilkens, C.A.: Sponsored search auctions with rich ads. In: WWW, pp. 43–51. ACM (2017)
Chawla, S., Malec, D.L., Malekian, A.: Bayesian mechanism design for budget-constrained agents. In: EC, pp. 253–262. ACM (2011)
Che, Y., Gale, I.L.: The optimal mechanism for selling to a budget-constrained buyer. J. Econ. Theory 92(2), 198–233 (2000)
Chen, N., Gravin, N., Lu, P.: On the approximability of budget feasible mechanisms. In: SODA, pp. 685–699. SIAM (2011)
Chen, N., Gravin, N., Lu, P.: Truthful generalized assignments via stable matching. Math. Oper. Res. 39(3), 722–736 (2014)
Deng, Y., Mao, J., Mirrokni, V.S., Zuo, S.: Towards efficient auctions in an auto-bidding world. In: WWW, pp. 3965–3973. ACM/IW3C2 (2021)
Devanur, N.R., Weinberg, S.M.: The optimal mechanism for selling to a budget constrained buyer: The general case. In: EC, pp. 39–40. ACM (2017)
Dobzinski, S., Lavi, R., Nisan, N.: Multi-unit auctions with budget limits. In: FOCS, pp. 260–269. IEEE Computer Society (2008)
Dobzinski, S., Leme, R.P.: Efficiency guarantees in auctions with budgets. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 392–404. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43948-7_33
Jalaly, P., Tardos, É.: Simple and efficient budget feasible mechanisms for monotone submodular valuations. ACM Trans. Econ. Comput. 9(1), 4:1–4:20 (2021)
Leonardi, S., Monaco, G., Sankowski, P., Zhang, Q.: Budget feasible mechanisms on matroids. Algorithmica 83(5), 1222–1237 (2021)
Lu, P., Xiao, T.: Improved efficiency guarantees in auctions with budgets. In: EC, pp. 397–413. ACM (2015)
Lu, P., Xiao, T.: Liquid welfare maximization in auctions with multiple items. In: Bilò, V., Flammini, M. (eds.) SAGT 2017. LNCS, vol. 10504, pp. 41–52. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66700-3_4
Lv, H., et al.: Utility maximizer or value maximizer: mechanism design for mixed bidders in online advertising. In: AAAI 2023 (2023)
Myerson, R.B.: Optimal auction design. Math. Oper. Res. 6(1), 58–73 (1981)
Nisan, N., Ronen, A.: Algorithmic mechanism design. Games Econ. Behav. 35(1–2), 166–196 (2001)
Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V.V. (eds.): Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)
Pai, M.M., Vohra, R.: Optimal auctions with financially constrained buyers. J. Econ. Theory 150, 383–425 (2014)
Singer, Y.: Budget feasible mechanisms. In: FOCS, pp. 765–774. IEEE Computer Society (2010)
Zhou, Y., Serizawa, S.: Multi-object auction design beyond quasi-linearity: leading examples. Technical report, ISER Discussion Paper (2021)
Acknowledgements
Chenyang Xu and Pinyan Lu were supported in part by Science and Technology Innovation 2030 - “The Next Generation of Artificial Intelligence” Major Project No. 2018AAA0100900. Additionally, Chenyang Xu received support from the National Natural Science Foundation of China (Grant No. 62302166), and the Dean’s Fund of Shanghai Key Laboratory of Trustworthy Computing, East China Normal University. Ruilong Zhang was supported by NSF grant CCF-1844890.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Lu, P., Xu, C., Zhang, R. (2024). Auction Design for Value Maximizers with Budget and Return-on-Spend Constraints. In: Garg, J., Klimm, M., Kong, Y. (eds) Web and Internet Economics. WINE 2023. Lecture Notes in Computer Science, vol 14413. Springer, Cham. https://doi.org/10.1007/978-3-031-48974-7_27
Download citation
DOI: https://doi.org/10.1007/978-3-031-48974-7_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-48973-0
Online ISBN: 978-3-031-48974-7
eBook Packages: Computer ScienceComputer Science (R0)