Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

Extending the MC-nets representation scheme to cooperative game settings with uncertainty or overlaps

Streviniotis Errikos

Full record

---

Summary

Cooperative game theory studies how self rational agents interact with each other in order to form coalitions and achieve a common goal by collaborating, while maximising their own profits. Representing the collaborations efficiently is key for supporting coalition formation decisions and achieving tractable computation in cooperative game settings.Moreover, research in cooperative games often assumes that there is no uncertainty in the settings of the game, or that agents cannot participate in many coalitions simultaneously.In this thesis, we focus on a well-known coalitional representation scheme, the MC-nets representation, and extend it to settings where we remove the aforementioned unrealistic assumptions, namely having complete information and no-overlaps.We begin by extending the Relational Rules representation, a scheme that itself extends MC-nets to cooperative games with overlapping coalitions, so that it now includes both positive and negative literals. Our proposed representation reduces to the classic MC nets representation for non-overlapping environments.We then introduce a novel succinct representation scheme for cooperative games under uncertainty, the ε-MC nets. The proposed representation is discussed first in the context of transferable utility games, and exploits estimates over marginal contributions to form compact rules representing collaboration patterns with potentially uncertain value.In more detail, given a set of MC-nets rules that use prior beliefs over values instead of the actual ones, we provide a polynomial algorithm for reaching the proposed succinct representation. We provide theoretical results regarding the information loss (regarding the perceived value of the agent collaboration patterns) after the compression of the original representation of the set. We show that the loss from compressing the set is bounded by a value directly proportional to ε, which represents an error regarding the believed value of an original rule which we are willing to accept in order to compress the representation.We then extend our algorithm to exploit equivalence classes of agents. This allowsus to obtain an even more compact representation, and to derive new, previously unheld beliefs over the value of unobserved agent collaboration patterns. Moreover, we show that our approach extends naturally to non-transferable utility games.We conduct a systematic experimental evaluation of our algorithm’s variants, studying its behaviour in various realistic settings, and provide results on the compression achieved in each evaluated setting. Our experimental results confirm the effectiveness of our approach.

Available Files

Services