Advertisement
Published in:
2012 | OriginalPaper | Chapter
Commodity Auctions and Frugality Ratios
Authors : Paul W. Goldberg, Antony McCabe
Published in: Algorithmic Game Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study set-system auctions whereby a single buyer wants to purchase
Q
items of some commodity. There are multiple sellers, each of whom has some known number of items, and a private cost for supplying those items. Thus a “feasible set” of sellers (a set that is able to comprise the winning bidders) is any set of sellers whose total quantity sums to at least
Q
. We show that, even in a limited special case, VCG has a
frugality ratio
of at least
n
− 1 (with respect to the NTUmin benchmark) and that this matches the upper bound for any set-system auction. We show a lower bound on the frugality of any truthful mechanism of
$\sqrt{Q}$
in this setting and give a truthful mechanism with a frugality ratio of
$2\sqrt{Q}$
. However, we show that similar types of ‘scaling’ mechanism, in the general (integer) case, give a frugality ratio of at least
${{4Qe^{-2}}\over{{\rm In}^2Q}}$
.