Statistical Seminar: Every Monday at 2:00 pm.
Time: 2:00 pm – 3:00 pm
Date: 18th September 2023
Place: 3001

Andrea CELLI (Bocconi University) – No-Regret Learning in Bilateral Trade via Global Budget Balance

Abstract:

Bilateral trade revolves around the challenge of facilitating transactions between two strategic agents — a seller and a buyer — both of whom have a private valuations for the item. We study the online version of the problem, in which at each time step a new seller and buyer arrive. The learner’s task is to set a price for each agent, without any knowledge about their valuations. The sequence of sellers and buyers is chosen by an oblivious adversary. In this setting, known negative results rule out the possibility of designing algorithms with sublinear regret when the learner has to guarantee budget balance for each iteration. We introduce the notion of global budget balance, which requires the agent to be budget balanced only over the entire time horizon. By requiring global budget balance, we provide the first no-regret algorithms for bilateral trade with adversarial inputs under various feedback models (full feedback and one-bit feedback). We complement these results with a nearly-matching lower bound

Link : https://zoom.us/j/95817279120?pwd=WWhPT1ZIRjFiOVF2VEQzNXJNdFZBQT09

Organizers:
Cristina BUTUCEA (CREST), Alexandre TSYBAKOV (CREST), Karim LOUNICI (CMAP) , Jaouad MOURTADA (CREST)
Sponsors:
CREST-CMAP