Online bilateral trade: learning the optimal policy in a stochastic environment

Bilateral trade models the interaction between a seller and a buyer with private valuations. Within the online learning framework introduced by Nicolò Cesa-Bianchi et Al., mechanisms post fixed prices sequentially and are evaluated against the best fixed price in hindsight. More recently, Bernasconi et Al. introduce a new notion of budget balance, together with a stronger benchmark: the best randomized pricing strategy over price pairs that satisfies global budget balance in expectation. While they prove that learning against such baseline is impossible in adversarial environments, this work shows that the distributional benchmark is attainable in stochastic environment, introducing a globally budget-balanced learning algorithm that achieves O(T^(3/4)) pseudo-regret against such distributional benchmark up to logarithmic factors.

Il bilateral trade modella l’interazione tra un venditore e un acquirente con valutazioni private. Nel framework di online learning introdotto da Nicolò Cesa-Bianchi et Al., i meccanismi pubblicano sequenzialmente prezzi fissi e vengono valutati rispetto al miglior prezzo fisso a posteriori. Più recentemente, Bernasconi et Al. introducono una nuova nozione di budget balance, insieme a un benchmark più forte: la migliore strategia di pricing randomizzata su coppie di prezzi che soddisfa il vincolo di global budget balance in aspettativa. Mentre dimostrano che imparare rispetto a tale riferimento è impossibile in ambienti avversari, questo lavoro mostra che il benchmark distribuzionale è conseguibile in ambienti stocastici, introducendo un algoritmo di apprendimento globalmente budget-balanced che ottiene pseudo-regret O(T^(3/4)) rispetto a tale benchmark distribuzionale a meno di fattori logaritmici.