Cooperative Game Theory & its Application to Multi-Agent Systems
Lecturer:
Dr. Talal Rahwan
(University of Southampton, UK).
About the lecturer | Course Summary | Slides: All (pdf) Updated (pptx) |Assignment (deadline 10 July 2012)
About the lecturer:
Dr. Talal Rahwan graduated from the Department of Information Technology at the University of Aleppo in Syria, where he has been awarded Al-Basel Presidential Award for Academic Achievement (presented annually to students ranked 1st in each department at Syrian Universities). He was then awarded an Overseas Research Scholarship to do his Ph.D. at the School of Electronics and Computer Science at the University of Southampton (which is ranked 2nd in the UK for the Quality of its research). In 2007, Dr. Rahwan received the British Computer Society’s Distinguished Dissertation Award, which is annually presented to the best British Ph.D. in computer science. In 2010, he was selected by the IEEE Computer Society as one of the top 10 young Artificial Intelligence researcher in the world. He is currently a senior research fellow at the University of Southampton. His research has been published at prestigious Artificial Intelligence conferences and journals, including AAAI, IJCAI, ECAI, AAMAS, ACM-EC, JAIR and AIJ.
Course summary: Multi-agent systems are a new paradigm for understanding and building distributed systems, where it is assumed that the computational components are (1) autonomous: able to control their own behaviour in the furtherance of their own goals, and (2) social, i.e., they interact with each other. In many such systems, agents can improve their performance by working together, i.e., forming coalitions. This holds both for cooperative agents, i.e., agents who share a common set of goals, and for selfish agents who only care about their own reward. For cooperative agents, to find an optimal collaboration pattern, it suffices to identify the best way of splitting agents into coalitions. In contrast, when the agents are selfish, we also have to specify how to divide the rewards from cooperation, since each agent needs to be incentivized to participate in the proposed coalition.
In this course, we discuss coalition formation in multi-agent systems for both selfish and cooperative agents. To deal with selfish agents, we introduce classic solution concepts of coalitional game theory that capture the notions of stability and fairness in coalition formation settings. We then give an overview of existing representation formalisms for coalitional games. For each such formalism, we discuss the complexity of computing the solution concepts, focusing on algorithms whose running time is polynomial in the number of agents. In the second half of the course, we focus on practical approaches for finding an optimal partition of agents into teams. We present the state-of-the art algorithms for this problem, and compare their relative strengths and weaknesses.