Tomer Ezra

TCS Journal 2026 Journal Article

Fair division with interdependent values

• Georgios Birmpas
• Tomer Ezra
• Stefano Leonardi
• Matteo Russo

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 set of goods that needs to be allocated to a set of agents (without disposal). Each agent is given a private signal, and his valuation function depends on the signals of all agents. Without the use of payments, there are strong impossibility results for designing strategyproof allocation mechanisms even in settings without interdependent values. Therefore, we turn to design mechanisms that always admit equilibria that are fair with respect to their true signals, despite their potentially distorted perception. To do so, we first extend the definitions of pure Nash equilibrium and well-studied fairness notions in literature to the interdependent setting. We devise simple allocation mechanisms that always admit a fair equilibrium with respect to the true signals. We complement this result by showing that, even for very simple cases with binary additive interdependent valuation functions, no allocation mechanism that always admits an equilibrium, can guarantee that all equilibria are fair with respect to the true signals.

SODA Conference 2025 Conference Paper

Multi-Agent Combinatorial Contracts

• Paul Dütting
• Tomer Ezra
• Michal Feldman
• Thomas Kesselheim

STOC Conference 2025 Conference Paper

Multi-parameter Mechanisms for Consumer Surplus Maximization

• Tomer Ezra
• Daniel Schoepflin 0001
• Ariel Shaulker

We consider the problem of designing auctions that maximize consumer surplus (i.e., the social welfare minus the payments charged to the buyers). In the consumer surplus maximization problem, a seller with a set of goods faces a set of strategic buyers with private values, each of whom aims to maximize their own individual utility. The seller, in contrast, aims to allocate the goods in a way that maximizes the total buyer utility . The seller must then elicit the values of the buyers in order to decide what goods to award each buyer. The canonical approach in mechanism design to ensure truthful reporting of the private information is to find appropriate prices to charge each buyer in order to align their objective with the objective of the seller. Indeed, there are many celebrated results to this end when the seller’s objective is welfare maximization or revenue maximization . However, in the case of consumer surplus maximization the picture is less clear – using high payments to ensure the highest value bidders are served necessarily decreases their surplus utility, but using low payments may lead the seller into serving lower value bidders. Our main result in this paper is a framework for designing mechanisms that maximize consumer surplus. We instantiate our framework in a variety of canonical multi-parameter auction settings (i.e., unit-demand bidders with heterogeneous items, multi-unit auctions, and auctions with divisible goods) and use it to design auctions achieving consumer surplus with tight approximation guarantees against the total social welfare. Along the way, we resolve an open question posed by Hartline and Roughgarden [STOC 2008] for the two bidders single item setting.

AIJ Journal 2025 Journal Article

Pandora's box problem with time constraints

• Georgios Amanatidis
• Ben Berger
• Tomer Ezra
• Michal Feldman
• Federico Fusco
• Rebecca Reiffenhäuser
• Artem Tsikiridis

The Pandora's Box problem models the search for the best alternative when evaluation is costly. In the simplest variant, a decision maker is presented with $n$ boxes, each associated with a cost of inspection and a hidden random reward. The decision maker inspects a subset of these boxes one after the other, in a possibly adaptive order, and gains the difference between the largest revealed reward and the sum of the inspection costs. Although this classic version is well understood (Weitzman 1979), there is a flourishing recent literature on variants of the problem. Here we introduce a general framework -- the Pandora's Box Over Time problem -- that captures a wide range of variants where time plays a role, e. g. , by constraining the schedules of exploration and influencing costs and rewards. In our framework, boxes have time-dependent rewards and costs, whereas inspection may require a box-specific processing time. Moreover, once a box is inspected, its reward may deteriorate over time. Our main result is an efficient constant-factor approximation to the optimal strategy for the Pandora's Box Over Time problem, which is generally NP-hard to compute. We further obtain improved results for the natural special cases where boxes have no processing time, boxes are available only in specific time slots, or when costs and reward distributions are time-independent (but rewards may still deteriorate after inspection).

AAAI Conference 2024 Conference Paper

Pandora’s Problem with Deadlines

• Ben Berger
• Tomer Ezra
• Michal Feldman
• Federico Fusco

Pandora’s problem is a fundamental model that studies optimal search under costly inspection. In the classic version, there are n boxes, each associated with a known cost and a known distribution over values. A strategy inspects the boxes sequentially and obtains a utility that equals the difference between the maximum value of an inspected box and the total inspection cost. Weitzman (1979) presented a surprisingly simple strategy that obtains the optimal expected utility. In this work we introduce a new variant of Pandora’s problem in which every box is also associated with a publicly known deadline, indicating the final round by which its value may be chosen. This model captures many real-life scenarios where alternatives admit deadlines, such as candidate interviews and college admissions. Our main result is an efficient threshold-based strategy that achieves a constant approximation relative to the performance of the optimal strategy for the deadlines setting.

SODA Conference 2023 Conference Paper

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

