Tutorial | Presented by |
---|---|
Multi-Agent Reinforcement Learning and Dynamics of Learning | Daan Bloembergen (University of Liverpool) |
Automated Security Analysis for Multi-agent Systems | Alessandro Bruni and Carsten Schürmann (IT University of Copenhagen) |
Cooperative Games in Structured Environments | Georgios Chalkiadakis (Technical University of Crete), Gianluigi Greco (University of Calabria), Evangelos Markakis (Athens University of Economics and Business) |
Constraints and Changes in Argumentation: State of the Art and Challenges of Argumentation Dynamics | Sylvie Doutre and Jean-Guy Mailly (Université Toulouse 1 Capitole – IRIT / Université Paris Descartes – LIPADE) |
Game Theory | Ulle Endriss (University of Amsterdam) |
Assignment Problems: From Classical Mechanism Design to Multi-Agent Systems | Aris Filos-Ratsikas (University of Oxford) |
Introduction to Judgment Aggregation | Umberto Grandi (Université Toulouse 1 Capitole - IRIT) |
Probabilistic Model Checking | Marta Kwiatkowska (University of Oxford) |
Specification and Verification of Multi-Agent Systems | Wojciech Penczek and Michal Knapik (Polish Academy of Sciences) |
Dynamic epistemic logic and its applications to plan/protocol synthesis | Sophie Pinchinat (Université de Rennes) and François Schwarzentruber (École normale supérieure de Rennes) |
Modelling and Analysis of Cyber-Social Systems | Christian W. Probst (Technical University of Denmark) |
Predicting Human Decision-Making: Tools of the Trade (EurAI lecture) | Ariel Rosenfeld (Bar-Ilan University) |
Engineering Machine Ethics | Marija Slavkovik (University of Bergen) |
Decision Making for Artificial Intelligence | Paolo Turrini (Imperial College London) |
Topics Covered:
- The classical literature on one-sided matching, originating from the influential paper by Hylland and Zeckhauser
- I will talk about normative properties such as ex-ante and ex-post Pareto efficiency, ordinal efficiency, weak and strong strategyproofness, anonymity, neutrality, non-bossiness and envy- freeness.
- I will cover the best-known mechanisms, i.e. Random Priority, Probabilistic Serial and the Pseudo-market mechanism and explain which properties the satisfy and which ones they don’t.
- I will talk about structural results, such as Svensson’s characterization, Zhou’s impossibility, the characterizations of Probabilistic Serial and ordinal efficiency and the more recent characterization of ordinal randomized strategyproof mechanisms.
- Computational Results in Computer Science
- I will talk about several computational results regarding those classical mechanisms, such as the complexity of manipulating Probabilistic Serial, the computational complexity of Random Serial dictatorship
- Quantitative approaches in Computer Science
- I will talk about the maximization of the utilitarian and the egalitarian welfare by several classes of matching mechanisms for unrestricted domains and metric spaces, presenting results from and other related sources.
- I will talk about the Price of Anarchy of one-sided matching mechanisms for the utilitarian objective
- Assignment in practice
- I will cover several real-life applications of assignment mechanisms such as school choice and kidney exchange programs
Aris Filos-Ratsikas is a post-doctoral Research Assistant at the University of Oxford. He received his PhD in Theoretical Computer Science in August 2015 from the University of Aarhus, and his work is primarily on social choice, assignment problems, markets and fair division.
Topics Covered:
- Overview of public and private key cryptography, hash functions and signature schemes.
- Models for security: the symbolic (Dolev-Yao) and the computational(semantic) approaches.
- Security properties: secrecy, authentication, indistinguishability.
- Symbolical modeling of security protocols: representing security protocols as inference rules.
- Automated reasoning of security in the symbolic model with tool support.
and some of the subtleties that make automated reasoning about security a hard problem will be presented, to give a taste to the audience.
Alessandro Bruni is Assistant Professor at the IT University of Copenhagen focusing on formal methods applied to computer security, including logic and language based approaches to reasoning about security, and the construction of secure software systems. He received his Ph.D. at the Technical University of Denmark in 2015 with a thesis on the Analysis of Security Protocols in Embedded Systems. Teaching experience: Alessandro has taught security protocol analysis as part of the Critical Systems Seminar class at the IT-University of Copenhagen.
Topics Covered:
- Short introduction to abstract argumentation.
- Review of existing approaches for argumentation dynamics.
- Typology of constraints and changes in argumentation.
- Open questions and concluding remarks.
Sylvie Doutre received a Ph.D. in computer science in 2002 from Univ. of Toulouse
(France), entitled “On the preferred semantics of argumentation frameworks”. From June 2004 to August 2005, Sylvie Doutre worked as a postdoctoral researcher at the University of Liverpool (United Kingdom), in the “Agent Applications, Research and Technology” group. Since September 2005, Sylvie Doutre is an Associate Professor at the Univ. of Toulouse 1, member of the “Logic, Interaction, Language, and Computation” group at IRIT. Her research interests mainly concern argumentation-based reasoning, on its modelling and algorithmic aspects, and on its applications to agents’ interactions.
At the same time, in many real-world settings, the structure of the environment constrains the formation of coalitions among agents. These settings can be represented by coalitional games equipped with interaction graphs, that restrict agent interactions. An interaction graph determines the set of all feasible coalitions, in that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected.
Such structure in the environment opens up possibilities for the efficient computation of key game-theoretic solution concepts, in conjunction with expressive game representation mechanisms. Given this, there has been recently much work on studying cooperation and cooperative games in such settings. The aim of this tutorial is to provide (a) an extensive review these approaches, and (b) intuitions and technical insight on key results in this domain. Cooperation and cooperative games has always been at the very core of multiagent systems research. Papers on cooperative games have been prominent in past AAMAS, EUMAS, and sister conferences.
Topics Covered:
- Cooperative games and their computational aspects
- basic models and concepts
- basic solution concepts
- representation schemes (induced subgraph games, marginal contribution nets)
- key problems (e.g., coalition structure generation)
- extensions and application domains
- Cooperative games with restricted agent interactions (coalitional games over graphs)
- interaction graph structures of interest
- compact coalitional games
- computing solution concepts over graphs: algorithms and complexity
- coalition structure generation on coalitional games over graphs
- related applications (e.g., cooperative task execution, calculating the cost of journeys in the “ridesharing” domain)
- extensions (games with uncertainty, partition function games)
Georgios Chalkiadakis is an Associate Professor at the School of Electical and Computer Engineering, Technical University of Crete (TUC). His research interests are in the areas of multiagent systems, algorithmic game theory, and learning; and more specifically, in coalition formation, decision making under uncertainty, and reinforcement learning in multiagent domains. His PhD thesis (University of Toronto, 2007) was nominated for the IFAAMAS-2007 Victor Lesser Distinguished Dissertation Award. Georgios is the co-author of the graduate level textbook “Computational Aspects of Cooperative Game Theory” (with Michael Wooldridge and Edith Elkind). Before joining TUC, he was a Research Fellow at the School of Electronics and Computer Science, University of Southampton, UK; and has also worked as a software engineer at the Institute of Computer Science of the Foundation for Research and Technology – Hellas, and as a teacher of informatics in Greek high schools. Georgios has served in the Organizing Committee of several workshops in top AI and MAS international conferences; and has organised and chaired two AI/MAS summer schools.
This course, based on Russel and Norvig’s classic AI textbook, is an introductory exploration of the most fundamental aspects of agent-based decision-making which are relevant to AI practice. Agents are mathematical entities which live in an unknown environment and are guided towards the realisation of personal objectives, e.g., reaching a given terminal state. An agent is endowed with a representation of the environment and an action repertoire at each state. The environment is unknown, stochastic, and evolves following some rules that might be unknown to the agent, as well. The task is to take the best possible decision that can be taken given the (incomplete) information available. This simple model is the basis of a number of important achievements in AI, and combines the use of logical reasoning, probabilistic reasoning and sequential decision-making.
Topics Covered:
In Part 1 I will introduce the concept of decision-making agent, which will be equipped with the capacity to make probabilistic inferences about the world around. I will recall the basics of probabilistic reasoning and add a treatment of utility and how to incorporate them in decision-making, focussing on the principle of maximisation of expected utility, revisiting the examples and drawing conclusions on the best actions to take.
Part 2 will introduce sequential decision-making, focussing on stochastic actions, i.e., actions upon which the agent has no full control. I will show how to calculate the expected utility of a plan, introducing the agent’s value of time (or patience), i.e., how much they value a reward today with respect to the same reward tomorrow.
Part 2 will introduce sequential decision-making, focussing on stochastic actions, i.e., actions upon which the agent has no full control. I will show how to calculate the expected utility of a plan, introducing the agent’s value of time (or patience), i.e., how much they value a reward today with respect to the same reward tomorrow.
Part 3 will introduce Markov Decision Processes (MDPs), a widely used framework to reason about decisions in time. MDPs will be systems in which agents will have to take decisions in time, calculating the effect of policies, choices of stochastic actions at each decision point, given their patience. Policies’ properties will be discussed, together with a method for finding the optimal one: the Value Iteration Algorithm.
Finally, Part 4 will introduce the very basics of reinforcement learning, discussing how the agent can use probabilistic inference to take decisions in an environment that can only be partially explored.
Level and Prerequisites
Introductory.
I received my PhD from Utrecht University in 2011, with a thesis on Logic and Games. In 2011 I moved to the Computer Science and Communication Unit of the University of Luxembourg, where I was awarded a COFUND Marie Curie fellowship, on a project on Cooperation and Multi Agent Systems. In 2013 I moved to the Department of Computing, Imperial College London, where I was awarded a Marie Curie IEF fellowship, on a project on norms and the regulation of Multi Agent Systems. In 2015 I was awarded an Imperial College Research Fellowship, on a project on negotiation and distributed Artificial Intelligence.
Overall, I have published 10 journal papers, 14 conference papers, five workshop papers and one book chapter in the field of Artificial Intelligence, together with a forth- coming entry on Logic and Games Theory in the Stanford Encyclopedia of Philosophy.
We introduce dynamic epistemic logic (DEL) and its natural extension with fix-points and describe how it naturally captures information change triggered by the occurrence events in a multi-agent system. The usefulness of this logic is illustrated by many examples supported by a demo tool called “Hintikka’s world (people.irisa.fr/Francois.Schwarzentruber/hintikkasworld/), that the students will also use. In particular, we will show how so-called planning and protocol synthesis problems, widely investigated in the literature, can be expressed in DEL. We will also present a symbolic representation of DEL models.Then, the two classic decision problems of satisfiability and model-checking of DEL are investigated. (a) In a first stage, the fix-point-free fragment of the logic is considered. (b) In a second stage, the decidability of fix-points formulas for safety and reachability properties is investigated with two main tools. The first tool relies on the expressive power of DEL to describe the executions of powerful machines (such as Turing machines, pushdown automata, queue automata). The second tool stems from an accurate analysis of the infinite structure induced by the model-checked formula and their connections with well-known classes of infinite structures, typically the one of automatic structures by Blumensath and Grädel.
Topics Covered:
- Dynamic epistemic logic.
- Decision problems for DEL without fix-points: model-checking and satisfiability.
- Decision problems for DEL with fix-points: safety and reachability properties.
- Dynamic epistemic structures, automatic structures.
- Application to plan/protocol synthesis.
Sophie Pinchinat is a full professor at the University of Rennes 1 and a collaborator of ENS Rennes. She is the head of the research team LogicA (Logic and Applications) at the IRISA/INRIA Laboratory. Her research interests range between logic, automata and games; imperfect information, knowledge, uncertainty situations; synthesis problems; supervisory control theory. She has a long term experience in teaching logic, automata and games for the verification and the synthesis of interacting systems. She serves the editorial board of the international journal Discrete-event Dynamical Systems and the Program Committees of several international conferences such as CSL, FSTTCS, TARK, GandALF. She also often reviews articles submitted to Studia Logica, Fundamentae Informatica, Information and Computation and IEEE Transactions on Automatic Control. See http://people.irisa.fr/Sophie.Pinchinat/ for further details.
Topics Covered:
- A very brief introduction to moral philosophy.
- Introduction to machine ethics, motivation and scope.
- Overview of the Moor classification of the types of artificial moral agents.
- Top-down and bottom up approaches to engineering ethical reasoning with examples of implemented systems.
- The context impact of machine ethics.
- The dark side of machine ethics, building deliberately unethical systems.
Marija Slavkovik is a postdoctoral fellow at the University of Bergen since 2013 where she conducts research on collective reasoning and decision making methods for artificial intelligence. Marija obtained her doctoral degree from the University of Luxembourg with a dissertation on “Judgment Aggregation for Multi-Agent Systems” in 2012, after which she spent a year as a postdoc in the Department of Computer Science at the University of Liverpool. It is there that she got involved with machine ethics project. She has since been very active in building a network of machine ethics researchers interested in this area. She is in the program committees of, among others, ECAI’17, IJCAI’17, AAAI’17, LOFT’17. She was the student session chair of ESSLLI’10 and a coordinator for the Dagstuhl seminar 16222 on Judgment Aggregation for Artificial Intelligence.
Topics Covered:
- Strategic Games
- normal-form games, pure and mixed strategies
- solution concepts, particularly Nash equilibrium
- extensions and variants (e.g., congestion games, Bayesian games)
- Mechanism Design
- basic auction theory
- Vickrey-Clarke-Groves mechanisms
Ulle Endriss is Associate Professor of Artificial Intelligence at the Institute for Logic, Language and Computation (ILLC) at the University of Amsterdam. His research concerns the design and analysis of methods for collective decision making. He regularly publishes in the leading conferences and journals in his field, received the Best Paper Award at AAMAS on two occasions, and is an editor of the Handbook of Computational Social Choice published in 2016. He currently serves as an elected member of the Board of Directors of IFAAMAS as well as an Associate Editor of the journals JAAMAS, AIJ and JAIR.
Topics Covered:
- Short introduction to computational social choice. Historical introduction to judgment aggregation : from legal theory, to social choice theory, to multi-agent systems
- A unified setting for paradoxes of aggregation: binary aggregation with integrity constraints
- Mini-tutorial on computational complexity (depending on the audience)
- Computational complexity of winner determination for judgement aggregation rules
- Impossibility results and winning coalitions in formula-based judgment aggregation
- Strategic manipulation: where do preferences come from, individual strategic voting, external control and lobbying in multiple referenda
- Overview of applications and related problems: collective annotation for corpora, crowdsourcing, multiagent argumentation, opinion diffusion on networks
Umberto Grandi is assistant professor at the University of Toulouse 1 Capitole, and a member of the research group in Logic, Interaction, Language and Computation at the Institut de Recherche en Informatique de Toulouse (IRIT) since 2014. He obtained his PhD at the University of Amsterdam in 2012 under the supervision of Ulle Endriss, and he joined IRIT after a two-year postdoc at the University of Padova. His research interests are in computational social choice, more precisely the aggregation of judgments on logically correlated issues, game-theoretical studies of collective choice, and opinion diffusion on social networks.
Topics Covered:
- Socio-technical systems.
- Modelling human behaviour.
- Modelling Cyber-social systems.
- Analysing Cyber-social systems.
Christian W Probst is an associate professor and head of the section for Cyber Security at the Department of Applied Mathematics and Computer Science at the Technical University of Denmark. Christian’s research interests are in the field of IT and organisational security and he has been the technical lead of the TREsPASS project. He has developed the ExASyM model for socio-technical systems, which enables risk assessment of these systems and, eg, the identification of insider threats. Christian’s current research investigates risk assessment for cyber-social systems, where human actors are an integral part of the system.
University of Liverpool
Topics Covered:
- Reinforcement learning: Markov decision processes, value iteration, temporal difference methods, Q-learning, learning automata.
- Multi-agent learning: Markov games, independent learning, joint-action learning, gradient ascent approaches.
- Multi-agent learning dynamics: normal-form games, Nash equilibrium, evolutionary game theory, replicator dynamics, evolutionarily stable strategies.
Daan Bloembergen is a postdoctoral research associate at the University of Liverpool, UK. He graduated from Maastricht University (NL) with a M.Sc. in Artificial Intelligence in 2010 for which he earned the honor cum laude. He received his Ph.D. in May 2015, also from Maastricht University, where he worked on the project “Analyzing Multiagent Learning”, funded by the NWO (Netherlands Organisation for Scientific Research). His current research interests are studying the learning dynamics of multi-agent systems in general and multi-agent reinforcement learning and the relation to evolutionary game theory in particular. He has published on this topic in several journals and conferences among which JAIR, AAMAS, ECAI, and AAAI.
Topics Covered:
- Motivation and examples: Agents for human rehabilitation, human-robot inter- action, automated advice provision, argumentation, security, negotiation etc.
- The basics of human decision-making: decision theory and game theory, bounded rationality, historical and contemporary computational models of human behavior from behavioral economics, cognitive psychology and AI. Experimental evidence for human decision-making and behavior and they are different from what we usually consider to be rational.
- Tools of the trade: Normative vs. descriptive approaches for predicting human decision-making, computational models and the integration of normative theories from different disciplines (e.g., social science and economics) to enhance classic prediction methods.
- From prediction to action: combining human decision-making prediction methods in the design of intelligent agents that interact proficiently with people. Frameworks, methodologies and applications to security, games, argumentation, advice provision, rehabilitation, human-robot interaction, personal assistants and negotiation.
- Additional topics and challenges: implicit vs. explicit interaction settings, enhancing prediction capabilities using additional modalities (e.g., facial expressions), transfer learning of decision policies across domains and people, the complexity of acquiring (reliable) human data, minority cases in human-generated data.
Ariel Rosenfeld is currently completing his PhD in Computer Science at Bar-Ilan University, Israel. He obtained a BSc in Computer Science and Economics, graduated ‘magna cum laude’, from Tel-Aviv University, Israel. Rosenfeld’s research focus is Human-Agent Interaction and he has published on the topic at top venues such as AAAI, IJCAI, AAMAS and ECAI. Rosenfeld has a rich lecturing background, span- ning over a decade, and he is currently acting as a lecturer at Bar-Ilan University and in Ben-Gurion University, Israel.
Topics Covered:
- Discrete-time Markov chains. Probabilistic logic PCTL with rewards. PCTL model checking for Markov chains. Case study: Bluetooth protocol.
- Markov decision processes (MDPs), PCTL model checking for MDPs. Strategy synthesis from PCTL. Case study: Firewire protocol.
- Automata-theoretic techniques for model checking. Buchi and Rabin automata.LTL model checking for DTMCs and MDPs.
- Multiobjective LTL model checking for MDPs. Multiobjective strategy synthesis. Stochastic games. Case study: Robot planning.
The course aims at enhancing students knowledge and skills connecting logical theories of computational systems with practical applications.
Topics Covered:
- Introduction to specification and verification of MAS
- Modal logic: modal operators, possible worlds semantics. Modal logic as a generic framework to model and reason about MAS. Reasoning about knowledge: basic multi-agent epistemic logic. Common knowledge and distributed knowledge. Decision problems. Formal verification by model checking. Some complexity classes. Model checking epistemic properties. Example domains: robots on a rescue mission, security of e-voting.
- Reasoning about dynamics of systems
- Temporal logic. Linear vs. branching time. Linear time logic: LTL. Branching-time logic: CTL. Specification of dynamics: robots, voting. Combining modalities: logics of knowledge and time. CTL+Knowledge. Standard non-symbolic algorithms of model checking and basic complexity results.
- Verification of strategic abilities. Tools and experimental results.
- Temporal logic meets game theory: alternating-time temporal logic ATL. Model checking ATL for explicit models. Tools: VERICS, MCMAS.
Wojciech Penczek is a full professor and the head of the Theory of Distributed Systems Group at the Polish Academy of Sciences. He was a research fellow at the Technical University of Eindhoven and Manchester University; he also worked as a consultant at AT&T. His research is now focused on verification methods for (timed) distributed and multi-agent systems. He has been a project leader of the EC-founded project CRIT-2 and played a main role in several national projects. He has chaired and was a PC member of many conferences on Computer Science. He is the author of more than 100 conference and journal articles on temporal logic, verification methods, model checking, and formal theories of multi-agent systems. His teaching record, besides numerous regular undergraduate courses, includes one course at ESSLLI (2010) and two courses at EASSS (European Agent Systems Summer School).