2 papers
cs.GT2025
Approximating Pandora's Knapsack via Simple Policies
Zohar Barak, Asnat Berlin, Ilan Reuven Cohen +3
We introduce Pandora's Knapsack: a hybrid between the classic stochastic knapsack problem [Dean et al., 2008] and Pandora's box [Weitzman, 1979]. As in stochastic knapsack, items h…
cs.GT2024
Plant-and-Steal: Truthful Fair Allocations via Predictions
Ilan Reuven Cohen, Alon Eden, Talya Eden +1
We study truthful mechanisms for approximating the Maximin-Share (MMS) allocation of agents with additive valuations for indivisible goods. Algorithmically, constant factor approxi…