Game Theory an der AKAD Hochschule Stuttgart | Karteikarten & Zusammenfassungen

Lernmaterialien für Game Theory an der AKAD Hochschule Stuttgart

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Game Theory Kurs an der AKAD Hochschule Stuttgart zu.

TESTE DEIN WISSEN

Folk Theorem (general)

Lösung anzeigen
TESTE DEIN WISSEN

• The folk theorem shows that there is a huge multiplicity of equilibria in infinitely repeated games.


• The threat of using a trigger strategy is often too strong since it suffices to punish so long that a deviation becomes unprofitable. Hence the punishment can stop after a finite time.


• The threat with a trigger strategy is often incredible.

Lösung ausblenden
TESTE DEIN WISSEN

Game without equilibrium (3)

Lösung anzeigen
TESTE DEIN WISSEN

• “Highest number wins”:
– Two players write down a number.
– The player with the higher number wins.


• This is an infinite game in which each player has infinitely many actions.


• This game has no equilibrium (neither in pure nor in mixed strategies).

Lösung ausblenden
TESTE DEIN WISSEN

How to determine mixed strategy
equilibria?

Lösung anzeigen
TESTE DEIN WISSEN

• According to the previous lemma all actions that are chosen with positive probability in a mixed strategy lead to the same utility.


• This is the key to the calculation of the mixed strategy equilibria, i.e. the determination of the actions that are chosen with positive probability and the corresponding weights.

Lösung ausblenden
TESTE DEIN WISSEN

The Exchange Game

Lösung anzeigen
TESTE DEIN WISSEN

Scenario:

Two players and two envelopes
• Both players know that envelopes may contain 5, 10, 20, 40, 80, or 160 Euro
• Both player know that one envelope contains twice the amount of the other envelope
• The two envelopes are randomly distributed to the two players
• After both players have inspected their envelopes they are asked whether they want to exchange
• Making an exchange offer costs 1
• If both agree to exchange, they exchange


Supposition:

• Suppose one player has 10 and the other 20
• Expected gain from exchange for player with 20 is ½·40 + ½·10 - 1= 24 > 20
• Expected gain from exchange for player with 10 is ½·20 + ½·5 - 1= 11.5 > 10
• Since both players profit from an exchange, they may both agree to exchange → exchange takes place

• How can it be that both agree, since, a priori it is clear that exactly one player wins from the exchange, while the other one loses?
Problem: players did not think about the strategic situation. Since both parties involved act strategically, the problem cannot be solved by shortsighted expected values, but by a strategic analysis


Strategic Analysis:
consider the border cases first. Suppose player finds 160; knows for sure that other player has 80 → does not want to exchange
⇒ player with 80 knows that he can only exchange with a player with 40→ does not want to exchange
⇒ player with 40 knows that he can only exchange with a player with 20→ does not want to exchange

⇒ player with 5 would like to exchange with 10, but knows that player with 10 does not make an offer → player with 5 saves the cost of 1 and also does not make an offer to exchange


-> Strategic analysis shows that there are no incentives for exchange, although each player ≠ 160 has a positive expected value from the exchange

Lösung ausblenden
TESTE DEIN WISSEN

Backward Induction (3)

Lösung anzeigen
TESTE DEIN WISSEN

• Backward induction is an algorithm to determine subgame perfect equilibria.


• The game tree is analyzed from backward and the equilibria of the subgames are determined.


• This is also the way to proof Zermelo’s theorem.

Lösung ausblenden
TESTE DEIN WISSEN

The 5 Voting Schemes

Lösung anzeigen
TESTE DEIN WISSEN

1) Simple majority voting: 

each voter votes for her most preferred alternative. The alternative with the highest number of votes wins.


2) Plurality runoff:

each voter votes for her most preferred alternative. The two alternatives with the highest number of votes go to a second round with simple majority voting between these two first-round winners.


3) Sequential runoff:

each voter votes for her most preferred alternative. The alternative with the fewest votes is eliminated; the others go to a second round of majority voting. This is repeated until just one alternative remains.


4) Borda count:

Each voter assigns points to each alternative according to its rank order
– the least preferred alternative receives 0 points, second least preferred alternative receives 1 point, …, most preferred alternative receives N-1 points
(if N is the number of available alternatives).
– the sum of points is calculated for each alternative
 the alternative with the highest sum of points wins.


5) Condorcet procedure:

If there is one alternative that wins all pairwise round robin tournaments, it is the winning alternative.

Lösung ausblenden
TESTE DEIN WISSEN

Normal Form Games (4)

Lösung anzeigen
TESTE DEIN WISSEN

• A normal form game is a game in which the players decide simultaneously and independent of each other.


• This means that no player knows the decision of the other players at the time of decision.


• The description of a strategic situation by a normal form game is suited if the players
decide at the same time
– or decide in sequence without knowing the decisions of the predecessors


