Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions
Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions
复制标题
组合拍卖中福利最大化的严格信息论下限
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
J. Vondrák
中科院分区：
文献类型：
--
作者：
V. Mirrokni;Michael Schapira;J. Vondrák
我们给出了组合拍卖中福利最大化问题的紧致信息论下界。在这个问题中，目标是在k个投标人之间以最大化投标人所分配物品的价值总和的方式来划分m个物品。投标人对由估值函数表示的物品有复杂的偏好，这些函数将价值分配给物品的所有子集。
我们研究了“黑箱”设置，在这种设置下，拍卖人可以通过Oracle访问投标人的估值功能。特别是，我们探索了众所周知的价值查询模型，在该模型中，对估值函数的允许查询是以项目子集的形式进行的，而回复是估值函数分配给该项目子集的价值。
我们考虑了不同类型的赋值函数：亚模、亚加性和超加性。对于这些类，已经表明，通过多项式(k和m)个值查询，可以分别获得1--1/e、1/√m和√m/m的逼近比。我们证明了这些逼近因子本质上是最好的：对于任何固定的ε>；0，子模估值的(1-1/e+ε)-逼近或次加性估值的1/m1/2-ε-逼近将需要指数级的许多值查询，而对于超加性估值的εm/m-逼近将需要超多项式的值查询数。
We provide tight information-theoretic lower bounds for the welfare maximization problem in combinatorial auctions. In this problem, the goal is to partition m items among k bidders in a way that maximizes the sum of bidders' values for their allocated items. Bidders have complex preferences over items expressed by valuation functions that assign values to all subsets of items.
We study the "black box" setting in which the auctioneer has oracle access to the valuation functions of the bidders. In particular, we explore the well-known value query model in which the permitted query to a valuation function is in the form of a subset of items, and the reply is the value assigned to that subset of items by the valuation function.
We consider different classes of valuation functions: submodular,subadditive, and superadditive. For these classes, it has been shown that one can achieve approximation ratios of 1 -- 1/e, 1/√m, and √ m/m, respectively, via a polynomial (in k and m) number of value queries. We prove that these approximation factors are essentially the best possible: For any fixed ε > 0, a (1--1/e + ε)-approximation for submodular valuations or an 1/m1/2-ε-approximation for subadditive valuations would require exponentially many value queries, and a log1+ε m/ m-approximation for superadditive valuations would require a superpolynomial number of value queries.