Non-Transferable Utility Coalitional Games via Mixed-Integer Linear Constraints

• Published in: The Journal of artificial intelligence research 2010-01, Vol.38, p.633-685
• Main Authors: Greco, G., Malizia, E., Palopoli, L., Scarcello, F.
• Format: Article
• Language: English
• Subjects: Artificial intelligence; Constraints; Games; Mixed integer
• ISSN: 1076-9757; 1076-9757; 1943-5037
• DOI: 10.1613/jair.3060

Coalitional games serve the purpose of modeling payoff distribution problems in scenarios where agents can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. In the classical Transferable Utility (TU) setting, coalition worths can be freely distributed amongst agents. However, in several application scenarios, this is not the case and the Non-Transferable Utility setting (NTU) must be considered, where additional application-oriented constraints are imposed on the possible worth distributions. In this paper, an approach to define NTU games is proposed which is based on describing allowed distributions via a set of mixed-integer linear constraints applied to an underlying TU game. It is shown that such games allow non-transferable conditions on worth distributions to be specified in a natural and succinct way. The properties and the relationships among the most prominent solution concepts for NTU games that hold when they are applied on (mixed-integer) constrained games are investigated. Finally, a thorough analysis is carried out to assess the impact of issuing constraints on the computational complexity of some of these solution concepts.