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 et al., and investigate the core, the nucleolus, the τ-value, and the Shapley value.