New arXiv paper uses game theory to cut food waste via optimal menu selection

A new computational paper on arXiv tackles the ubiquitous challenge of ordering food for groups with varied dietary preferences and requirements while minimizing waste. The authors—Haris Aziz, Nicholas Mattei, Shivika Narang, and Sanjukta Roy—formalize this as a collective decision-making problem. They consider two consumption models: an optimistic model where a central planner optimally allocates food to maximize the number of fed agents, and a pessimistic model where agents serve themselves in an arbitrary order, guaranteeing a worst-case outcome. The goal in both cases is to select a valid menu (one that sufficiently feeds everyone) of the smallest possible size.

The team provides characterizations of valid menus under each model, identifies polynomial-time algorithms for important special cases, and designs integer linear programs for general instances. A key contribution is the definition and analysis of the 'waste of pessimism'—the ratio between the minimum size of a pessimistic menu and that of an optimistic menu. They prove tight upper bounds on this ratio, offering insights into the efficiency loss from uncoordinated self-service. These results are not only theoretically rigorous but also practical, enabling caterers, event planners, and cafeterias to reduce food waste through algorithmic menu selection. The paper also connects to problems in matching theory, extending its impact beyond food waste.