Seminars

View all Seminars  |  Download ICal for this event

Menu Selection: Provably minimizing food waste

Series: Bangalore Theory Seminars

Speaker: Shivika Narang, UNSW Sydney

Date/Time: Jan 08 11:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Abstract:
We introduce a novel collective decision making problem that captures the ubiquitous issue of ordering food to cater for varied dietary restrictions. Our settings involve agents with potentially diverse dietary requirements over menu options with varied serving sizes. The goal is to select a menu where everyone has enough food they can consume and which minimizes the food waste. We introduce two different consumption models: optimistic and pessimistic. Optimistic consumption assumes a situation when a central planner can optimally allocate the food ordered among the agents to maximize the number of people who get enough to eat. Pessimistic considers the worst case guarantee on consumption when agents fill their own plates in an arbitrary order.

Our work provides two sets of characterizations: I) We characterize minimum sized valid menus under either consumption model and II) We characterize the space of instances which admit efficient algorithms to find minimum sized menus. Our results here help us construct ILPs to find minimum sized menus in general settings. Further for some structured settings, we find tractable algorithms to do so. The second direction we consider is to understand the worst case discrepancy between the size of minimum sized optimistic and pessimistic menus. We call this the waste of pessimism captured by the ratio of the minimum sized pessimistic menu to that of the minimum sized optimistic menu. We show tight upper bounds on this ratio for structured settings. On the way, our results also provide additional insights on the problem of finding a minimum sized maximal matching, which may be of independent interest.

Joint work with Sanjukta Roy, Haris Aziz and Nicholas Mattei.

Microsoft Teams link<

Link

We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, Nirjhar Das, KVN Sreenivas, Debajyoti Kar, Rahul Madhavan