10 papers
Contextual Online Bilateral Trade
Romain Cosson, Federico Fusco, Anupam Gupta +3
We study repeated bilateral trade when the valuations of the sellers and the buyers are contextual. More precisely, the agents' valuations are given by the inner product of a conte…
Anonymous Contracts
Johannes Brustle, Paul Duetting, Stefano Leonardi +2
We study a multi-agent contracting problem where agents exert costly effort to achieve individually observable binary outcomes. While the principal can theoretically extract the fu…
Multicalibration Yields Better Matchings
Riccardo Colini Baldeschi, Simone Di Gregorio, Simone Fioravanti +9
Consider the problem of finding the best matching in a weighted graph where we only have access to predictions of the actual stochastic weights, based on an underlying context. If…
Online Learning in the Random Order Model
Martino Bernasconi, Andrea Celli, Riccardo Colini-Baldeschi +3
In the random-order model for online learning, the sequence of losses is chosen upfront by an adversary and presented to the learner after a random permutation. Any random-order in…
Online Learning with Sublinear Best-Action Queries
Matteo Russo, Andrea Celli, Riccardo Colini Baldeschi +5
In online learning, a decision maker repeatedly selects one of a set of actions, with the goal of minimizing the overall loss incurred. Following the recent line of research on alg…
Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment
Tomer Ezra, Stefano Leonardi, Michał Pawłowski +2
The online joint replenishment problem (JRP) is a fundamental problem in the area of online problems with delay. Over the last decade, several works have studied generalizations of…
Contract Design Beyond Hidden-Actions
Tomer Ezra, Stefano Leonardi, Matteo Russo
In the classical principal-agent hidden-action contract model, a principal delegates the execution of a costly task to an agent. In order to complete the task, the agent chooses an…
Fair Division with Interdependent Values
Georgios Birmpas, Tomer Ezra, Stefano Leonardi +1
We introduce the study of designing allocation mechanisms for fairly allocating indivisible goods in settings with interdependent valuation functions. In our setting, there is a se…
Fully Dynamic Online Selection through Online Contention Resolution Schemes
Vashist Avadhanula, Andrea Celli, Riccardo Colini-Baldeschi +2
We study fully dynamic online selection problems in an adversarial/stochastic setting that includes Bayesian online selection, prophet inequalities, posted price mechanisms, and st…
Prophet Inequalities via the Expected Competitive Ratio
Tomer Ezra, Stefano Leonardi, Rebecca Reiffenhäuser +2
We consider prophet inequalities under downward-closed constraints. In this problem, a decision-maker makes immediate and irrevocable choices on arriving elements, subject to const…