abstract:
In the max-flow game, agents are represented by the edges of a capacitated directed graph with a designated source (s) and sink (t). Given a set of agents (S), the associated profit is the maximum s-t flow that can be achieved in the subgraph formed by the edges of S. The total profit generated by the maximum flow must be divided among the agents, and an imputation describes how this profit is allocated. An imputation is said to be at the *core* of the game if no subset of agents has an incentive to break away from the grand coalition. A subset of agents (S) will secede if their collective profit share is less than the maximum flow that can be routed through their subgraph from the source to the sink.
This paper focuses on determining a lexicographically fair core imputation. A *leximin core imputation* ensures fairness by maximizing the profit share of the agent with the lowest profit share, then the next lowest, and so on, all within core constraints. We first prove that finding a core imputation that maximizes the minimum profit share is NP-hard. This result implies that computing a leximin core imputation in polynomial time is not feasible. In light of this intractability, we narrow our focus to core imputations that are "consistent" with the optimal solutions to the dual of the linear program that determines the value of the game; we refer to these as Dual-Consistent Core (DCC) imputations. We present both an LP-based approach and a combinatorial algorithm for efficiently computing the leximin DCC imputation in max-flow games.
-Michael
https://publish.illinois.edu/theory-cs/theory-seminar/theory-seminar-fall-2024/
