First-price path auctions
First-price path auctions
复制标题
DOI：
10.1145/1064009.1064031
复制
发表时间：
2005-06
期刊：
影响因子：
--
通讯作者：
Nicole Immorlica;David R Karger;E. Nikolova;Rahul Sami
中科院分区：
文献类型：
--
作者：
Nicole Immorlica;David R Karger;E. Nikolova;Rahul Sami
研究了图中给定节点间拍卖流的首价拍卖机制。首价拍卖是指获胜路径的链接获得出价的任何拍卖；设计人员可以灵活地指定剩余的细节。我们假设边缘是具有固定能力和成本的独立个体，它们的目标是利润最大化。我们描述了首价拍卖的所有强ε-纳什均衡，并表明总支付不会显著大于，而通常小于众所周知的优势策略维克里-克拉克-格罗夫斯机制。然后，我们提出了首价拍卖的随机化版本，其均衡条件可以放宽为ε-纳什均衡。接下来我们考虑一个需求量不确定的模型，但它的概率分布是已知的。对于这个模型，我们证明了一个简单的事前第一价格拍卖可能不存在ε-纳什均衡。然后，我们提出了一个具有ε-Nash均衡的改进的2参数出价机制。对于这个2参数机制的随机化版本，我们描述了所有eNE的集合，并证明了任何eNE中总支付的界。
We study first-price auction mechanisms for auctioning flow between given nodes in a graph. A first-price auction is any auction in which links on winning paths are paid their bid amount; the designer has flexibility in specifying remaining details. We assume edges are independent agents with fixed capacities and costs, and their objective is to maximize their profit. We characterize all strong ε-Nash equilibria of a first-price auction, and show that the total payment is never significantly more than, and often less than, the well known dominant strategy Vickrey-Clark-Groves mechanism. We then present a randomized version of the first-price auction for which the equilibrium condition can be relaxed to ε-Nash equilibrium. We next consider a model in which the amount of demand is uncertain, but its probability distribution is known. For this model, we show that a simple ex ante first-price auction may not have any ε-Nash equilibria. We then present a modified mechanism with 2-parameter bids which does have an ε-Nash equilibrium. For a randomized version of this 2-parameter mechanism we characterize the set of all eNEs and prove a bound on the total payment in any eNE.