• The fact that each player has a utility over the outcomes (i.e. the actions of all players) and not only on the payoff of the own action, distinguishes a strategic situation from a pure decision situation.

Lösung ausblenden
TESTE DEIN WISSEN

How to understand mixed strategy
equilibria (4)

Lösung anzeigen
TESTE DEIN WISSEN

• Randomization (e.g. matching pennies)
• Uncertainty about the action choices of the opponent(s)
• Probabilities as historic frequencies
• Probabilities may represent the proportion in which certain (pure strategy playing) types are present in the opponent population

Lösung ausblenden
TESTE DEIN WISSEN

Indifference

Lösung anzeigen
TESTE DEIN WISSEN

• According to the fundamental lemma, mixed strategy equilibria consist of pure strategies that are all best replies to the (mixed) strategies of the others. This means that all pure strategies lead to the same payoff as the mixed strategy, given that the others do not deviate.


• Why should a player then play the mixed strategy and not just one of the pure strategies that are best replies?
-> The answer is that otherwise, the other players would have an incentive to deviate and the whole system would become unstable: players have to mix, such that the prob. of “scoring right” equals the prob. of “scoring left”.

Lösung ausblenden
TESTE DEIN WISSEN

Core and Bargaining Set

Lösung anzeigen
TESTE DEIN WISSEN

• The bargaining set assumes that the argument underlying an objection for which there is no counter-objection undermines the stability of an outcome.


• The bargaining set is a weaker concept than the core since it allows objections, but only those with counter-objections.


• The core does not allow any objections.


 Hence the core is a subset of the bargaining set.

Lösung ausblenden
TESTE DEIN WISSEN

Shapley Value - Intuition

Lösung anzeigen
TESTE DEIN WISSEN

• Suppose the N players wait in front of a room.
• In a random order these players enter the room; one after the other.
• For each player that enters calculate the amount by which this player increases the coalition value of the players already in. This is the player’s marginal contribution.
• The idea of the Shapley value is to allocate the marginal contribution to each player.

• If one would give each player exactly her marginal contribution, the allocation would depend on the random order in which the players enter.
• Hence, the Shapley value allocates the average marginal contribution (averaged over all N! sequences in which the players can possibly enter the room) to each player.

Lösung ausblenden
TESTE DEIN WISSEN

Group Choice

Lösung anzeigen
TESTE DEIN WISSEN

• In the non-cooperative game theory analysis the decider is always an individual with preferences over the possible outcomes of the game.
• Even if we model a firm as a player, we assume that it has a single utility function.
• In fact, the decisions of a firm are the result of a process in the firm (its board of directors). How this process works is neglected.


• In cooperative game theory we studied coalition formation and group decisions for allocating payoffs.
• In this chapter we study mechanisms that aid a group (e.g. a committee, a parliament, a board, …) to decide among alternatives (e.g. candidates in an election, new laws, different business plans).

Lösung ausblenden
  • 68994 Karteikarten
  • 669 Studierende
  • 71 Lernmaterialien

Beispielhafte Karteikarten für deinen Game Theory Kurs an der AKAD Hochschule Stuttgart - von Kommilitonen auf StudySmarter erstellt!

Q:

Folk Theorem (general)

A:

• The folk theorem shows that there is a huge multiplicity of equilibria in infinitely repeated games.


• The threat of using a trigger strategy is often too strong since it suffices to punish so long that a deviation becomes unprofitable. Hence the punishment can stop after a finite time.


• The threat with a trigger strategy is often incredible.

Q:

Game without equilibrium (3)

A:

• “Highest number wins”:
– Two players write down a number.
– The player with the higher number wins.


• This is an infinite game in which each player has infinitely many actions.


• This game has no equilibrium (neither in pure nor in mixed strategies).

Q:

How to determine mixed strategy
equilibria?

A:

• According to the previous lemma all actions that are chosen with positive probability in a mixed strategy lead to the same utility.


• This is the key to the calculation of the mixed strategy equilibria, i.e. the determination of the actions that are chosen with positive probability and the corresponding weights.

Q:

The Exchange Game

A:

Scenario:

Two players and two envelopes
• Both players know that envelopes may contain 5, 10, 20, 40, 80, or 160 Euro
• Both player know that one envelope contains twice the amount of the other envelope
• The two envelopes are randomly distributed to the two players
• After both players have inspected their envelopes they are asked whether they want to exchange
• Making an exchange offer costs 1
• If both agree to exchange, they exchange


Supposition:

• Suppose one player has 10 and the other 20
• Expected gain from exchange for player with 20 is ½·40 + ½·10 - 1= 24 > 20
• Expected gain from exchange for player with 10 is ½·20 + ½·5 - 1= 11.5 > 10
• Since both players profit from an exchange, they may both agree to exchange → exchange takes place

• How can it be that both agree, since, a priori it is clear that exactly one player wins from the exchange, while the other one loses?
Problem: players did not think about the strategic situation. Since both parties involved act strategically, the problem cannot be solved by shortsighted expected values, but by a strategic analysis


