Giving Some Space Can Be Hard: Two New Models to Match Agents with Locations by Dr. Shivika Narang
September 1 @ 12:00 pm - 1:00 pm
Abstract: There can be a multitude of reasons to match agents to specific locations in a given space. In this talk we cover two: distributing delivery orders and assigning shared hostel rooms. For both settings we shall try to find solutions that satisfy desirable properties and characterize instances for which they exist.
We first initiate the study of fair distribution of delivery tasks among a set of agents wherein delivery jobs are placed along the vertices of a graph. Our goal is to fairly distribute delivery costs (modeled as a submodular function) among a fixed set of agents while satisfying some desirable notions of economic efficiency. We characterize instances that admit fair and efficient solutions by exploiting underlying graph structures. Unfortunately, finding these solutions proves to be NP-hard. We complement this by designing an XP algorithm (parameterized by the number of agents) that can find all fair and efficient solutions when they exist. We conclude this discussion by theoretically and experimentally analyzing the price of fairness.
We shall then introduce Leontief utilities to the problem of roommate matchings. We aim to find strategyproof mechanisms that give good bounds on agent welfare. We first find that no approximation to welfare can be achieved under strategyproof mechanisms for either Leontief or additive utilities. Even for binary additive utilities no maximum welfare mechanism can be strategyproof. In contrast, we then –surprisingly– find that binary Leontief utilities enable us to find strategyproof mechanisms that maximize welfare.
Joint work with Hadi Hosseini, Sanjukta Roy and Tomasz Was.
Bio: Shivika Narang is a postdoctoral fellow at UNSW Sydney. Previously she was a postdoc at Simons Laufer Mathematical Sciences Institute, Berkeley (SLMath) and completed her PhD from IISc Bengaluru. During her PhD, she received the Tata Consultancy Services Research Fellowship. Her work is currently focused on finding fair and efficient solutions to societal problems. She largely works in computational social choice, especially matching and allocation problems.