ECAI Conference 2025 Conference Paper
- Vibulan J
- Swapnil Dhamal
- Shweta Jain 0002
This paper explores the problem of fair assignment on Multi-Stage graphs. A multi-stage graph consists of nodes partitioned into K disjoint sets (stages) structured as a sequence of weighted bipartite graphs formed across adjacent stages. The goal is to assign node-disjoint paths to n agents starting from the first stage and ending in the last stage. We show that an efficient assignment that minimizes the overall sum of costs of all the agents’ paths may be highly unfair and lead to significant cost disparities (envy) among the agents. We further show that finding an envy-minimizing assignment on a multi-stage graph is NP-hard. We propose the C-Balance algorithm, which guarantees envy that is bounded by 2M in the case of two agents, where M is the maximum edge weight. We demonstrate the algorithm’s tightness by presenting an instance where the envy is 2M. We further show that the cost of fairness (CoF), defined as the ratio of the cost of the assignment given by the fair algorithm to that of the minimum cost assignment, is bounded by 2 for C-Balance. We then extend this approach to n agents by proposing the DC-Balance algorithm that makes iterative calls to C-Balance. We show the convergence of DC-Balance, resulting in envy that is arbitrarily close to 2M. We derive CoF bounds for DC-Balance and provide insights about its dependency on the instance-specific parameters and the desired degree of envy. We experimentally show that our algorithm runs several orders of magnitude faster than a suitably formulated ILP.