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 $\alpha$-regret for any $\alpha<2$, (b) but with full feedback sublinear $2$-regret is achievable (c) with a single price and partial feedback one cannot get sublinear $\alpha$ regret for any constant $\alpha$ (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.
翻译:我们研究的是相继的双边贸易,其中买卖双方的估价完全武断(即由对手确定)。卖主和买主是具有私利估价的战略代理人,目标是设计一种机制,在激励兼容、个别合理和预算平衡的情况下,最大限度地提高效率(或从贸易中得益),同时保持激励兼容、个别合理和预算平衡。在本文件中,我们考虑的是比社会福利更难估计的贸易收益。我们考虑的是各种反馈设想,并区分机制确定一个价格和它可以为买主和卖主提出不同价格的情况。我们就不同设想的区别展示出若干令人惊讶的结果。我们特别表明:(a) 任何1美元不可能达到次级线性alpha$-regret,(或从贸易中得益),但如果完全反馈,2美元-regret(c),单价和部分反馈是无法为任何恒定美元(d)的亚线性alpha$(alpha)的遗憾。然而,即使一比方的反馈也公布了两种价格,达到次级线2美元-regret) 完全分解。(e)