Non-transferable utility coalitional games via mixed-integer linear constraints

DOI10.1613/JAIR.3060MaRDI QIDQ3588641zbMATH OpenOpenAlexWikidataFDO

Authors Gianluigi Greco, Enrico Malizia, Luigi Palopoli, Francesco Scarcello

Publication date 9 September 2010

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.3852

zbMATH Keywords

computational complexitygame theorycoalitional games

Mathematics Subject Classification ID

Cooperative games (91A12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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.

Recommendations

• Answers set programs for non-transferable utility games: expressiveness, complexity and applications
• The Harsanyi value for nontransferable utility games with restricted cooperation
• Nontransferable utility games with fuzzy coalition restrictions
• Solving coalitional resource games
• On the complexity of core, kernel, and bargaining set

Cited in

(8)

• Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting
• Complexity results for preference aggregation over \((m)\)CP-nets: max and rank voting
• The complexity of the nucleolus in compact games
• Nontransferable utility games with fuzzy coalition restrictions
• Answers set programs for non-transferable utility games: expressiveness, complexity and applications
• A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
• Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
• On the complexity of core, kernel, and bargaining set

This page was built for publication: Non-transferable utility coalitional games via mixed-integer linear constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3588641)