Tomer Ezra

Fair Share Allocations for Almost All Agents

Tomer Ezra, Tamar Garbuz

We study fair allocation of indivisible goods among agents with additive valuations. Our main result guarantees every agent her exact AnyPrice Share (APS) whenever the total entitl…

Improved Impossibility Bounds for Maximin Share Allocations

Tomer Ezra, Tamar Garbuz

The maximin share (MMS) is a central fairness benchmark for allocating indivisible items, but it need not be simultaneously attainable even under additive preferences. While extens…

Welfare Approximation in Multilateral Trade

Tomer Ezra, Aadityan Ganesh, Aviad Rubinstein

We introduce the study of \emph{multilateral trade}: a mechanism-design problem in which a single potential trade involves $k$ agents and can be executed only if all $k$ agents agr…

Money Burning Mechanism Design: From Welfare to Surplus

Tomer Ezra

We settle the worst-case approximability of consumer-surplus maximization in general multidimensional mechanism-design environments. We do so through two black-box reductions from…

cs.GT2025

Black-Box Lifting and Robustness Theorems for Multi-Agent Contracts

Paul Dütting, Tomer Ezra, Michal Feldman +1

Multi-agent contract design has largely evaluated contracts through the lens of pure Nash equilibria (PNE). This focus, however, is not without loss: In general, the principal can…

cs.GT2025

Multi-Project Contracts

Tal Alon, Matteo Castiglioni, Junjie Chen +3

We study a new class of contract design problems where a principal delegates the execution of multiple projects to a set of agents. The principal's expected reward from each projec…

The Competition Complexity of Prophet Secretary

Tomer Ezra, Tamar Garbuz

We study the classic single-choice prophet secretary problem through a resource augmentation lens. Our goal is to bound the $(1 - ε)$ -competition complexity for different classes of…

Prophet Inequality from Samples: Is the More the Merrier?

Tomer Ezra

We study a variant of the single-choice prophet inequality problem where the decision-maker does not know the underlying distribution and has only access to a set of samples from t…

cs.GT2024★ 1 cited

Multi-Agent Combinatorial Contracts

Paul Duetting, Tomer Ezra, Michal Feldman +1

Combinatorial contracts are emerging as a key paradigm in algorithmic contract design, paralleling the role of combinatorial auctions in algorithmic mechanism design. In this paper…

Contract Design for Sequential Actions

Tomer Ezra, Michal Feldman, Maya Schlesinger

We introduce a novel model of contracts with combinatorial actions that accounts for sequential and adaptive agent behavior. As in the standard model, a principal delegates the exe…

Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms

Tomer Ezra, Michal Feldman, Zhihao Gavin Tang

In Bayesian online settings, every element has a value that is drawn from a known underlying distribution, which we refer to as the element's identity. The elements arrive sequenti…

The Competition Complexity of Prophet Inequalities

Johannes Brustle, José Correa, Paul Dütting +3

We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the $(1 - ε)$ -competition complexity of different t…

Multi-Parameter Mechanisms for Consumer Surplus Maximization

Tomer Ezra, Daniel Schoepflin, Ariel Shaulker

We consider the problem of designing auctions which maximize consumer surplus (i.e., the social welfare minus the payments charged to the buyers). In the consumer surplus maximizat…

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…

cs.GT2023

On the (In)approximability of Combinatorial Contracts

Tomer Ezra, Michal Feldman, Maya Schlesinger

We study two combinatorial contract design models -- multi-agent and multi-action -- where a principal delegates the execution of a costly project to others. In both settings, the…

cs.GT2023

The Importance of Knowing the Arrival Order in Combinatorial Bayesian Settings

Tomer Ezra, Tamar Garbuz

We study the measure of order-competitive ratio introduced by Ezra et al. [2023] for online algorithms in Bayesian combinatorial settings. In our setting, a decision-maker observes…

cs.GT2023

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…

cs.GT2022★ 1 cited

Multi-Agent Contracts

Paul Duetting, Tomer Ezra, Michal Feldman +1

We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the h…

cs.GT2022

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…

cs.GT2022

"Who Is Next in Line?'' On the Significance of Knowing the Arrival Order in Bayesian Online Settings

Tomer Ezra, Michal Feldman, Nick Gravin +1

We introduce a new measure for the performance of online algorithms in Bayesian settings, where the input is drawn from a known prior, but the realizations are revealed one-by-one…

Combinatorial Contracts

Paul Duetting, Tomer Ezra, Michal Feldman +1

We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take any subset o…

Prophet Inequality with Competing Agents

Tomer Ezra, Michal Feldman, Ron Kupfer

We introduce a model of competing agents in a prophet setting, where rewards arrive online, and decisions are made immediately and irrevocably. The rewards are unknown from the out…

Fair-Share Allocations for Agents with Arbitrary Entitlements

Moshe Babaioff, Tomer Ezra, Uriel Feige

We consider the problem of fair allocation of indivisible goods to $n$ agents, with no transfers. When agents have equal entitlements, the well established notion of the maximin sh…