Giving Some Space Can Be Hard: Two New Models to Match Agents with Locations by Shivika Narang

Title: Giving Some Space Can Be Hard: Two New Models to Match Agents with Locations

Speaker: Shivika Narang (UNSW Sydney)

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 office spaces. 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 and analyze distance preservation games (DPGs). In DPGs, agents express ideal distances to other agents and need to choose locations in the unit interval while preserving their ideal distances as closely as possible. We analyze the existence and computation of location profiles that are jump stable (i.e., no agent can benefit by moving to another location) or welfare optimal for DPGs, respectively.

Joint Work with Hadi Hosseini and Tomasz Wąs (Fair Delivery) and Haris Aziz, Hau Chan, Patrick Lederer, and Toby Walsh (DPGs).

Speaker 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. Her work is currently focused on fairness and efficiency in computational social choice, especially matching and allocation problems.