AAMAS Conference 2025 Conference Paper
Fair Assignment on Multi-Stage Graphs
- Vibulan J
- Swapnil Dhamal
- Shweta Jain
- Ojassvi Kumar
- Aman Kumar
- Harpreet Singh
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.