Viðburðadagatal tölvunarfræðideildar

ICE-TCS seminar: Venanzio Capretta

The Effectivity of Coalitions in Games

  • 18.8.2019, 11:50 - 12:35


ICE-TCS seminar #336

Date and time: Monday, 19 August 2019, 11:50-12:35
Location: Room M106
Speaker:  Venanzio Capretta, University of Nottingham, http://www.cs.nott.ac.uk/~pszvc/

Title: The Effectivity of Coalitions in Games

"Coalition Logic" studies how a group of agents in a multi-player game can collaborate to achieve a common goal. It was introduced by Marc Pauly in 2002 (``A modal logic for coalitional power in games'') who defined its semantics and axiomatic system. We started studying the topic with the goal to give a constructive account and formalize it using the proof assistants Coq and Agda. We discovered that a main result about the representability of the effective power of a coalition can be considerably simplified with a different proof than the one given originally by Pauly. In the talk I will define the notion of multi-player "game form": a setting in which several agents play simultaneously and the outcome depends on the global "strategy profile". Given such a game and a coalition, a group of agents, we can define what sets of outcomes the coalition can achieve by working together. This determines an "effectivity function" that maps each coalition to sets of goals, where a goal is a set of outcomes.These effectivity functions satisfy a list of properties, collectively called "playability". If, independently of any game, we consider a function satisfying these playability properties, we may ask whether there is a game that realizes it. Pauly gives a construction of a game that represent a playable effectivity function, using a complex well-founded sequence of partitions, each requiring the use of choice principles.I will explain our simpler representation result, which construct a more intuitive game in a constructive way.
This is joint work with Colm Baston.