The price of imperfect competition for a spanning network

• 成果类型: Article
• 署名作者: Moulin, Herve; Velez, Rodrigo A.
• 署名单位: Rice University; Texas A&M University System; Texas A&M University College Station
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2013.03.012
• 发表日期: 2013
• 页码: 11-26
• 关键词: Algorithmic mechanism design; Worst case scenario equilibrium analysis; Frugality; Minimum cost spanning tree problem; Price of imperfect competition

摘要

A buyer procures a network to span a given set of nodes; each seller bids to supply certain edges, then the buyer purchases a minimal cost spanning tree. An efficient tree is constructed in any equilibrium of the Bertrand game. We evaluate the price of imperfect competition (PIC), namely the ratio of the total price that could be charged to the buyer in some equilibrium, to the true minimal cost. If each seller can only bid for a single edge and costs satisfy the triangle inequality, we show that the PIC is at most 2 for an odd number of nodes, and at most 2n-1/n-2 for an even number n of nodes. Surprisingly, this worst case ratio does not improve when the cost pattern is ultrametric (a much more demanding substitutability requirement), although the overhead is much lower on average under typical probabilistic assumptions. But the PLC increases swiftly when sellers can only provide a subset of all edges. (C) 2013 Elsevier Inc. All rights reserved.