6 EC
Semester 1, period 2
5082FMAS6Y
A multi-agent system (MAS) is a system consisting of several autonomous entities, called agents, that interact with each other. This interaction can take many different forms: from the agents working on their own individual interests (competition) to them making collective decisions (e.g., voting or sharing goods). As such, MASs can be studied from many different perspectives. For example, while competitive interaction is paradigmatically studied in game theory, collective decision making is the main subject of (computational) social choice. Logical frameworks have been also developed for reasoning about MASs with the provided tools allowing us not only to represent diverse attitudes towards information (e.g., knowledge, beliefs, preferences and intentions, both for individuals and for groups) but also to represent the diverse actions that affect them (e.g., several forms of inference, different types of communication).
This course introduces basic tools for formal representations of interaction in MASs.
1. Game theory.
Non-cooperative game theory: games in normal form and in extensive form. Basic solution concepts in both cases (e.g., Nash equilibrium, backward induction).
2. Computational social choice.
Basics of voting (i.e., preference aggregation) and fair division (i.e., how to share divisible items).
3. Logical foundations.
Logics for representing preferences, and their use in describing solution concepts in game theory. Logics for coalitions and their use in describing group capabilities.
F. R. Velázquez-Quesada. Lecture notes on theoretical foundations of multi-agent systems. Current version available from http://bit.ly/2zivP19, 2018.
Optional: Yoav Shoham and Kevin Leyton-Brown. Multiagent Systems. Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2009. Available online from http://www.masfoundations.org/download.html
Complementary.
* For the whole course: Michael Wooldridge, 'An Introduction to MultiAgent Systems' (2nd edition), Wiley, 2009. ISBN 978-0-470-51946-2.
http://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/imas/IMAS2e.html
* For game theory: K. Leyton-Brown and Y. Shoham. Essentials of Game Theory: A Concise Multidisciplinary Introduction. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2008. ISBN 978-1-598-29593-1. doi: 10.2200/S00108ED1V01Y200802AIM003.
* For computational social choice: F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors. 'Handbook of Computational Social Choice'. Cambridge University Press, USA, 2016. ISBN 978-1-107-06043-2.
Additional material will be posted online before its discussion. When available, slides will be posted online after the lecture.
By the end of the course, the student should be able to:
The course consists only of lectures (hoorcolleges). Some examples and exercises will be discussed during the lectures, but the students are expected to work on most of them on their own (homeworks).
Programme's requirements concerning attendance (OER-B):
| Item and weight | Details |
|
Final grade | |
|
50% Tentamen | Must be ≥ 5.5 |
|
50% Homeworks average | Must be ≥ 5.5 |
Students have to hand in the answers to homework exercises (typed in LaTeX and submitted electronically), which together will contribute to 50% of the final grade. A final exam will contribute to the remaining 50%. IMPORTANT: in order to approve the course, the student should get an approval grade (greater or equal than 5,5) for *both* (i) the average of the homeworks and (ii) the final exam.
Contact the course coordinator to make an appointment for inspection.
The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl
| Monday 29 of October |
1st session on game theory •Plan: presentation of the course, normal-form games, best response, Nash equilibrium |
| Tuesday 30 of October |
2nd session on game theory •Plan: domination, Pareto domination and Pareto efficiency. •Homework #1; will be posted at the end of the session. |
| Monday 5 of November |
3rd session on game theory •Plan: extensive games, from extensive games to normal form games, backward induction. •Homework #1; should be submitted before the beginning of the session. |
| Tuesday 6 of November |
4th session on game theory •Plan: from normal-form games to extensive games, imperfect information, strategies under imperfect information. •Homework #2; will be posted at the end of the session |
| Monday 12 of November |
1st session on computational social choice •Plan: brief introduction to computational social choice, some voting rules and their drawbacks. •Homework #2; should be submitted before the beginning of the session. |
| Tuesday 13 of November |
2nd session on computational social choice •Plan: requirements for voting rules, impossibility results and ways to go around them. •Homework #3; will be posted at the end of the session |
| Monday 19 of November |
3rd session on computational social choice •Plan: basics of fair division, utility vectors, collective utility functions and their derived ordering, requirements over this ordering. •Homework #3; should be submitted before the beginning of the session |
| Tuesday 20 of November |
4th session on computational social choice •Plan: two more basic requirements (proportionality and envy-freeness), actual cake cutting methods. •Homework #4; will be posted at the end of the session |
| Monday 26 of November |
1st session on logical foundations •Plan: modal logic and basic preference logic. •Homework #4; should be submitted before the beginning of the session |
| Tuesday 27 of November |
2nd session on logical foundations •Plan: encoding normal-form games, characterising best responses, characterising domination. •Homework #5; will be posted at the end of the session |
| Monday 3 of December |
3rd session on logical foundations •Plan: preference change. •Homework #5; should be submitted before the beginning of the session |
| Tuesday 4 of December |
4th session on logical foundations •Plan: logic for coalitional abilities. •Homework #6; will be posted at the end of the session. |
| Monday 10 of December |
5th session on logical foundations∗ •Plan: temporal extensions of coalition logic. •Homework #6; should be submitted before the beginning of the session. |
| Tuesday 11 of December | Summary session |
| Tuesday 18 of December | Exam |
| Monday 25 of February | Retake exam |
The schedule for this course is published on DataNose.