Stepwise randomized combinatorial auctions achieve revenue monotonicity
Stepwise randomized combinatorial auctions achieve revenue monotonicity
复制标题
逐步随机组合拍卖实现收入单调性
DOI：
10.1137/1.9781611973068.81
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Kevin Leyton
中科院分区：
文献类型：
--
作者：
Baharak Rastegari;A. Condon;Kevin Leyton
在使用VCG的组合拍卖中，卖家有时可以通过放弃竞标者来增加收入（例如b[5]）。在我们之前的工作b[26]中，我们表明，这种“收入单调性”的失败发生在极其广泛的确定性策略组合拍卖机制下，即使竞标者“已知单一”的估值。在这项工作中，我们考虑的问题是，这些竞标者的收入单调，策略证明机制是否可以在更广泛的随机机制类别中找到。我们展示了——令人惊讶的是——这样的机制确实存在，展示了它们是如何构建的，并考虑了在多项式时间内实现它们的算法技术。
In combinatorial auctions that use VCG, a seller can sometimes increase revenue by dropping bidders (see e.g. [5]). In our previous work [26], we showed that such failures of "revenue monotonicity" occur under an extremely broad range of deterministic strategyproof combinatorial auction mechanisms, even when bidders have "known single-minded" valuations. In this work we consider the question of whether revenue monotonic, strategyproof mechanisms for such bidders can be found in the broader class of randomized mechanisms. We demonstrate that---surprisingly- such mechanisms do exist, show how they can be constructed, and consider algorithmic techniques for implementing them in polynomial time.
More formally, we characterize a class of randomized mechanisms defined for known single-minded bidders that are strategyproof and revenue monotonic, and furthermore satisfy some other desirable properties, namely participation, consumer sovereignty and maximality, representing the mechanism as a solution to a quadratically constrained linear program (QCLP). We prove that the QCLP is always feasible (i.e., for all bidder valuations) and give its solution analytically. Furthermore, we give an algorithm for running such a mechanism in time polynomial in the number of bidders and goods; this is interesting because constructing an instance of such mechanisms from our QCLP formulation in a naive way can require exponential time.
影响因子：
0.6
作者：
Robert W. Day;Paul R. Milgrom
通讯作者：
Robert W. Day;Paul R. Milgrom