Taming the Communication and Computation Complexity of Combinatorial Auctions: The FUEL Bid Language
Taming the Communication and Computation Complexity of Combinatorial Auctions: The FUEL Bid Language
复制标题
DOI：
10.1287/mnsc.2022.4465
复制
发表时间：
2022-06-15
影响因子：
5.4
通讯作者：
Schwarza, Gregor
中科院分区：
文献类型：
--
作者：
Bichler, Martin;Milgrom, Paul;Schwarza, Gregor
组合拍卖已经被广泛应用于在复杂的投标人偏好的情况下分配多个物品。枚举异或（XOR）投标语言是事实上的标准投标语言的频谱拍卖和其他应用程序，尽管困难，在较大的拍卖，枚举所有相关的包或解决由此产生的NP-难赢家确定问题。我们介绍了灵活使用和有效的许可（燃料）投标语言，这是提出了无线电频谱拍卖，以减轻通信和计算相比，基于XOR的拍卖。我们将由此产生的分配问题建模为整数规划，讨论计算复杂性，并进行了一系列广泛的计算实验，结果表明，燃料投标语言的赢家确定问题可以在平均不到半小时的时间内可靠地解决大型实际问题实例。相比之下，使用XOR出价语言的拍卖即使对于小得多的问题也会很快变得棘手。我们比较密封投标燃料拍卖密封投标与XOR投标语言和同步时钟拍卖。密封投标与异或出价语言的拍卖会招致显着的福利损失，因为遗漏的出价问题和计算的难度，同步时钟拍卖会导致显着低于燃料的效率，因为曝光问题。
Combinatorial auctions have found widespread application for allocating multiple items in the presence of complex bidder preferences. The enumerative exclusive OR (XOR) bid language is the de facto standard bid language for spectrum auctions and other applications, despite the difficulties, in larger auctions, of enumerating all the relevant packages or solving the resulting NP-hard winner determination problem. We introduce the flexible use and efficient licensing (FUEL) bid language, which was proposed for radio spectrum auctions to ease both communications and computations compared with XORbased auctions. We model the resulting allocation problem as an integer program, discuss computational complexity, and conduct an extensive set of computational experiments, showing that the winner determination problem of the FUEL bid language can be solved reliably for large realistic-sized problem instances in less than half an hour on average. In contrast, auctions with an XOR bid language quickly become intractable even for much smaller problemsizes. We compare a sealed-bid FUEL auction to a sealed-bid auction with an XOR bid language and to a simultaneous clock auction. The sealed-bid auction with an XOR bid language incurs significant welfare losses because of the missing bids problem and computational hardness, the simultaneous clock auction leads to a substantially lower efficiency than FUEL because of the exposure problem.