Fair Assignment on Multi-Stage Graphs

Vibulan J (IIITDM Kancheepuram), Swapnil Dhamal (Indian Institute of Technology Ropar), Shweta Jain (Indian Institute of Technology Ropar), Ojassvi Kumar (Indian Institute of Technology Ropar), Aman Kumar (Indian Institute of Technology Ropar), Harpreet Singh (Indian Institute of Technology Ropar)

Abstract

This paper explores the problem of fair assignment of disjoint paths to agents on multi-stage graphs. We motivate the problem by demonstrating that an assignment minimizing the overall cost of all the agents' paths may lead to significant envy among the agents. Showing NP-hardness of finding an envy-minimizing assignment, we propose algorithms that achieve a desired degree of envy while also providing a bound on the Cost of Fairness. Our algorithms run several orders of magnitude faster than a suitably formulated ILP.