Strategic Analysis:
consider the border cases first. Suppose player finds 160; knows for sure that other player has 80 → does not want to exchange
⇒ player with 80 knows that he can only exchange with a player with 40→ does not want to exchange
⇒ player with 40 knows that he can only exchange with a player with 20→ does not want to exchange

⇒ player with 5 would like to exchange with 10, but knows that player with 10 does not make an offer → player with 5 saves the cost of 1 and also does not make an offer to exchange


-> Strategic analysis shows that there are no incentives for exchange, although each player ≠ 160 has a positive expected value from the exchange

Q:

Backward Induction (3)

A:

• Backward induction is an algorithm to determine subgame perfect equilibria.


• The game tree is analyzed from backward and the equilibria of the subgames are determined.


• This is also the way to proof Zermelo’s theorem.

Mehr Karteikarten anzeigen
Q:

The 5 Voting Schemes

A:

1) Simple majority voting: 

each voter votes for her most preferred alternative. The alternative with the highest number of votes wins.


2) Plurality runoff:

each voter votes for her most preferred alternative. The two alternatives with the highest number of votes go to a second round with simple majority voting between these two first-round winners.


3) Sequential runoff:

each voter votes for her most preferred alternative. The alternative with the fewest votes is eliminated; the others go to a second round of majority voting. This is repeated until just one alternative remains.


4) Borda count:

Each voter assigns points to each alternative according to its rank order
– the least preferred alternative receives 0 points, second least preferred alternative receives 1 point, …, most preferred alternative receives N-1 points
(if N is the number of available alternatives).
– the sum of points is calculated for each alternative
 the alternative with the highest sum of points wins.


5) Condorcet procedure:

If there is one alternative that wins all pairwise round robin tournaments, it is the winning alternative.

Q:

Normal Form Games (4)

A:

• A normal form game is a game in which the players decide simultaneously and independent of each other.


• This means that no player knows the decision of the other players at the time of decision.


• The description of a strategic situation by a normal form game is suited if the players
decide at the same time
– or decide in sequence without knowing the decisions of the predecessors


• The fact that each player has a utility over the outcomes (i.e. the actions of all players) and not only on the payoff of the own action, distinguishes a strategic situation from a pure decision situation.

Q:

How to understand mixed strategy
equilibria (4)

A:

• Randomization (e.g. matching pennies)
• Uncertainty about the action choices of the opponent(s)
• Probabilities as historic frequencies
• Probabilities may represent the proportion in which certain (pure strategy playing) types are present in the opponent population

Q:

Indifference

A:

• According to the fundamental lemma, mixed strategy equilibria consist of pure strategies that are all best replies to the (mixed) strategies of the others. This means that all pure strategies lead to the same payoff as the mixed strategy, given that the others do not deviate.


• Why should a player then play the mixed strategy and not just one of the pure strategies that are best replies?
-> The answer is that otherwise, the other players would have an incentive to deviate and the whole system would become unstable: players have to mix, such that the prob. of “scoring right” equals the prob. of “scoring left”.

Q:

Core and Bargaining Set

A:

• The bargaining set assumes that the argument underlying an objection for which there is no counter-objection undermines the stability of an outcome.


• The bargaining set is a weaker concept than the core since it allows objections, but only those with counter-objections.


• The core does not allow any objections.


 Hence the core is a subset of the bargaining set.

Q:

Shapley Value - Intuition

A:

• Suppose the N players wait in front of a room.
• In a random order these players enter the room; one after the other.
• For each player that enters calculate the amount by which this player increases the coalition value of the players already in. This is the player’s marginal contribution.
• The idea of the Shapley value is to allocate the marginal contribution to each player.

• If one would give each player exactly her marginal contribution, the allocation would depend on the random order in which the players enter.
• Hence, the Shapley value allocates the average marginal contribution (averaged over all N! sequences in which the players can possibly enter the room) to each player.

Q:

Group Choice

A:

• In the non-cooperative game theory analysis the decider is always an individual with preferences over the possible outcomes of the game.
• Even if we model a firm as a player, we assume that it has a single utility function.
• In fact, the decisions of a firm are the result of a process in the firm (its board of directors). How this process works is neglected.


• In cooperative game theory we studied coalition formation and group decisions for allocating payoffs.
• In this chapter we study mechanisms that aid a group (e.g. a committee, a parliament, a board, …) to decide among alternatives (e.g. candidates in an election, new laws, different business plans).

Game Theory

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten StudySmarter Kurse für deinen Studiengang Game Theory an der AKAD Hochschule Stuttgart

Für deinen Studiengang Game Theory an der AKAD Hochschule Stuttgart gibt es bereits viele Kurse, die von deinen Kommilitonen auf StudySmarter erstellt wurden. Karteikarten, Zusammenfassungen, Altklausuren, Übungsaufgaben und mehr warten auf dich!

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Game Theory
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Game Theory