Search

Coalition structure generation is the problem of partitioning the agents of a given environment into disjoint and exhaustive coalitions so that the whole available worth is maximized. While this problem has been classically studied in settings where all coalitions are allowed to form, it has been recently reconsidered in the literature moving from the observation that environments often forbid the formation of certain coalitions. By following this latter perspective, a model for coalition structure generation is proposed where constraints of two different kinds can be expressed simultaneously. Indeed, the model is based on the concept of valuation structure , which consists of a set of pivotal agents that are pairwise incompatible, plus an interaction graph prescribing that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. It is shown that valuation structures can be used to model a number of relevant problems arising in real-world application domains. Then, the complexity of coalition structure generation over valuation structures is studied, by assuming that the functions associating each coalition with its worth are given as input according to some compact encoding—rather than explicitly listing all exponentially-many associations. In particular, islands of tractability are identified based on the topological properties of the underlying interaction graphs and on suitable algebraic properties of the given worth functions. Finally, stability issues over valuation structures are studied too, by considering the core as the prototypical solution concept. [ABSTRACT FROM AUTHOR]

In many real-world settings, the structure of the environment constrains the formation of coalitions among agents. These settings can be represented by characteristic function games, also known as coalitional games , equipped with interaction graphs. An interaction graph determines the set of all feasible coalitions, in that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. Our work analyzes stability issues arising in such environments, by focusing on the core as a solution concept, and by considering the coalition structure viewpoint, that is, without assuming that the grand-coalition necessarily forms. The complexity of the coalition structure core is studied over a variety of interaction graph structures of interest, including complete graphs, lines, cycles, trees, and nearly-acyclic graphs (formally, having bounded treewidth). The related stability concepts of the least core and the cost of stability are also studied. Results are derived for the setting of compact coalitional games, i.e., for games that are implicitly described via a compact encoding, and where simple calculations on this encoding are to be performed in order to compute the payoff associated with any coalition. Moreover, specific results are provided for compact games defined via marginal contribution networks , an expressive encoding mechanism that received considerable attention in the last few years. [ABSTRACT FROM AUTHOR]

Abstract: Coalitional games model scenarios where players can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. A fundamental issue of coalitional games is to single out the most desirable outcomes in terms of worth distributions, usually called solution concepts. Since decisions taken by realistic players cannot involve unbounded resources, recent computer science literature advocated the importance of assessing the complexity of computing with solution concepts. In this context, the paper provides a complete picture of the complexity issues arising with three prominent solution concepts for coalitional games with transferable utility, namely, the core, the kernel, and the bargaining set, whenever the game worth-function is represented in some reasonably compact form. The starting points of the investigation are the settings of graph games and of marginal contribution nets, where the worth of any coalition can be computed in polynomial time in the size of the game encoding and for which various open questions were stated in the literature. The paper answers these questions and, in addition, provides new insights on succinctly specified games, by characterizing the computational complexity of the core, the kernel, and the bargaining set in relevant generalizations and specializations of the two settings. Concerning the generalizations, the paper shows that dealing with arbitrary polynomial-time computable worth functions—no matter of the specific game encoding being considered—does not provide any additional source of complexity compared to graph games and marginal contribution nets. Instead, only for the core, a slight increase in complexity is exhibited for classes of games whose worth functions encode NP-hard optimization problems, as in the case of certain combinatorial games. As for specializations, the paper illustrates various tractability results on classes of bounded treewidth graph games and marginal contribution networks. [Copyright &y& Elsevier]

Coalitional games are mathematical models suited to study payoff distribution problems in cooperative scenarios. In abstract terms, a coalitional game can be specified by explicitly listing all possible—in fact, exponentially many—coalitions with their associated distributions. This naïve representation, however, quickly becomes infeasible over games involving many agents, thereby calling for suitable compact representations, that is, encoding mechanisms that (on some specific classes of games of interest) take an amount of space that grows polynomially with the number of agents. To date, a plethora of compact encodings have been already introduced and analyzed from the algorithm and computational viewpoints. Despite their specific technical differences, these encodings typically share the assumption that the utility associated with a coalition can be freely transferred among agents. Indeed, designing encoding mechanisms for the non-transferable utility (NTU) setting is a research issue that has been largely unexplored so far. The paper addresses this issue by proposing a compact encoding for representing and reasoning about the outcomes of NTU coalitional games founding on answer set programming. By exploiting the expressiveness of this well-known knowledge representation formalism, it is shown that the proposed representation can succinctly encode several games of interest within a wide range of application domains. Computational issues arising in the setting have been studied too, by addressing questions related to certain payoff distributions enjoying desirable stability properties. Eventually, a prototype system supporting the proposed framework has been implemented by leveraging a state-of-the-art answer set engine, and results of a thorough experimental activity conducted on top of it have been discussed. [ABSTRACT FROM AUTHOR]

The paper focuses on cooperative games where the worth of any coalition of agents is determined by the optimal value of a matching problem on (possibly weighted) graphs. These games come in different forms that can be grouped in two broad classes, namely of matching and allocation games, and they have a wide spectrum of applications, ranging from two-sided markets where buyers and sellers are encoded as vertices in a graph, to allocation problems where indivisible goods have to be assigned (matched) to agents in a fair way, possibly using monetary compensations. The Shapley value and the related notion of Banzhaf value have often been identified as appropriate solution concepts for many applications of matching/allocation games, but their computation is intractable in general. It is known that these concepts can be computed in polynomial time for matching games on unweighted trees and on graphs having degree at most two. However, it was open whether or not such positive results could be extended to the more general case of graphs having bounded treewidth, and to the case of allocation problems on weighted graphs. The paper provides a positive answer to these questions, by showing that computing the Shapley value and the Banzhaf value is feasible in polynomial time for the following classes of games: matching games over unweighted graphs having bounded treewidth, allocation games over weighted graphs having bounded treewidth, and allocation games over weighted graphs and such that each good is of interest for two agents at most. Without such structural restrictions, computing these solution concepts on allocation games is instead shown to be #P-hard, even in the case of unweighted graphs. [ABSTRACT FROM AUTHOR]