3 papers
cs.GT2025
Computing Envy-Free up to Any Good (EFX) Allocations via Local Search
Simina Brânzei
We present a simple local search algorithm for computing EFX (envy-free up to any good) allocations of indivisible goods among agents with additive valuations. EFX is a com…
cs.CC2024
A note on quantum lower bounds for local search via congestion and expansion
Simina Brânzei, Nicholas J. Recker
We consider the quantum query complexity of local search as a function of graph geometry. Given a graph with vertices and black box access to a function $f : V \to…
cs.GT2024
Dueling Over Dessert, Mastering the Art of Repeated Cake Cutting
Simina Brânzei, MohammadTaghi Hajiaghayi, Reed Phillips +2
We consider the setting of repeated fair division between two players, denoted Alice and Bob, with private valuations over a cake. In each round, a new cake arrives, which is ident…