图 书 馆
强盗设置的战略考量-在线广告拍卖的真实价格Strategic Considerations in Bandit Settings - The Price of Truthfulness in Online Ad Auctions |
|
| 课程网址: | http://videolectures.net/icml09_kakade_itscbs/ |
| 主讲教师: | Kakade Sham M |
| 开课单位: | 微软公司 |
| 开课时间: | 2009-08-26 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Research at the intersection of machine learning and economics has flourished in recent years due to the realization that many technological systems (such as the internet) are better understood and managed when they are viewed as economic systems rather than just merely technological ones. In particular, there is much recent work on understanding learning algorithms and models in settings where the strategic considerations of the participants must be taken into account (e.g. spam detection). This talk will examine the this broader issue in the setting of online ad-auctions (in particular "pay-per-click" auctions, where advertisers are charged only those rounds when their ad is clicked on). Designing such an auction faces the classic explore/exploit dilemma: while gathering information about the "click-through-rates" of advertisers, the mechanism may loose revenue; however, this gleaned information may prove valuable in the future for a more profitable allocation. In this sense, such mechanisms are prime candidates to be designed using multi-armed bandit techniques. However, a naive application of multi-armed bandit algorithms would not take into account the strategic considerations of the players - players might manipulate their bids (which determine the auction's revenue) in a way as to maximize their own utility. Hence, we consider the natural restriction that the auction be truthful. This work sharply characterizes what regret is achievable, under this truthful restriction. Interestingly, we show that this restriction imposes statistical limits on the achievable regret - that it is Theta(T^2/3), while for traditional bandit algorithms (without this truthful restriction) the achievable regret is O(T^1/2) (where T is the number of rounds). We term the extra T^1/6 factor, the "price of truthfulness". |
| 关 键 词: | 机器学习; 经济学; 强盗技术 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-04-15：chenxin |
| 阅读次数: | 54 |