Multi-Agent Systems
Period 2 | 2023-2024
,Game theory
Game theory studies multi-agent decision problems, that is, problems in which
independent decision-makers interact. What each agent does has an effect on the other
agents in the group (through utility). Assumptions:
● pay-off: agents have preferences encoded in utility function
● self-interest: agents strive to maximize their own pay-off
● rational behavior: agents reason about the actions of other agents and decide
rationally
Non-cooperative Cooperative (coalitional)
● Selfish individuals: only consider their own ● Teams
interest ● Binding commitments (“contracts”) allow
● Do not coordinate their actions in groups: groups of players to coordinate their actions
coordination might happen as “accident” of
selfish behavior
● Agreements need to be self-enforcing (no
“contracts”!)
Examples: matrix games, sequential games Examples: Shapley value
(bargaining)
Simultaneous Sequential
● Players make their moves simultaneously, ● Sequence of successive moves by players
without knowing what the other players will who can see each other’s moves
do! ● E.g. Chess, card games, open cry auctions
● E.g. Rock-paper-scissors, sealed bid
auctions
Pure strategy Mixed strategy
Select a single action and play it. Select a single action according to probability
distribution and play it.
Advantage: Introducing randomness can help
prevent opponents from gaining a strategic
advantage by exploiting patterns in the player's
choices.
Agent i plays strategy si which is a
probability distribution over k possible actions:
Utility
A mapping from states of the world to real numbers. These numbers are interpreted as
measures of an agent’s level of happiness in the given states.
1
, Encoding utilities of action
Normal form (matrix) Extensive form (decision tree)
Examples of games
Cournot’s Duopoly model
Two companies make an interchangeable product (e.g. bottled water). Without knowing the
other company’s strategy (i.e. simultaneously), both need to determine the quantity they will
produce, say q1 and q2 respectively. The unit price p of the product in the market depends on
the total produced quantity q1 + q2; specifically:
Stackelberg Duopoly model
Two companies make an interchangeable product (e.g. bottled water). One firm becomes
the leader and so makes the first move (i.e. sequential). The other firm is the follower and
can observe (and therefore react to) the decision of the leader.
2
,Zero- (or constant) sum game
My gain is your loss. Thus, cutting a cake, where taking a more significant piece reduces the
amount of cake available for others as much as it increases the amount available for that
taker, is a zero-sum game if all participants value each unit of cake equally. In a zero-sum
game, the combined pay-offs of a solution amount to zero.
Hotelling's Game
You are on the beach and the interval represents the beach. Two ice keep vendors have a
place on the beach. People in the green part will go to vendor x and people in the red part to
vendor y. The best solution is that both stay next to each other in the middle (so that one
3
,vendor has the left half and the other vendor the right half).
Tragedy of the commons
A common resource or "commons" is any resource, such as water or land, that provides
users with tangible benefits but which nobody has an exclusive claim. The tragedy of the
commons is an economic problem where the individual consumes a resource at the expense
of society. If an individual acts in their best interest, it can result in harmful over-consumption
to the detriment of all. This phenomenon may result in under-investment and total depletion
of a shared resource.
Public goods game
Subjects secretly choose how many of their private tokens to put into a public pot. The
tokens in this pot are multiplied by a factor (greater than one and less than the number of
players, N) and this "public good" payoff is evenly divided among players. Each subject also
keeps the tokens they do not contribute.
Traveller’s dilemma
Airline severely damages identical antiques purchased by two different travelers.
Management is willing to compensate them for the loss of the antiques, but since they have
no idea about their value, they tell the two travelers to separately write down their estimate of
the value as any number between $2 and $100 without conferring with one another. If both
travelers write down the same number, they will be reimbursed that amount. If they write
different numbers, management will pay both of them the lower figure, the person with the
4
, lower number will get a $2 bonus for honesty, while the one who wrote the higher number
will get a $2 penalty.
Social dilemmas
Actions taken independently by individuals in pursuit of their own private objectives result in
an inferior outcome compared to what could have been achieved if people had acted
together (cooperation), i.e. individual utility does not align with the social utility.
No greed (0<T<1) Greed (1>T>2)
No fear (S>0) Harmony Snowdrift volunteer
Fear (S<0) Stag Hunt Prisoner's dilemma
Prisoner’s dilemma
Two suspects in a crime are put into separate cells. The police officer tells them: Currently
you’re charged with trespassing which carries a jail sentence of one month. I know you were
planning a robbery though, but cannot prove it – I need your testimony. If you confess, I will
drop the charges against you, but your partner will be charged to the fullest extent of the law:
12 months in jail. I’m offering the same deal to him. If you both confess, your individual
testimony is less valuable, and you will get 8 months each.
C=quiet D=confess
quiet R = 1, R = 1 S = -12, T = 2
confess T = 2, S = -12 P = 0, P = 0
Stag Hunt Game (Common Interest Game)
Two hunters know that a stag (=hert) follows a certain path. If two hunters cooperate to kill
the stag there’s plenty to eat. The hunters hide and wait for a long time, alas with no sign of
the stag. However, a hare (=haas) is spotted by all hunters. If a hunter shoots the hare, he
will eat, but the stag will be alarmed and flee, and the other hunter will go hungry. If both
hunters kill the hare, they share the little there is.
stag hare
stag R = 10, R = 10 S = 0, T = 4
hare T = 4, S = 0 P = 2, P = 2
5
Period 2 | 2023-2024
,Game theory
Game theory studies multi-agent decision problems, that is, problems in which
independent decision-makers interact. What each agent does has an effect on the other
agents in the group (through utility). Assumptions:
● pay-off: agents have preferences encoded in utility function
● self-interest: agents strive to maximize their own pay-off
● rational behavior: agents reason about the actions of other agents and decide
rationally
Non-cooperative Cooperative (coalitional)
● Selfish individuals: only consider their own ● Teams
interest ● Binding commitments (“contracts”) allow
● Do not coordinate their actions in groups: groups of players to coordinate their actions
coordination might happen as “accident” of
selfish behavior
● Agreements need to be self-enforcing (no
“contracts”!)
Examples: matrix games, sequential games Examples: Shapley value
(bargaining)
Simultaneous Sequential
● Players make their moves simultaneously, ● Sequence of successive moves by players
without knowing what the other players will who can see each other’s moves
do! ● E.g. Chess, card games, open cry auctions
● E.g. Rock-paper-scissors, sealed bid
auctions
Pure strategy Mixed strategy
Select a single action and play it. Select a single action according to probability
distribution and play it.
Advantage: Introducing randomness can help
prevent opponents from gaining a strategic
advantage by exploiting patterns in the player's
choices.
Agent i plays strategy si which is a
probability distribution over k possible actions:
Utility
A mapping from states of the world to real numbers. These numbers are interpreted as
measures of an agent’s level of happiness in the given states.
1
, Encoding utilities of action
Normal form (matrix) Extensive form (decision tree)
Examples of games
Cournot’s Duopoly model
Two companies make an interchangeable product (e.g. bottled water). Without knowing the
other company’s strategy (i.e. simultaneously), both need to determine the quantity they will
produce, say q1 and q2 respectively. The unit price p of the product in the market depends on
the total produced quantity q1 + q2; specifically:
Stackelberg Duopoly model
Two companies make an interchangeable product (e.g. bottled water). One firm becomes
the leader and so makes the first move (i.e. sequential). The other firm is the follower and
can observe (and therefore react to) the decision of the leader.
2
,Zero- (or constant) sum game
My gain is your loss. Thus, cutting a cake, where taking a more significant piece reduces the
amount of cake available for others as much as it increases the amount available for that
taker, is a zero-sum game if all participants value each unit of cake equally. In a zero-sum
game, the combined pay-offs of a solution amount to zero.
Hotelling's Game
You are on the beach and the interval represents the beach. Two ice keep vendors have a
place on the beach. People in the green part will go to vendor x and people in the red part to
vendor y. The best solution is that both stay next to each other in the middle (so that one
3
,vendor has the left half and the other vendor the right half).
Tragedy of the commons
A common resource or "commons" is any resource, such as water or land, that provides
users with tangible benefits but which nobody has an exclusive claim. The tragedy of the
commons is an economic problem where the individual consumes a resource at the expense
of society. If an individual acts in their best interest, it can result in harmful over-consumption
to the detriment of all. This phenomenon may result in under-investment and total depletion
of a shared resource.
Public goods game
Subjects secretly choose how many of their private tokens to put into a public pot. The
tokens in this pot are multiplied by a factor (greater than one and less than the number of
players, N) and this "public good" payoff is evenly divided among players. Each subject also
keeps the tokens they do not contribute.
Traveller’s dilemma
Airline severely damages identical antiques purchased by two different travelers.
Management is willing to compensate them for the loss of the antiques, but since they have
no idea about their value, they tell the two travelers to separately write down their estimate of
the value as any number between $2 and $100 without conferring with one another. If both
travelers write down the same number, they will be reimbursed that amount. If they write
different numbers, management will pay both of them the lower figure, the person with the
4
, lower number will get a $2 bonus for honesty, while the one who wrote the higher number
will get a $2 penalty.
Social dilemmas
Actions taken independently by individuals in pursuit of their own private objectives result in
an inferior outcome compared to what could have been achieved if people had acted
together (cooperation), i.e. individual utility does not align with the social utility.
No greed (0<T<1) Greed (1>T>2)
No fear (S>0) Harmony Snowdrift volunteer
Fear (S<0) Stag Hunt Prisoner's dilemma
Prisoner’s dilemma
Two suspects in a crime are put into separate cells. The police officer tells them: Currently
you’re charged with trespassing which carries a jail sentence of one month. I know you were
planning a robbery though, but cannot prove it – I need your testimony. If you confess, I will
drop the charges against you, but your partner will be charged to the fullest extent of the law:
12 months in jail. I’m offering the same deal to him. If you both confess, your individual
testimony is less valuable, and you will get 8 months each.
C=quiet D=confess
quiet R = 1, R = 1 S = -12, T = 2
confess T = 2, S = -12 P = 0, P = 0
Stag Hunt Game (Common Interest Game)
Two hunters know that a stag (=hert) follows a certain path. If two hunters cooperate to kill
the stag there’s plenty to eat. The hunters hide and wait for a long time, alas with no sign of
the stag. However, a hare (=haas) is spotted by all hunters. If a hunter shoots the hare, he
will eat, but the stag will be alarmed and flee, and the other hunter will go hungry. If both
hunters kill the hare, they share the little there is.
stag hare
stag R = 10, R = 10 S = 0, T = 4
hare T = 4, S = 0 P = 2, P = 2
5
