Fair cost allocations under conflicts — a game-theoretic point of view —

Optimization theory resolves problems to minimize total costs when the agents are involved in some conflicts. In this paper, we consider how to allocate the minimized total cost among the agents. To do that, the allocation is required to be fair in a certain sense. We use a game-theoretic point of view, and provide algorithms to compute fair allocations in polynomial time for a certain conflict situation. More specifically, we study a minimum coloring game, introduced by Deng, Ibaraki and Nagamochi [X. Deng, T. Ibaraki, H. Nagamochi, Algorithmic aspects of the core of combinatorial optimization games, Math. Oper. Res. 24 (1999) 751–766], and investigate the core, the nucleolus, the ττ-value, and the Shapley value. In particular, we provide the following four results. (1) The characterization of the core for a perfect graph in terms of its extreme points. This leads to polynomial-time algorithms to compute a vector in the core, and to determine whether a given vector belongs to the core. (2) A characterization of the nucleolus for some classes of the graphs, including the complete multipartite graphs and the chordal graphs. This leads to a polynomial-time algorithm to compute the nucleolus for these classes of graphs. (3) A polynomial-time algorithm to compute the ττ-value for a perfect graph. (4) A polynomial-time algorithm to compute the Shapley value for a forest. The investigation of this paper gives several insights to the relationship of algorithm theory with cooperative games.