Fair Assignment on Multi-Stage Graphs

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.

Authors

• Vibulan J IIITDM Kancheepuram
• Swapnil Dhamal
• Shweta Jain Indian Institute of Science, Bangalore
• Ojassvi Kumar Indian Institute of Technology Ropar
• Aman Kumar
• Harpreet Singh Indian Institute of Technology Ropar

Keywords

• Fairness
• Multi-stage graphs
• Assignment
• Routing