Characterizing Truthful Multi-Armed Bandit Mechanisms

Details Characterizing Truthful Multi-Armed Bandit Mechanisms Characterizing Truthful Multi-Armed Bandit Mechanisms

2008-12-12

arxiv.org/abs/0812.2291v5

Computer Science

Data Structures and Algorithms

The conference version of this paper will appear in ACM EC 2009

Scientific paper

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 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.

Affiliated with

Also associated with

No associations

Rating

Characterizing Truthful Multi-Armed Bandit Mechanisms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Characterizing Truthful Multi-Armed Bandit Mechanisms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Characterizing Truthful Multi-Armed Bandit Mechanisms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-609400