6 papers
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…
Adaptive Contracts for Cost-Effective AI Delegation
Eden Saig, Tamar Garbuz, Ariel D. Procaccia +2
When organizations delegate text generation tasks to AI providers via pay-for-performance contracts, expected payments rise when evaluation is noisy. As evaluation methods become m…
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 -competition complexity for different classes of…
The Competition Complexity of Prophet Inequalities with Correlations
Tomer Ezra, Tamar Garbuz
We initiate the study of the prophet inequality problem through the resource augmentation framework in scenarios when the values of the rewards are correlated. Our goal is to deter…
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…