AGTA Tutorial Sheet 3
Please attempt these questions before coming to the tutorial.
1. A symmetric finite 2-player zero-sum game, is a game that “looks exactly the same” from the point of view of both players. (For example, rock-paper-scissors is a symmetric zero-sum game.)
More formally, a 2-player zero-sum game is symmetric if and only if it is specified by a (n × n) payoff matrix, A = (ai,j ), for player 1 (the row player), such that for all i,j ∈ {1,…,n}, we have ai,j = −aj,i, or in order words, such that A = −AT .
Copyright By PowCoder代写 加微信 powcoder
Show that the minimax value of any symmetric two player zero-sum game must be zero. (Intuitively, this should be obvious: in a symmetric game neither player can have an advantage, because the game “looks the same” to both players. But I want you to prove it. Hint: prove it by contradiction, assuming the value v∗ ̸= 0.)
2. Consider a 2-player zero-sum matrix game, given by the (2 × 3) payoff matrix:
294 A=703
Construct the LP, described in class, for computing the value, and minmaximizer strategy for player 1, for this game. Confirm that the LP looks like this:
Maximize v Subject to:
v − 2×1 − 7×2 ≤ 0 v − 9×1 − 0x2 ≤ 0 v − 4×1 − 3×2 ≤ 0 x1 + x2 = 1,
x1 ≥0,×2 ≥0.
Construct the dual of this LP, according to the “general recipe for LP duals” given in the lecture 7 slides (page 6). Conclude that the dual LP is precisely the LP for computing the value, and maxminimizer strategy for player 2, in the same game.
3. This is the “food for thought” question posed in the lecture slides regarding LP duality: recall the “diet problem”, described in the first lecture on LPs. It can be put in the form:
Minimize cT x Subject to: Ax ≥ b x1,…,xn ≥0
Construct the dual to this LP.
Then try to interpret the “meaning” of the dual. What do the dual variables “mean”, in the context of the diet problem? What is the dual trying to optimize? If the optimizing agent in the primal is “the frugal dieter”, then who is the optimizing “counter-agent” in the dual?
(Hint: try to assign consistent “units of measure” to the primal vari- ables, constants, and coefficients. These, and the constraints of the primal and dual, will then determine what the appropriate “units of measure” for the dual variables are, and that will hopefully guide you toward an interpretation of the dual.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com