Deferred-Acceptance Auctions for Multiple Levels of Service
Deferred-Acceptance Auctions for Multiple Levels of Service
复制标题
多级别服务的延期接受拍卖
DOI：
10.1145/3033274.3085142
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Tim Roughgarden
中科院分区：
文献类型：
--
作者：
Vasilis Gkatzelis;E. Markakis;Tim Roughgarden
延期感知能力（DA）拍卖是基于向后怪异算法并具有许多非凡的激励属性的机制，包括作为明显的策略范围的上升拍卖。 DA拍卖上的所有现有工作仅考虑二进制单参数问题，每个投标人``赢家''或``失去''。大约在许多基本机制设计问题上，福利最大化的DA拍卖：多单位拍卖，多甲状管束缚的问题或多个背包约束以及调度作业以最大程度地减少其总加权完成时间的问题。我们的结果需要设计具有良好近似保证的新型后退绿色算法。
Deferred-acceptance (DA) auctions} are mechanisms that are based on backward-greedy algorithms and possess a number of remarkable incentive properties, including implementation as an obviously-strategyproof ascending auction. All existing work on DA auctions considers only binary single-parameter problems, where each bidder either ``wins'' or ``loses.'' This paper generalizes the DA auction framework to non-binary settings, and applies this generalized framework to obtain approximately welfare-maximizing DA auctions for a number of basic mechanism design problems: multiunit auctions, problems with polymatroid constraints or multiple knapsack constraints, and the problem of scheduling jobs to minimize their total weighted completion time. Our results require the design of novel backward-greedy algorithms with good approximation guarantees.