Fixed Price Approximability of the Optimal Gain from Trade
Fixed Price Approximability of the Optimal Gain from Trade
复制标题
贸易最优收益的固定价格近似性
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
S. Turchetta
中科院分区：
文献类型：
--
作者：
Riccardo Colini;P. Goldberg;B. D. Keijzer;S. Leonardi;S. Turchetta
双边贸易是一种基本的经济情景，由战略行动的买家和卖家(持有一件物品)组成，双方都持有该物品的估值，这些估值来自公开的分配。最近的研究表明，同时具有主导策略激励相容、强预算平衡和事后个体理性的唯一机制是固定价格机制，即由价格p参数表示的机制，当且仅当买方的估值至少为p，卖方的估值至多为p时，交易才会发生。交易收益(GFT)是应用一种机制所带来的福利增加。我们研究了通过固定价格机制可实现的GFT。我们在双边贸易环境和有多个I.I.D.的双向拍卖环境下都探讨了这个问题。单位需求买方和卖方。我们首先确定一种固定价格机制，它实现的GFT至少是最优GFT的2/r倍，其中r是卖方估值不超过买方估值的概率。这是McAfee之前的一个结果的扩展。随后，我们在渐近意义上改进了这一近似因子，证明了设定固定价格的更复杂的规则会导致GFT在最优的因子O(\log(1/r)\)内。这是渐近可能的最佳逼近系数。对于双向拍卖情形，我们给出了一个固定价格机制，该机制使所有的交易收益至少是最优值的(1-1-)倍，概率为1-2/e^{#T^2/2}，其中T是该机制的预期交易次数。这可以被解读为一个“大市场”的结果：随着市场变得更厚，达到了最大限度的效率。
Bilateral trade is a fundamental economic scenario comprising a strategically acting buyer and seller (holding an item), each holding valuations for the item, drawn from publicly known distributions. It was recently shown that the only mechanisms that are simultaneously dominant strategy incentive compatible, strongly budget balanced, and ex-post individually rational, are fixed price mechanisms, i.e., mechanisms that are parametrised by a price p, and trade occurs if and only if the valuation of the buyer is at least p and the valuation of the seller is at most p. The gain from trade (GFT) is the increase in welfare that results from applying a mechanism. We study the GFT achievable by fixed price mechanisms. We explore this question for both the bilateral trade setting and a double auction setting where there are multiple i.i.d. unit demand buyers and sellers. We first identify a fixed price mechanism that achieves a GFT of at least 2 / r times the optimum, where r is the probability that the seller’s valuation does not exceed that of the buyer’s valuation. This extends a previous result by McAfee. Subsequently, we improve this approximation factor in an asymptotic sense, by showing that a more sophisticated rule for setting the fixed price results in a GFT within a factor \(O(\log (1/r))\) of the optimum. This is asymptotically the best approximation factor possible. For the double auction setting, we present a fixed price mechanism that achieves for all \(\epsilon > 0\) a gain from trade of at least \((1-\epsilon )\) times the optimum with probability \(1 - 2/e^{\#T \epsilon ^2 /2}\), where \(\#T\) is the expected number of trades of the mechanism. This can be interpreted as a “large market” result: Full efficiency is achieved in the limit, as the market gets thicker.
影响因子：
1.2
作者：
Colini-Baldeschi, Riccardo;Goldberg, Paul W.;Keijzer, Bart de;Leonardi, Stefano;Roughgarden, Tim;Turchetta, Stefano
通讯作者：
Turchetta, Stefano
DOI：
10.4230/lipics.icalp.2017.47
发表时间：
2017-03
期刊：
ArXiv
影响因子：
--
作者：
Yiannis Giannakopoulos;E. Koutsoupias;Philip Lazos
通讯作者：
Yiannis Giannakopoulos;E. Koutsoupias;Philip Lazos