English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Bilateral trade revolves around the challenge of facilitating transactionsbetween two strategic agents -- a seller and a buyer -- both of whom have aprivate valuations for the item. We study the online version of the problem, inwhich at each time step a new seller and buyer arrive. The learner's task is toset a price for each agent, without any knowledge about their valuations. Thesequence of sellers and buyers is chosen by an oblivious adversary. In thissetting, known negative results rule out the possibility of designingalgorithms with sublinear regret when the learner has to guarantee budgetbalance for each iteration. In this paper, we introduce the notion of globalbudget balance, which requires the agent to be budget balance only over theentire time horizon. By requiring global budget balance, we provide the firstno-regret algorithms for bilateral trade with adversarial inputs under variousfeedback models. First, we show that in the full-feedback model the learner canguarantee $\tilde{O}(\sqrt{T})$ regret against the best fixed prices inhindsight, which is order-wise optimal. Then, in the case of partial feedbackmodels, we provide an algorithm guaranteeing a $\tilde{O}(T^{3/4})$ regretupper bound with one-bit feedback, which we complement with a nearly-matchinglower bound. Finally, we investigate how these results vary when measuringregret using an alternative benchmark.

No-Regret Learning in Bilateral Trade via Global Budget Balance