Applied Probability Notes

Mechanism design is the game-theoretic setting where a designer chooses the game played in order to ensure some desired behavior or some desirable outcome occurs. We cover the VCG mechanism and Revelation Principle.

Continue reading “Mechanism design”

n-Person Games

We now consider games with more that $2$ players, so called $n$ -person games. We continue to consider non-cooperative games i.e. where players act solely in their own interests. From zero-sum games we extend our notation.

Continue reading “n-Person Games”

Two-person zero-sum games

We consider a highly simplified game between two players.

Continue reading “Two-person zero-sum games”

Foster-Lyapunov

Foster’s Lemma provides a natural condition to prove the positive recurrence of a Markov chain.

Continue reading “Foster-Lyapunov”

The Simplex Algorithm

The Simplex Theorem suggests a method for solving linear programs . It is called the Simplex Algorithm.

Continue reading “The Simplex Algorithm”

Linear Programming

A linear program is a constrained optimization problem with a linear objective, $f(x):=c^\top x$ , and linear functional constraints, $h(x):=Ax$ , we could for instance write