2 papers
cs.GT2025
When Contracts Get Complex: Information-Theoretic Barriers
Paul Dütting, Michal Feldman, Yoav Gal-Tzur +1
In the combinatorial-action contract model (Dütting et al., FOCS'21) a principal delegates the execution of a complex project to an agent, who can choose any subset from a given s…
cs.DS2024
A Bicriterion Concentration Inequality and Prophet Inequalities for -Fold Matroid Unions
Noga Alon, Nick Gravin, Tristan Pollner +4
We investigate prophet inequalities with competitive ratios approaching , seeking to generalize -uniform matroids. We first show that large girth does not suffice: for all $k…