On the Efficiency and Equilibria of Rich Ads

On the Efficiency and Equilibria of Rich Ads

MohammadAmin Ghiasi, MohammadTaghi Hajiaghayi, S├ębastien Lahaie, Hadi Yami

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 301-307. https://doi.org/10.24963/ijcai.2019/43

Search ads have evolved in recent years from simple text formats to rich ads that allow deep site links, rating, images and videos. In this paper, we consider a model where several slots are available on the search results page, as in the classic generalized second-price auction (GSP), but now a bidder can be allocated several consecutive slots, which are interpreted as a rich ad. As in the GSP, each bidder submits a bid-per-click, but the click-through rate (CTR) function is generalized from a simple CTR for each slot to a general CTR function over sets of consecutive slots. We study allocation and pricing in this model under subadditive and fractionally subadditive CTRs. We design and analyze a constant-factor approximation algorithm for the efficient allocation problem under fractionally subadditive CTRs, and a log-approximation algorithm for the subadditive case. Building on these results, we show that approximate competitive equilibrium prices exist and can be computed for subadditive and fractionally subadditive CTRs, with the same guarantees as for allocation.
Keywords:
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems
Agent-based and Multi-agent Systems: Resource Allocation