Core-competitive Auctions
Core-competitive Auctions
复制标题
核心竞争力拍卖
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
R. Leme
中科院分区：
文献类型：
--
作者：
G. Goel;M. Khani;R. Leme
著名的 VCG 拍卖的主要缺点之一是其收入较低（或为零），即使代理商对商品具有很高的价值，并且竞争结果会产生可观的收入。竞争性结果是指卖方和一部分买方不可能通过背叛和谈判获得为自己带来更高回报的结果来“阻止”拍卖。这对应于合作博弈论中众所周知的核心概念。特别是，当所销售的商品具有互补性时，VCG 收入就不具有竞争力。互补品存在于许多应用领域，包括频谱、采购和广告拍卖。在尝试为这些设置设计拍卖时，VCG 拍卖缺乏良好的收入构成了真正的障碍。鉴于这些应用领域的重要性，研究人员一直在寻找替代的拍卖设计。来自这一思路的一个重要研究方向是核心选择拍卖的设计（参见 Ausubel 和 Milgrom、Day 和 Milgrom、Day 和 Cramton、Ausubel 和 Baranov）。核心选择拍卖是组合拍卖，即使商品是互补的，其结果也能实现有竞争力的价格。虽然这些拍卖设计已在各种场景中实际应用，并以具有良好的收益特性而闻名，但它们缺乏 VCG 拍卖所需的激励相容性。这里的瓶颈是不可能的结果，表明没有拍卖可以同时实现有竞争力的价格（核心结果）和激励相容性。在本文中，我们试图通过提出以下自然问题来克服上述不可能的结果：是否有可能设计一种与激励相容的拍卖，其收入与竞争结果相当（即使更少）？为此，我们定义了核心竞争拍卖的概念。如果激励兼容拍卖的收入至少是核心结果最低收入的 1/α，我们就说它具有 α 核心竞争性。我们研究了互联网广告中最常见的互补商品设置之一，即文本和图像设置。在此设置中，有一个广告位可以填充单个图像广告或 k 个文本广告。我们为文本和图像设置设计了 O(ln ln k) 核心竞争随机拍卖和 O(√ln k) 竞争确定性拍卖。我们还表明这两个因素都很紧张。
One of the major drawbacks of the celebrated VCG auction is its low (or zero) revenue even when the agents have high value for the goods and a competitive outcome would have generated a significant revenue. A competitive outcome is one for which it is impossible for the seller and a subset of buyers to 'block' the auction by defecting and negotiating an outcome with higher payoffs for themselves. This corresponds to the well-known concept of core in cooperative game theory. In particular, VCG revenue is known to be not competitive when the goods being sold have complementarities. Complementary goods are present in many application domains including spectrum, procurement, and ad auctions. The absence of good revenue from VCG auction poses a real hurdle when trying to design auctions for these settings. Given the importance of these application domains, researchers have looked for alternate auction designs. One important research direction that has come from this line of thinking is that of the design of core-selecting auctions (See Ausubel and Milgrom, Day and Milgrom, Day and Cramton, Ausubel and Baranov). Core-selecting auctions are combinatorial auctions whose outcome implements competitive prices even when the goods are complements. While these auction designs have been implemented in practice in various scenarios and are known for having good revenue properties, they lack the desired incentive-compatibility property of the VCG auction. A bottleneck here is an impossibility result showing that there is no auction that simultaneously achieves competitive prices (a core outcome) and incentive-compatibility. In this paper we try to overcome the above impossibility result by asking the following natural question: is it possible to design an incentive-compatible auction whose revenue is comparable (even if less) to a competitive outcome? Towards this, we define a notion of core-competitive auctions. We say that an incentive-compatible auction is α-core-competitive if its revenue is at least 1/α fraction of the minimum revenue of a core-outcome. We study one of the most commonly occurring setting in Internet advertisement with complementary goods, namely that of the Text-and-Image setting. In this setting, there is an ad slot which can be filled with either a single image ad or k text ads. We design an O(ln ln k) core-competitive randomized auction and an O(√ln k) competitive deterministic auction for the Text-and-Image setting. We also show that both factors are tight.
DOI：
10.1145/1250910.1250959
发表时间：
2006-06
期刊：
ArXiv
影响因子：
--
作者：
Edith Elkind;L. A. Goldberg;P. Goldberg
通讯作者：
Edith Elkind;L. A. Goldberg;P. Goldberg