Tutorial on COOPERATIVE GAMES IN MULTI-AGENT SYSTEMS

Tutorial on COOPERATIVE GAMES IN MULTI-AGENT SYSTEMS

Download complete tutorial slides here.

Summary

Cooperative (or coalitional) games provide an expressive and flexible framework for modeling collaboration in multi-agent systems. However, from a computational perspective, cooperative games present a number of challenges, chief among them being how they can be succinctly represented and how to reason efficiently with such representations. In this tutorial, we survey work on several aspects of cooperative games and their applications to multi-agent systems. We assume a basic knowledge of AI principles (e.g., rule-based knowledge representation, very basic logic), but no knowledge of game theory or cooperative games. We introduce the basic models used in cooperative game theory, and the relevant solution concepts. We then describe the key computational issues surrounding such models, and survey the main approaches developed over the past decade for representing and reasoning about cooperative games in AI and computer science generally. We then discuss the aspects of cooperative games that are particularly important in multi-agent settings, such as uncertainty and decentralized coalition formation algorithms. We conclude by presenting recent applications of these ideas in multi-agent scenarios.

Syllabus

Target Audience and Prerequisites

Intended for all AAMAS delegates who want to gain an understanding of the role that the theory of cooperative games plays in multi-agent systems, the research challenges raised by the study of cooperative games, and the main approaches to addressing these challenges. We assume a basic knowledge of AI principles (eg rule-based knowledge representation, very basic logic), and basic discrete mathematics, but no knowledge of game theory or cooperative games.

About the Tutors

Edith Elkind is an Assistant Professor, Division of Mathematical Sciences, Nanyang Technological University, Singapore. She received her PhD from Princeton in 2005. After that, Edith was a postdoctoral research fellow at University of Warwick, University of Liverpool and Hebrew University of Jerusalem. Her main research interests are algorithmic game theory and computational social choice, with a particular emphasis on coalitional games. She has been a program committee member of several flagship conferences in AI, theoretical computer science and algorithmic game theory, such as AAMAS, AAAI, IJCAI, ECAI, ACM EC, COMSOC and ICALP. In 2008, Edith (jointly with Evangelos Markakis) taught a course on computational complexity in multi-agent systems at the 10th European Agent Systems Summer School (EASSS'08). She has also presented a mini-course of algorithmic game theory at University of Tartu, Estonia (Fall 2005), University of Southampton, UK (Spring 2005) and Nanyang Technological University, Singapore (Spring 2008).

Georgios Chalkiadakis is a Research Fellow in the School of Electronics and Computer Science, University of Southampton, UK. He is a member of the Intelligence, Agents and Multimedia Group, led by Professor Nicholas R. Jennings. Georgios gained his PhD in Computer Science from the University of Toronto in 2007, for work combining Bayesian reinforcement learning with game-theoretic, coalition formation-related ideas. His dissertation ("A Bayesian Approach to Multiagent Reinforcement Learning and Coalition Formation under Uncertainty") was nominated for the 2007 IFAAMAS Victor Lesser Dissertation Award. His main research interests comprise game theory and intelligent agent research--and more specifically coalitional game theory as well as reinforcement learning and decision making under uncertainty. His paper "Bayesian Reinforcement Learning for Coalition Formation under Uncertainty" (co-authored with Craig Boutilier) was a finalist for the Best Student Paper Award in AAMAS-2004; and he is a co-author of the paper "Coalition Structures in Weighted Voting Games" (joint work with Edith Elkind and Nicholas R. Jennings) which was a finalist for the Best Paper Award of the 18th European Conference on AI (ECAI-2008). Georgios was a program committee member for AAMAS-2008 and IJCAI-2009; he has years of teaching experience as a teaching assistant of CS undergraduate courses in the University of Crete and the University of Toronto, as well as a teacher of informatics in greek highschools.

Michael Wooldridge is a Professor in the Department of Computer Science at the University of Liverpool, UK. Wooldridge's main interests are in the use of formal methods for reasoning about autonomous agents and multi-agent systems, and he has published over two hundred articles in the area. Wooldridge was the recipient of the ACM Autonomous Agents Research Award in 2006. He was elected a Fellow of the British Computer Society in 2004, a Fellow of the European Association for Artificial Intelligence (ECCAI) in 2007, and a Fellow of the American Association for Artificial Intelligence (AAAI) in 2008. He has been co-editor in chief of the journal ``Autonomous Agents and Multi-Agent Systems'' (Kluwer), since 2003, and is an associate editor of JAIR -- the Journal of AI Research. Wooldridge founded AgentLink, the European Network of Excellence for agent-based computing (http://www.AgentLink.org/), and coordinated the network between 1997--2000. His introductory textbook ``An Introduction to Multiagent Systems'' was published by Wiley in 2002, (Chinese translation 2005; Greek translation 2007). His research monograph ``Reasoning about Rational Agents'' was published by The MIT Press in June 2000. Wooldridge was elected President of the International Foundation for Autonomous Agents and Multi-Agent Systems (IFAAMAS) for 2007-09.

Last modified: Wed Jul 21 09:24:56 BST 2010