• Tomer Ezra
• Michal Feldman
• Nikolai Gravin
• Zhihao Gavin Tang

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 in an online fashion. Our new measure is called order-competitive ratio. It is defined as the worst case (over all distribution sequences) ratio between the performance of the best order-unaware and order-aware algorithms, and quantifies the loss that is incurred due to lack of knowledge of the arrival order. Despite the growing interest in the role of the arrival order on the performance of online algorithms, this loss has been overlooked thus far. We study the order-competitive ratio in the paradigmatic prophet inequality problem, for the two common objective functions of (i) maximizing the expected value, and (ii) maximizing the probability of obtaining the largest value; and with respect to two families of algorithms, namely (i) adaptive algorithms, and (ii) single-threshold algorithms. We provide tight bounds for all four combinations, with respect to deterministic algorithms. Our analysis requires new ideas and departs from standard techniques. In particular, our adaptive algorithms inevitably go beyond single-threshold algorithms. The results with respect to the order-competitive ratio measure capture the intuition that adaptive algorithms are stronger than single-threshold ones, and may lead to a better algorithmic advice than the classical competitive ratio measure. * This work is supported by Science and Technology Innovation 2030 –“New Generation of Artificial Intelligence” Major Project No. (2018AAA0100903), Innovation Program of Shanghai Municipal Education Commission, Program for Innovative Research Team of Shanghai University of Finance and Economics (IRTSHUFE) and the Fundamental Research Funds for the Central Universities. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 866132), by the Israel Science Foundation (grant number 317/17), by an Amazon Research Award, and by the NSF-BSF (grant number 2020788). Tomer Ezra was partially supported by the ERC Advanced Grant 788893 AMDROMA “Algorithmic and Mechanism Design Research in Online Markets” and MIUR PRIN project ALGADIMAR “Algorithms, Games, and Digital Markets”. Zhihao Gavin Tang is supported by NSFC grant 61902233. Nick Gravin is supported by NSFC grant 62150610500.

STOC Conference 2023 Conference Paper

Multi-agent Contracts

• Paul Dütting
• Tomer Ezra
• Michal Feldman
• Thomas Kesselheim

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 heart of our model is a reward function , which maps the agent efforts to an expected reward of the principal. We seek to design computationally efficient algorithms for finding optimal (or near-optimal) linear contracts for reward functions that belong to the complement-free hierarchy. Our first main result gives constant-factor approximation algorithms for submodular and XOS reward functions, with value and demand oracles, respectively. It relies on an unconventional use of “prices” and (approximate) demand queries for selecting the set of agents that the principal should contract with, and exploits a novel scaling property of XOS functions and their marginals, which may be of independent interest. Our second main result is an Ω(√ n ) impossibility for settings with n agents and subadditive reward functions, even with demand oracle access. A striking feature of this impossibility is that it applies to subadditive functions that are constant-factor close to submodular. This presents a surprising departure from previous literature, e.g., on combinatorial auctions.

FOCS Conference 2021 Conference Paper

Combinatorial Contracts

• Paul Dütting
• Tomer Ezra
• Michal Feldman
• Thomas Kesselheim

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 of a given set of unobservable actions, each of which has an associated cost. The cost of a set of actions is the sum of the costs of the individual actions, and the principal's reward as a function of the chosen actions satisfies some form of diminishing returns. The principal incentivizes the agents through a contract, based on the observed outcome. Our main results are for the case where the task delegated to the agent is a project, which can be successful or not. We show that if the success probability as a function of the set of actions is gross substitutes, then an optimal contract can be computed with polynomially many value queries, whereas if it is submodular, the optimal contract is NP-hard. All our results extend to linear contracts for higher-dimensional outcome spaces, which we show to be robustly optimal given first moment constraints. Our analysis uncovers a new property of gross substitutes functions, and reveals many interesting connections between combinatorial contracts and combinatorial auctions, where gross substitutes is known to be the frontier for efficient computation.

AAAI Conference 2021 Conference Paper

Fair and Truthful Mechanisms for Dichotomous Valuations

• Moshe Babaioff
• Tomer Ezra
• Uriel Feige

We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties expost. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations.

IJCAI Conference 2021 Conference Paper

On a Competitive Secretary Problem with Deferred Selections

• Tomer Ezra
• Michal Feldman
• Ron Kupfer

We study the secretary problem in multi-agent environments. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes an immediate and irrevocable decision whether to accept each award upon its arrival. The requirement to make immediate decisions arises in many cases due to an implicit assumption regarding competition. Namely, if the decision maker does not take the offered award immediately, it will be taken by someone else. We introduce a novel multi-agent secretary model, in which the competition is explicit. In our model, multiple agents compete over the arriving awards, but the decisions need not be immediate; instead, agents may select previous awards as long as they are available (i. e. , not taken by another agent). If an award is selected by multiple agents, ties are broken either randomly or according to a global ranking. This induces a multi-agent game in which the time of selection is not enforced by the rules of the games, rather it is an important component of the agent's strategy. We study the structure and performance of equilibria in this game. For random tie breaking, we characterize the equilibria of the game, and show that the expected social welfare in equilibrium is nearly optimal, despite competition among the agents. For ranked tie breaking, we give a full characterization of equilibria in the 3-agent game, and show that as the number of agents grows, the winning probability of every agent under non-immediate selections approaches her winning probability under immediate selections.

FOCS Conference 2019 Conference Paper

Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers

• Tomer Ezra
• Michal Feldman
• Eric Neyman
• Inbal Talgam-Cohen
• S. Matthew Weinberg

We study the communication complexity of welfare maximization in combinatorial auctions with m items and two players with subadditive valuations. We show that outperforming the trivial 1/2-approximation requires exponential communication, settling an open problem of Dobzinski, Nisan and Schapira [STOC’05, MOR’10] and Feige [STOC’06, SICOMP ’09]. To derive our results, we introduce a new class of subadditive functions that are “far from” fractionally subadditive (XOS) functions, and establish randomized communication lower bounds for a new “near-EQUALITY” problem, both of which may be of independent interest.