Your peers in the course Algorithmic Game Theory at the TU München create and share summaries, flashcards, study plans and other learning materials with the intelligent StudySmarter learning app.

Get started now!

Algorithmic Game Theory

Weak dominance

ai weakly dominates bi if for all a-i ∈ A-i, ui(ai,a-i) ≥ ui(bi,a-i) and for at least one a-i ∈ A-i, ui(ai,a-i) > ui(bi,a-i).

Algorithmic Game Theory

Pareto-Optimality

An outcome is Pareto-optimal if it is not Pareto-dominated.

An outcome is (weakly) Pareto-dominated if there exists another outcome in which all players obtain at least as much utility and one player is strictly better off.

Algorithmic Game Theory

When is a Maximin strategy recommended?

In face of uncertainty, a player may maximize his worst-case utility.

When games are neither solvable via ISD nor via IWD.

Algorithmic Game Theory

What is a mixture of maximin strategies called?

The set of maximin strategies is convex, i.e., a mixture of maximin strategies is again a maximin strategy.

Algorithmic Game Theory

The security level of player i is

The security level is the minimal utility that the player can enforce.

Independent of the opponents’ rationality.

Algorithmic Game Theory

Maximin strategies (and security levels) can be computed __ time.

Maximin strategies (and security levels) can be computed in polynomial time.

Algorithmic Game Theory

How can we efﬁciently check whether an action is dominated by some mixed strategy?

Linear Programming (LP)

Algorithmic Game Theory

How can a game be solved via iterated strict dominance?

A game can be solved via iterated strict dominance (ISD) if only a single action proﬁle survives the iterated elimination of dominated actions.

Algorithmic Game Theory

What are Solution Concepts?

A solution concept identiﬁes reasonable, desirable, or otherwise signiﬁcant strategy proﬁles of a game.

Algorithmic Game Theory

Important properties of solution concepts:

- Existence – Games may not be solvable via ISD or IWD.
- Uniqueness
- If a game is solvable via ISD, the resulting action proﬁle is unique.
- If a game is solvable via IWD, there may be different resulting action proﬁles.

- Efﬁcient computability
- It can be decided in polynomial time whether a game can be solved via ISD.
- Whether a game can be solved via IWD cannot be decided in polynomial time unless P=NP.

Algorithmic Game Theory

Very weak dominance

ai very weakly dominates bi if for all a-i ∈ A-i, ui(ai,a-i) ≥ ui(bi,a-i).

Algorithmic Game Theory

Are succint games normal games?

No

Beyond the Normal Form

For your degree program Computer Science at the TU München there are already many courses on StudySmarter, waiting for you to join them. Get access to flashcards, summaries, and much more.

Back to TU München overview pageStudySmarter is an intelligent learning tool for students. With StudySmarter you can easily and efficiently create flashcards, summaries, mind maps, study plans and more. Create your own flashcards e.g. for Algorithmic Game Theory at the TU München or access thousands of learning materials created by your fellow students. Whether at your own university or at other universities. Hundreds of thousands of students use StudySmarter to efficiently prepare for their exams. Available on the Web, Android & iOS. It’s completely free.

Best EdTech Startup in Europe

1## Learning Plan

2## Flashcards

3## Summaries

4## Teamwork

5## Feedback