Computational Aspects of Cooperative Game Theory (Synthesis Lectures on Artificial Intelligence and Machine Learning)

Computational Aspects of Cooperative Game Theory (Synthesis Lectures on Artificial Intelligence and Machine Learning)

Michael Wooldridge

Language: English

Pages: 168

ISBN: 1608456528

Format: PDF / Kindle (mobi) / ePub

Cooperative game theory is a branch of (micro-)economics that studies the behavior of self-interested agents in strategic settings where binding agreements among agents are possible. Our aim in this book is to present a survey of work on the computational aspects of cooperative game theory. We begin by formally defining transferable utility games in characteristic function form, and introducing key solution concepts such as the core and the Shapley value. We then discuss two major issues that arise when considering such games from a computational perspective: identifying compact representations for games, and the closely related problem of efficiently computing solution concepts for games. We survey several formalisms for cooperative games that have been proposed in the literature, including, for example, cooperative games defined on networks, as well as general compact representation schemes such as MC-nets and skill games. As a detailed case study, we consider weighted voting games: a widely-used and practically important class of cooperative games that inherently have a natural compact representation. We investigate the complexity of solution concepts for such games, and generalizations of them.

We briefly discuss games with non-transferable utility and partition function games. We then overview algorithms for identifying welfare-maximizing coalition structures and methods used by rational agents to form coalitions (even under uncertainty), including bargaining algorithms. We conclude by considering some developing topics, applications, and future research directions.

Table of Contents: Introduction / Basic Concepts / Representations and Algorithms / Weighted Voting Games / Beyond Characteristic Function Games / Coalition Structure Formation / Advanced Topics

"This manuscript was a pleasure to discover, and a pleasure to read -- a broad, but succinct, overview of work in computational cooperative game theory. I will certainly use this text with my own students, both within courses and to provide comprehensive background for students in my research group. The authors have made a substantial contribution to the multiagent systems and algorithmic game theory communities." --Professor Jeffrey S. Rosenschein, The Hebrew University of Jerusalem, Israel

"With the advent of the internet, the computational aspects of cooperative game theory are ever more relevant. This unique and timely book by Chalkiadakis, Elkind, and Wooldridge gives a concise and comprehensive survey of the subject, and serves at the same time as a one-stop introduction to cooperative game theory." --Professor Bernhard von Stengel, London School of Economics, UK

"In recent years, research on the computational aspects of cooperative game theory has made tremendous progress, but previous textbooks have not included more than a short introduction to this important topic. I am excited by the thorough treatment in this new book, whose authors have been and continue to be at the very forefront of this research. Newcomers to the area are well advised to read this book carefully and cover to cover." --Professor Vincent Conitzer, Duke University, USA

"Cooperative game theory has proved to be a fertile source of challenges and inspiration for computer scientists. This book will be an essential companion for everyone wanting to explore the computational aspects of cooperative game theory." --Prof Makoto Yokoo, Kyushu University, Japan

"An excellent treatise on algorithms and complexity for cooperative games. It navigates through the maze of cooperative solution concepts to the very frontiers of algorithmic game theory research.The last chapter in particular will be enormously valuable for graduate students and young researchers looking for research topics." --Professor Xiaotie Deng, University of Liverpool, UK




















university Y to write a paper. Both will obtain some benefit from writing the paper, but the benefit that B obtains may well be much greater than the benefit that A obtains, simply because the value added to B’s career is greater than the value added to A’s, and the benefits that B obtains (enhanced reputation, scientific credibility, standing in the field) cannot easily be transferred from B to A. Such settings in cooperative game theory are the domain of non-transferable utility games (NTU

games). Characteristic function games are, for obvious reasons, not appropriate for modelling NTU games. In this section, we will focus on NTU games, and in particular, we survey some key NTU game models that have been proposed in the multiagent systems and algorithmic game theory communities. 72 5. BEYOND CHARACTERISTIC FUNCTION GAMES 5.1.1 FORMAL MODEL We begin by introducing a basic model of NTU games, a counterpart to the characteristic function game model of chapter 2. The basic idea

elaborate on connections between games with and without cooperation. We will argue that, by taking the possibility of cooperation into account, we can obtain a better understanding of some scenarios that are usually modeled as non-cooperative games; conversely, in many cases, cooperative solutions concepts can be justified in non-cooperative terms. 7.1.1 COOPERATION IN NORMAL-FORM GAMES Aumann [11] and Aumann and Peleg [14] observed that, if players in a normal-form game are allowed to

a parting note, in this section we list several topics in coalitional game theory that, in our opinion, present interesting research opportunities for the immediate future. The first one is algorithmic aspects of coalitional games in structured environments. These are environments that can be modeled by identifying the players with the vertices of a graph and allowing a coalition to form only if it corresponds to a connected subgraph. Intuitively, edges encode relationships between players (an

problem are encoded or represented. In the problems listed above, the inputs are games and the outcomes for games. Thus, to formally analyze the problems listed above in computational terms, we need some way of representing or encoding games and their outcomes. A rule of thumb in computational analysis is that the more concise or expressive a representation scheme used to encode inputs is, the harder will be the associated computational problems. This issue is emphasized rather dramatically when

Download sample