Dr. Aleksandr Kazachkov
ISE Assistant Professor
University of Florida
Friday, May 3, 2024
2:15-3:15pm Tickle 500
Abstract: We consider allocating indivisible goods with provable fairness guarantees that are satisfied regardless of which bundle of items each agent receives. This setting arises, for example, with a local food bank that attempts to presort donations into boxes that should all be comparable in nutritional value.
Symmetrical allocations of this type are known to exist for divisible resources, such as through consensus splitting of a cake into parts, each having equal value for all agents, ensuring that in any allocation of the cake slices, no agent would envy another. As this is unachievable in general for indivisible goods, we instead primarily study a criterion that we call symmetric envy freeness up to one good (symEF1), under which an agent’s maximum envy when receiving any bundle is bounded above by the value of the agent’s favorite item in any other bundle.
Although symEF1 is a much stronger condition than the regular EF1 notion, we show that a symEF1 allocation always exists for two agents, as well as for agents that have identical or binary valuations, along with a corresponding efficient algorithm. We further provide sufficient conditions for existence of exponentially-many symEF1 allocations for more than two agents. We provide a comparison to other fairness and efficiency criteria, including a lower bound on the impact on social welfare that suggests a steep price of fairness when imposing the symEF1 constraint. Finally, we perform computational experiments to study the incidence of symEF1 allocations as a function of the number of agents and items when valuations are drawn uniformly at random.
Bio: Aleksandr Kazachkov is an assistant professor in the Department of Industrial and Systems Engineering and an assistant director of the Center of Applied Optimization at the University of Florida. His research is in discrete optimization and computational economics, with prior work focusing on cutting plane algorithms, theory of fair allocation of scarce resources, and fair mechanism design for healthcare, humanitarian, and sports settings. He received his Ph.D. at Carnegie Mellon University, studying under Egon Balas, and following that was a postdoctoral researcher at Polytechnique Montréal under Andrea Lodi. His research has been supported by a grant from the Air Force Office of Scientific Research and it has been recognized with a GERAD Postdoctoral Fellowship, 2018 INFORMS Computing Society Student Paper Award, and 2014 MIP Workshop Best Poster Prize.