Frugality ratios and improved truthful mechanisms for vertex cover
Frugality ratios and improved truthful mechanisms for vertex cover
复制标题
DOI：
10.1145/1250910.1250959
复制
发表时间：
2006-06
期刊：
影响因子：
--
通讯作者：
Edith Elkind;L. A. Goldberg;P. Goldberg
中科院分区：
文献类型：
--
作者：
Edith Elkind;L. A. Goldberg;P. Goldberg
在集合系统拍卖中，有几个重叠的代理团队，并且有一个任务可以由这些团队中的任何一个团队完成。拍卖商的目标是雇佣一支团队，并支付尽可能低的费用。此设置的示例包括最短路径拍卖和顶点覆盖拍卖。最近，Karlin，Kempe和Tamir为这个问题引入了节俭比率的新定义。非正式地说，“节俭比率”是指某一机制的总支付金额与期望的支付范围之比。这一比率反映了该机制在多大程度上支付了相对于真实拍卖中被认为公平的成本的价格。本文针对顶点覆盖问题提出了一种新的真实多项式时间拍卖算法，并给出了它的节约率。我们证明了解的质量具有一个常数的最优因子，节俭比在一个常数因子的最佳可能的最坏情况界内；这是该问题具有这些性质的第一次拍卖。此外，我们还展示了如何在保持近似比的情况下将任何真实的拍卖转化为节俭的拍卖。此外，我们考虑了Karlin等人定义的两个自然修改，并分析了所得到的付款界限的性质，如单调性、计算难度和关于绘制-分解规则的稳健性。我们研究了不同的支付界限之间的关系，对于一般的集合系统和特定的集合系统拍卖，如路径拍卖和顶点覆盖拍卖。我们使用这些新的定义来证明我们的主要结果的顶点覆盖拍卖通过引导技术，这可能是独立的兴趣。
In set-system auctions, there are several overlapping teams of agents, and a task that can be completed by any of these teams. The auctioneer's goal is to hire a team and pay as little as possible. Examples of this setting include shortest-path auctions and vertex-cover auctions. Recently, Karlin, Kempe and Tamir introduced a new definition of frugality ratio for this problem. Informally, the "frugality ratio" is the ratio of the total payment of a mechanism to a desired payment bound. The ratio captures the extent to which the mechanism overpays, relative to perceived fair cost in a truthful auction. In this paper, we propose a new truthful polynomial-time auction for the vertex cover problem and bound its frugality ratio. We show that the solution quality is with a constant factor of optimal and the frugality ratio is within a constant factor of the best possible worst-case bound; this is the first auction for this problem to have these properties. Moreover, we show how to transform any truthful auction into a frugal one while preserving the approximation ratio. Also, we consider two natural modifications of the definition of Karlin et al., and we analyse the properties of the resulting payment bounds, such as monotonicity, computational hardness, and robustness with respect to the draw-resolution rule. We study the relationships between the different payment bounds, both for general set systems and for specific set-system auctions, such as path auctions and vertex-cover auctions. We use these new definitions in the proof of our main result for vertex-cover auctions via a boot-strapping technique, which may be of independent interest.