2 papers
cs.DS2025
Optimal Single-Choice Prophet Inequalities from Samples
Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg
We study the single-choice Prophet Inequality problem when the gambler is given access to samples. We show that the optimal competitive ratio of can be achieved with a single…
cs.CC2025
Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash
Yakov Babichenko, Christos Papadimitriou, Aviad Rubinstein
We conjecture that PPAD has a PCP-like complete problem, seeking a near equilibrium in which all but very few players have very little incentive to deviate. We show that, if one as…