We consider a multi-round auction setting motivated by pay-per-click auctions for Internet advertising. In each round the auctioneer selects an advertiser and shows her ad, which is then either clicked or not. An advertiser derives value from clicks; the value of a click is her private information. Initially, neither the auctioneer nor the advertisers have any information about the likelihood of clicks on the advertisements. The auctioneer's goal is to design a (dominant strategies) truthful mechanism that (approximately) maximizes the social welfare. If the advertisers bid their true private values, our problem is equivalent to the multi-armed bandit problem, and thus can be viewed as a strategic version of the latter. In particular, for both problems the quality of an algorithm can be characterized by regret, the difference in social welfare between the algorithm and the benchmark which always selects the same "best" advertisement. We investigate how the design of multi-armed bandit algorithms is affected by the restriction that the resulting mechanism must be truthful. We find that deterministic truthful mechanisms have certain strong structural properties -essentially, they must separate exploration from exploitation -and they incur much higher regret than the optimal multi-armed bandit algorithms. Moreover, we provide a truthful mechanism which (essentially) matches our lower bound on regret. This is a full version of a conference paper published in 10th ACM Conf. on Electronic Commerce (EC), 2009. Apart from the revised presentation, this version is updated to reflect the follow-up work [9, 56, 22, 48] and the current snapshot of open questions. † This research was done while Y. Sharma was a student at Cornell University and an intern at Microsoft Research Silicon Valley. The first notable necessary property of a truthful MAB mechanism is a much stronger version of monotonicity which we call "pointwise monotonicity": Definition 1.1. A click realization consists of click information for all agents and all rounds: it specifies whether a given agent receives a click if it is selected in a given round. 2 An allocation rule is pointwise monotone if for each click realization, each bid profile and each round, if an agent is selected at this round, then she is also selected after increasing her bid (fixing everything else). We first consider the case of two agents and show that truthful MAB mechanisms must have a strict separation between exploration and exploitation, in the following sense. A crucial feature of exploration is the ability to influence the allocation in forthcoming rounds. To make this point more concrete, we call a round t influential for a given click realization, with influenced agent j, if for some bid profile changing the click realization for this round can affect the allocation of agent j in some future round. We show that in any influential round, the allocation can not depend on the bids. Thus, we show that influential rounds are essentially useless for exploitation. A is called exploration-separated if for any click realization, the allocation in any influential round does not depend on the bids. In our model, agents derive value from clicks. In particular, an agent with zero value per click receives no value. We focus on mechanisms in which a truthfully bidding agent with zero value-per-click pays exactly zero; we call such mechanisms normalized. Among truthful single-parameter mechanisms, normalized mechanisms are precisely the ones that satisfy two desirable properties: voluntary participation (truthfully bidding agents never lose from participating), and no positive transfers (advertisers are charged, not paid). We also make a mild assumption that an allocation rule is scale-free: invariant under multiplying all bids by the same positive number, i.e. does not depend on the choice of the currency unit. Many MAB algorithms from prior work can be easily converted into scale-free MAB allocation rules via some generic ways to incorporate bids into algorithms' specification. 3 We are now ready to present our main structural result for two agents. Theorem 1.3. Consider the MAB mechanism design problemwith two agents. Let A be a non-degenerate, 4 deterministic, scale-free allocation rule. Then a mechanism (A, P) is normalized and truthful for some payment rule P if and only if A is pointwise monotone and exploration-separated. The case of more than two agents requires slightly more refined notions. Definition 1.4. For a given realization and bid profile, a round is secured from an agent if that agent cannot change the allocation at that round by increasing his bid. A deterministic MAB allocation rule is called weakly separated if for every click realization and bid profile, if a round is influential for this realization and bid profile, then it is secured from every agent that this round influences.
Babaioff et al. REF provide a characterization of truthful MAB mechanisms, wherein the objective is to maximize social welfare.
Characterizing Truthful Multi-armed Bandit Mechanisms
SIAM Journal on Computing
SIAM Journal on Computing
Computer Science Mathematics