.png){kind=icon}
返回
Algorithm for optimal winner determination in combinatorial auctions
.png){kind=icon}
OA
AI
DOI：10.1016/S0004-3702(01)00159-X.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Combinatorial auctions, that is, auctions where bidders can bid on combinations of items, tend to lead to more efficient allocations than traditional auction mechanisms in multi-item auctions where the agents' valuations of the items are not additive. However, determining the winners so as to maximize revenue is NP-complete. First, we analyze existing approaches for tackling this problem: exhaustive enumeration, dynamic programming, and restricting the allowable combinations. Second, we study the possibility of approximate winner determination, proving inapproximability in the general case, and discussing approximation algorithms for special cases. We then present our search algorithm for optimal winner determination. Experiments are shown on several bid distributions which we introduce. The algorithm allows combinatorial auctions to scale up to significantly larger numbers of items and bids than prior approaches to optimal winner determination by capitalizing on the fact that the space of bids is sparsely populated in practice. The algorithm does this by provably sufficient selective generation of children in the search tree, by using a secondary search for fast child generation, by using heuristics that are admissible and optimized for speed, and by preprocessing the search space in four ways. Incremental winner determination and quote computation techniques are presented. We show that basic combinatorial auctions only allow bidders to express complementarity of items. We then introduce two fully expressive bidding languages, called XOR-bids and OR-of-XORs, with which bidders can express general preferences (both complementarity and substitutability). The latter language is more concise. We show how these languages enable the use of the Vickrey-Clarke-Groves mechanism to construct a combinatorial auction where each bidder's dominant strategy is to bid truthfully. Finally, we extend our search algorithm and preprocessors to handle these languages as well as arbitrary XOR-constraints between bids. (C) 2001 Elsevier Science B.V. All rights reserved.
Keyword:
auction
combinatorial auction
multi-item auction
multi-object auction
bidding with synergies
winner determination
multiagent systems
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
13.9
论文数:
6.1K
被引数:
1.9W
机构
暂无机构信息
引用论文
.png){kind=icon}
查看更多内容