Auctions Between Regret-Minimizing Agents

This paper deals with the following common type of scenario: several users engage in a repeated online auction, where each of them is assisted by a learning agent. A typical example is advertisers that compete for ad-slots: typically, each of these advertisers fills in his key parameters into some advertiser-facing website, and then this website's "agent" participates on the advertiser's behalf in a sequence of auctions for ad slots. Often, the auction's platform designer provides this agent as its advertiser-facing user interface. In cases where the platform's agent does not optimize sufficiently well for the advertiser (but rather, say, for the auctioneer) one would expect some other company to provide a better (for the advertiser) agent. A typical learning algorithm of this type will have at its core some regret-minimization algorithm [33, 9], such as multiplicative weights (see [2] and references therein) or some variant of fictitious play [12, 54], such as follow the perturbed leader [31, 40]. In particular, for ad auctions, there is empirical data showing that bids are largely consistent with no-regret learning [46, 52].