On characterizations of truthful mechanisms for combinatorial auctions and scheduling
On characterizations of truthful mechanisms for combinatorial auctions and scheduling
复制标题
关于组合拍卖和调度的真实机制的表征
DOI：
10.1145/1386790.1386798
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Mukund Sundararajan
中科院分区：
文献类型：
--
作者：
Shahar Dobzinski;Mukund Sundararajan
我们表征了两个多参数域中的真实机制。第一个表征表明，组合拍卖的每种机制与两个始终分配所有项目的亚基竞标者都是仿射的最大化器。第二个结果表明，每种真实的机器调度机制，用于两台无关的机器，这些机制产生了最小生产物的有限近似，必须独立于任务。也就是说，机制必须分别确定每个作业的分配。
特征提高了我们对这些多参数设置的理解，并就算法机理设计中核心问题的近似性具有新的含义。
We characterize truthful mechanisms in two multi-parameter domains. The first characterization shows that every mechanism for combinatorial auctions with two subadditive bidders that always allocates all items is an affine maximizer. The second result shows that every truthful machine scheduling mechanism for 2 unrelated machines that yields a finite approximation of the minimum makespan, must be task independent. That is, the mechanism must determine the allocation of each job separately.
The characterizations improve our understanding of these multi-parameter settings and have new implications regarding the approximability of central problems in algorithmic mechanism design.
DOI：
10.1007/978-3-642-04645-2
发表时间：
2009-07
期刊：
--
影响因子：
--
作者：
Yoram Bachrach;Edith Elkind;Reshef Meir;Dmitrii V. Pasechnik;Michael Zuckerman;Jörg Rothe;J. Rosenschein
通讯作者：
Yoram Bachrach;Edith Elkind;Reshef Meir;Dmitrii V. Pasechnik;Michael Zuckerman;Jörg Rothe;J. Rosenschein