競合的オークションに対する平均化

概要

論文の詳細を見る
We study digital-goods auctions for items in unlimited supply introduced by Goldberg, Hartline and Wright. Since no deterministic algorithms are competitive for this class of auctions, one of the central research issues is how to obtain a nice probabilistic distribution over truthful algorithms. In this paper, we introduce a rather systematic approach to this goal: Consider for example the Sampling Cost Share (SCS) auction. It is well known that SCS works well if the the current bid vector produces many winners against F^<(2)>, the standard benchmark algorithm for competitive analysis. In fact, its competitive ratio is approaching to 2.0 as k (=the number of F^<(2)> winners) grows. On the other hand, its competitive ratio becomes as bad as 4.0 for k=2. Our new approach is to develop a sequence of similar cost-share type algorithms, DCS_k, which work well for small k. Now we choose a sufficiently large constant N and run DCS_1, DCS_2, ..., DCS_N and SCS with probabilities p_1, p_2, ..., p_N and q, respectively. It should be noted that we can use LP to obtain optimal p_1, p_2,..., p_N and q. By this averaging method, we can improve the competitive ratio of SCS from 4.0 to 3.531 and that of the currently best Aggregated 〓3 algorithm due to Hartline and McGrew from 3.243 to 3.119.
2010-04-15