Sponsored Search Auction Design Beyond Single Utility Maximization

Auction design for the modern advertising market has gained significant prominence in the field of game theory. With the recent rise of auto-bidding tools, an increasing number of advertisers in the market are utilizing these tools for auctions. The diverse array of auto-bidding tools has made auction design more challenging. Various types of bidders, such as quasi-linear utility maximizers and constrained value maximizers, coexist within this dynamic gaming environment. We study sponsored search auction design in such a mixed-bidder world and aim to design truthful mechanisms that maximize the total social welfare. To simultaneously capture the classical utility and the value-max utility, we introduce an allowance utility model. In this model, each bidder is endowed with an additional allowance parameter, signifying the threshold up to which the bidder can maintain a value-max strategy. The paper distinguishes two settings based on the accessibility of the allowance information. In the case where each bidder's allowance is public, we demonstrate the existence of a truthful mechanism achieving an approximation ratio of (1+) for any > 0. In the more challenging private allowance setting, we establish that a truthful mechanism can achieve a constant approximation. Further, we consider uniform-price auction design in large markets and give a truthful mechanism that sets a uniform price in a random manner and admits bounded approximation in expectation.