[agents] NEW BOOK: Computational Aspects of Cooperative Game Theory (Chalkiadakis, Elkind, and Wooldridge)

[Wooldridge, Michael]

** New Book ** ** New Book ** ** New Book ** ** New Book ** 


COMPUTATIONAL ASPECTS of COOPERATIVE GAME THEORY
by Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge

Published 2011 by Morgan & Claypool Publishers.

http://dx.doi.org/10.2200/S00355ED1V01Y201107AIM016


** OVERVIEW **

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.

The book's web site, below, contains additional material including:

- complete downloadable lecture slides to accompany the book;
- video lectures of the book by the authors;
- downloadable bibliography (BibTeX) for the book.

Book web site: http://web.spms.ntu.edu.sg/~eelkind/coopbook/

"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."
-- Professor 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


** PUBLICATION DETAILS **

"Computational Aspects of Cooperative Game Theory" 
by Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge.
Published October 2011 by Morgan & Claypool Publishers. 
http://dx.doi.org/10.2200/S00355ED1V01Y201107AIM016


** TABLE OF CONTENTS **

Preface
Acknowledgments
Summary of Key Notation

1. Introduction
 1.1 Why are Non-Cooperative Games Non-Cooperative?
 1.2 Computational Problems in Game Theory
 1.3 The Remainder of This Book
 1.4 Further Reading

2. BasicConcepts
 2.1 Characteristic Function Games
 2.2 Solution Concepts
  2.2.1 Shapley Value
  2.2.2 Banzhaf Index
  2.2.3 Core and Core-Related Concepts
  2.2.4 Nucleolus
  2.2.5 Kernel 
  2.2.6 Bargaining Set
  2.2.7 Stable Set

3. Representations and Algorithms
 3.1 Combinatorial Optimization Games
  3.1.1 Induced Subgraph Games
  3.1.2 Network Flow Games 
  3.1.3 Assignment and Matching Games
  3.1.4 Minimum Cost Spanning Tree Games
  3.1.5 Facility Location Games
 3.2 Complete Representations  
  3.2.1 Marginal Contribution Nets
  3.2.2 Synergy Coalition Groups
  3.2.3 Skill-Based Representations
  3.2.4 Algebraic Decision Diagrams
 3.3 Oracle Representation

4. Weighted Voting Games
 4.1 Definition and Examples
 4.2 Dummies and Veto Players 
  4.2.1 Power and Weight
  4.2.2 Computing the Power Indices
  4.2.3 Paradoxes of Power
 4.3 Stability in Weighted Voting Games
  4.3.1 The Least Core, the Cost of Stability, and the Nucleolus
 4.4 Vector Weighted Voting Games
  4.4.1 Computing the Dimension of a Simple Game

5 Beyond Characteristic Function Games
 5.1 Non-transferable Utility Games
  5.1.1 Formal Model
  5.1.2 Hedonic Games
  5.1.3 Qualitative Games
 5.2 Partition Function Games

6. Coalition Structure Formation
 6.1 Coalition Structure Generation 
 6.1.1 Dynamic Programming
  6.1.2 Anytime Algorithms
 6.2 Coalition Formation by Selfish Rational Agents  
  6.2.1 Coalition Formation Via Bargaining 
  6.2.2 Dynamic Coalition Formation  
  6.2.3 Coalition Formation Under Uncertainty
 6.3 Coalition Formation and Learning

7 Advanced Topics
 7.1 Links between Cooperative and Non-cooperativeGames
  7.1.1 Cooperation in Normal-Form Games
  7.1.2 Non-Cooperative Justifications of Cooperative Solution Concepts
  7.1.3 Program Equilibrium
 7.2 Using Mechanism Design for Coalition Formation
  7.2.1 Anonymity-Proof Solution Concepts
 7.3 Overlapping and Fuzzy Coalition Formation
 7.4 Logical Approaches to Cooperative Game Theory
 7.5 Applications
  7.5.1 Coalitions in Communication Networks
  7.5.2 Coalitions in the Electricity Grid
  7.5.3 Core-Selecting Auctions
 7.6 Research Directions

Bibliography
Authors' Biographies
Index