论文标题
$α$ regret分析对抗双边贸易
An $α$-regret analysis of Adversarial Bilateral Trade
论文作者
论文摘要
我们研究顺序双边贸易，卖方和买家的估值是完全任意的（即由对手决定的）。卖方和买家是具有私人估值的战略代理商，目标是设计一种机制，可以最大程度地提高效率（或从贸易中获得），同时又是兼容，个人合理和预算平衡的机制。在本文中，我们认为从贸易中获得的收益比社会福利要困难得多。 我们考虑各种反馈方案，并区分机制发布一个价格以及何时可以为买卖双方发布不同价格的情况。我们对不同场景之间的分离显示了几个令人惊讶的结果。特别是我们表明，（a）对于任何$α<2 $，（b）来说，无法实现sublinear $α$ regret，但使用全额反馈sublinear $ 2 $ - regret是可以实现的（c），单个价格和部分反馈都无法获得sublinear $α$的遗憾，因为任何常数的$α$（d）$α$（d），即$ 2 $ - regret和（e）在全部反馈和部分反馈之间的$ 2 $ regret范围中有一个可证明的分离。
We study sequential bilateral trade where sellers and buyers valuations are completely arbitrary (i.e., determined by an adversary). Sellers and buyers are strategic agents with private valuations for the good and the goal is to design a mechanism that maximizes efficiency (or gain from trade) while being incentive compatible, individually rational and budget balanced. In this paper we consider gain from trade which is harder to approximate than social welfare. We consider a variety of feedback scenarios and distinguish the cases where the mechanism posts one price and when it can post different prices for buyer and seller. We show several surprising results about the separation between the different scenarios. In particular we show that (a) it is impossible to achieve sublinear $α$-regret for any $α<2$, (b) but with full feedback sublinear $2$-regret is achievable (c) with a single price and partial feedback one cannot get sublinear $α$ regret for any constant $α$ (d) nevertheless, posting two prices even with one-bit feedback achieves sublinear $2$-regret, and (e) there is a provable separation in the $2$-regret bounds between full and partial feedback.
