6 papers · 1 filter
Optimal Online Stochastic Matching
Paul Duetting, Michal Feldman, Mathieu Molina
We resolve the problem of unweighted online stochastic matching with a known arrival law by establishing its optimal competitive ratio. For Poisson arrivals, we achieve $1-e/e^e\ap…
Settling the Complexity Landscape of Multi-Agent Contracts with Binary Actions
Michal Feldman, Maya Schlesinger, Shay Shani
We study the computational complexity of optimal contract design in the multi-agent binary-action model, focusing on gross-substitutes reward functions and related classes. While a…
Fair Prophets
Paul Duetting, Michal Feldman, Mathieu Molina
We initiate the study of -fair prophet inequalities. This interpolates between utilitarian welfare , Nash welfare , and Rawlsian max-min fairness . G…
Epistemic Pairwise Maximin Share
Michal Feldman, Amos Fiat, Yael Nissan +1
We introduce epistemic pairwise maximin share (EPMMS), a new fairness notion for fair division of indivisible goods. Two fundamental notions in this setting are envy-freeness up to…
Combinatorial Contracts Through Demand Types
Elizabeth Baldwin, Paul Duetting, Michal Feldman +1
In the combinatorial action model of contract design, a principal delegates a complex project to an agent, incentivizing a subset of actions from a ground set of actions, via a…
Equal-Pay Contracts
Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka +1
We study multi-agent contract design, where a principal incentivizes a team of agents to take costly actions that jointly determine the project success via a combinatorial reward f…