12 papers
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…
One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts
Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka +1
We study multi-agent contract design with combinatorial actions, under budget constraints, and for a broad class of objective functions, including profit (principal's utility), rew…
Ultra Efficient Contracts: Pushing the Boundaries of Tractable Contract Design
Michal Feldman, Liat Yashin
We study the optimal contract problem in the \emph{combinatorial actions} framework of Dütting et al.~[FOCS'21], where a principal delegates a project to an agent who chooses a sub…
Budget-Feasible Contracts
Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka +1
The problem of computing near-optimal contracts in combinatorial settings has recently attracted significant interest in the computer science community. Previous work has provided…
Succinct Ambiguous Contracts
Paul Duetting, Michal Feldman, Yarden Rashti
Real-world contracts are often ambiguous. While recent work by Dütting, Feldman, Peretz, and Samuelson (EC 2023, Econometrica 2024) demonstrates that ambiguous contracts can yield…
The Pseudo-Dimension of Contracts
Paul Duetting, Michal Feldman, Tomasz Ponitka +1
Algorithmic contract design studies scenarios where a principal incentivizes an agent to exert effort on her behalf. In this work, we focus on settings where the agent's type is dr…
Proportionally Fair Makespan Approximation
Michal Feldman, Jugal Garg, Vishnu V. Narayan +1
We study fair mechanisms for the classic job scheduling problem on unrelated machines with the objective of minimizing the makespan. This problem is equivalent to minimizing the eg…