TY - GEN
T1 - On representing coalitional games with externalities
AU - Michalak, Tomasz P.
AU - Rahwan, Talal
AU - Sroka, Jacek
AU - Dowell, Andrew
AU - Wooldridge, Michael J.
AU - McBurney, Peter J.
AU - Jennings, Nicholas R.
PY - 2009
Y1 - 2009
N2 - We consider the issue of representing coalitional games in multi-agent systems with externalities (i.e., in systems where the performance of one coalition may be affected by other co-existing coalitions). In addition to the conventional partition function game representation (PFG), we propose a number of new representations based on a new notion of externalities. In contrast to conventional game theory, our new concept is not related to the process by which the coalitions are formed, but rather to the effect that each coalition may have on the entire system and vice versa. We show that the new representations are fully expressive and, for many classes of games, more concise than the conventional PFG. Building upon these new representations, we propose a number of approaches to solve the coalition structure generation problem in systems with externalities. We show that, if externalities are characterised by various degrees of regularity, the new representations allow us to adapt coalition structure generation algorithms that were originally designed for domains with no externalities, so that they can be used when externalities are present. Finally, building upon [16] and [9], we present a unified method to solve the coalition structure generation problem in any system, with or without externalities, provided sufficient information is available.
AB - We consider the issue of representing coalitional games in multi-agent systems with externalities (i.e., in systems where the performance of one coalition may be affected by other co-existing coalitions). In addition to the conventional partition function game representation (PFG), we propose a number of new representations based on a new notion of externalities. In contrast to conventional game theory, our new concept is not related to the process by which the coalitions are formed, but rather to the effect that each coalition may have on the entire system and vice versa. We show that the new representations are fully expressive and, for many classes of games, more concise than the conventional PFG. Building upon these new representations, we propose a number of approaches to solve the coalition structure generation problem in systems with externalities. We show that, if externalities are characterised by various degrees of regularity, the new representations allow us to adapt coalition structure generation algorithms that were originally designed for domains with no externalities, so that they can be used when externalities are present. Finally, building upon [16] and [9], we present a unified method to solve the coalition structure generation problem in any system, with or without externalities, provided sufficient information is available.
KW - Coalition structure generation
KW - Partition function games
KW - Representation
UR - http://www.scopus.com/inward/record.url?scp=77950550671&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77950550671&partnerID=8YFLogxK
U2 - 10.1145/1566374.1566377
DO - 10.1145/1566374.1566377
M3 - Conference contribution
AN - SCOPUS:77950550671
SN - 9781605584584
T3 - Proceedings of the ACM Conference on Electronic Commerce
SP - 11
EP - 20
BT - EC'09 - Proceedings of the 2009 ACM Conference on Electronic Commerce
T2 - 2009 ACM Conference on Electronic Commerce, EC'09
Y2 - 6 July 2009 through 10 July 2009
ER -