Auto-bidding with Budget and ROI Constrained Buyers

Auto-bidding with Budget and ROI Constrained Buyers

Xiaodong Liu, Weiran Shen

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 2817-2825. https://doi.org/10.24963/ijcai.2023/314

In online advertising markets, an increasing number of advertisers are adopting auto-bidders to buy advertising slots. This tool simplifies the process of optimizing bids based on various financial constraints. In our study, we focus on second-price auctions where bidders have both private budget and private ROI (return on investment) constraints. We formulate the auto-bidding system design problem as a mathematical program and analyze the auto-bidders' bidding strategy under such constraints. We demonstrate that our design ensures truthfulness, i.e., among all pure and mixed strategies, always reporting the truthful budget and ROI is an optimal strategy for the bidders. Although the program is non-convex, we provide a fast algorithm to compute the optimal bidding strategy for the bidders based on our analysis. We also study the welfare and provide a lower bound for the PoA (price of anarchy). Moreover, we prove that if all bidders utilize our auto-bidding system, a Bayesian Nash equilibrium exists. We provide a sufficient condition under which the iterated best response process converges to such an equilibrium. Finally, we conduct extensive experiments to empirically evaluate the effectiveness of our design.
Keywords:
Game Theory and Economic Paradigms: GTEP: Auctions and market-based systems
Game Theory and Economic Paradigms: GTEP: Mechanism design