Summary: Multi-agent Systems (MAS)
After completing the course, the student
Knows the main concepts and abstractions that are used in multi-agent systems (e.g., autonomous agents, environment,
interaction, knowledge, preference, strategy, protocol).
Is acquainted with the theoretical aspects and problems of multi-agent systems (e.g., preference modelling, interaction analysis,
negotiation, communication, coordination).
Knows basic concepts from decision and game theory (e.g., decision rules, various equilibria, mechanism design, social choice
functions, voting mechanisms).
Is able to work with game theoretic concepts (e.g., determining different equilibria, working with different game settings such as
strategic and extensive games, determining winners of various voting mechanism and auctions).
Recognizes different applications of multi-agent systems (e.g., auctions, voting systems, automatic negotiation systems).
Has insight into the strengths and weaknesses of multi-agent systems (e.g., distributed nature of multiagent systems, impossibility
results from game theory and its relevance for multi-agent systems).
Recognizes the interdisciplinary nature of multi-agent systems (e.g., the relations between multi-agent systems with social
sciences, psychology, and economy).
Basic concepts
Lecture 1: Introduction
Lecture 2: Game Theory (part 1)
Lecture 3: Game Theory (part 2)
Lecture 4: Extensive games
Lecture 5: Games and Communication
Lecture 6: Coalitional Theory
Lecture 7: Aggregating Preferences & Social Choice
Lecture 8: Mechanism Design
Lecture 9: Auctions
Exercises
-
Basic concepts Column & row:
Column:
, Row: Autonomous agents sense their environments, learn and reason
to decide and execute actions that maximize the chance to
Normal form games vs. extensive form games: successfully achieve their objectives.
In an extensive-form game, actions are taken in succession. In a
normal-form game actions are taken simultaneously.
Extensive-form game Normal-form game
Autonomous agents are:
Common-payoff games: 1. Pro-active: deliberative/goal-directed behaviors.
Games in which, for every action profile, all players have the -> react and respond to (all) the possibilities and try to find the
same payoff (also know as: pure coordination games or team best outcome.
games). 2. Adaptive: changing its behavior based on experience.
3. Reactive: respond to changes in its environment.
In such games the agents have no conflicting interests; their sole 4. Rational: behaves to maximize its achievements.
challenge is to coordinate on an action that is maximally -> there are different types of rationality, this course focuses
beneficial to all. on economical rationality.
Example: -> economical rationality: when you make a choice, you will
choose the thing you like best.
5. Social: capable of interacting and communicating with other
agents.
Symmetric game: The difference between probabilistic and stochastic is
A game in which if player 1 plays that probabilistic is (mathematics) of, pertaining to or derived
strategy A and player 2 plays strategy using probability while stochastic is random, randomly
B, player 1’s payoff is the same as determined, relating to stochastic.
player 2’s payoff if player 1 were to
instead play B and player 2 were to Multi-agent systems
instead play A and vice versa. A multi-agent system consists of a set of autonomous agents that
interact with each other and their surrounding environment to
Zero-sum games: achieve their (joint) objectives.
Also know as constant-sum games or strictly competitive.
Zero sum game is a game in which the sum of all player’s payoffs Coordination aims at avoiding extraneous activities by
equals zero for every outcome. synchronising and aligning agents activities:
* Cooperation: agents’ can cooperate to solve their problems
A two-player normal-form game is constant sum if there exists a (e.g. task sharing, results sharing).
constant c such that for each strategy profile a ∈ A1 × A2 it is the * Organisation: organisation aims at arranging and managing
case that u1(a) + u2(a) = c. the agents’ interaction (e.g. marketplaces).
* Negotiation: agents negotiate to reach agreements (e.g.
It is called zero-sum because, when not clarified, it is assumed auction bidding, argumentation to convince each other to
that, c = 0, that is, that we have a zero-sum game. agree on an outcome).
Zero-sum games represent situations of pure competition; one In a multi-agent environment, the effect of your decision is also
player’s gain must come at the expense of the other player. affected by other agents decisions.
-> example: an agent opens a door, then another agent closes
Example: the door. Even though the first agent opened the door, the
state of the door right now is closed.
Symmetric zero sum game:
Theorem: in finite, two player, symmetric, zero sum games, each
player’s equilibrium expected utility must be equal to zero.
Note!: equilibrium implies payoffs of 0, not payoffs of 0 imply
equilibrium!
Lecture 1 (Introduction)
Lecture 2 (Game Theory: part 1)
(Individual) autonomous agents Game theory is the mathematical study of interaction among
independent, self interested agents.
