Tutorial 3: solution sketches
1. Claim: A = −AT implies xT Ay = −yT Ax for all vectors x, y of the right length.
Proof. xTAy=xT(−AT)y=−(xTATy)=−(xTATy)T =−yTAx,wherethesecond to last step uses the fact that BT = B for all 1 × 1-matrices, and the last step uses the facts that (BT )T = B and (BC)T = CT BT . (One could of course prove the claim by e.g. direct calculation)
In particular, the claim implies that xT Ax = −xT Ax, which gives xT Ax = 0. This means that whenever both players play with the same mixed strategy x, they both have an expected payoff of zero. Thus in any strategy profile (x,y), if one of the players has a negative expected payoff, they can improve by copying the other players strategy. Thus no strategy profile giving non-zero expected payoffs can be a Nash equilibrium of the game.
Copyright By PowCoder代写 加微信 powcoder
2. Using the recipe from page 12 of the slides for lecture 4, we get the linear program
Maximize v Subject to: (xTA)j ≥v i xi = 1
Writing this out explicitly, we get the the linear program Maximize v Subject to:
2×1 + 7×2 ≥ v
9×1 + 0x2 ≥ v
4×1 + 3×2 ≥ v x1 + x2 = 1 x1 ≥0,×2 ≥0
which is equivalent to the linear program that was given. To compute the dual using the general recipe, we express it in the form
Maximize cT x Subject to: (Bx)i ≤ bi (Bx)j = bj
Using the given linear program we can get to the desired form by setting bT = (0,0,0,1) cT = (0,0,1), xT = (x1,x2,v) and
−2 −7 1 B=−9 0 1 −4 −3 1
To be clear with the indices, our linear program is then
Maximize cT x Subject to:
(Bx)i ≤bi fori=1,2,3 (Bx)4 = b4
xi ≥0fori=1,2
Now, using the general recipe the dual is
Minimize bT y Subject to:
(BTy)i ≥ci fori=1,2 (BTy)3 =c3
yi ≥0fori=1,2,3,
which, when setting y = (y1, y2, y3, v) translates to
Mimimize v
Subject to:
−2y1 −9y2 −4y3 +v≥0 −7y1 +0y2 −3y3 +v ≥ 0 y1 + y2 + y3 = 1
yi ≥0fori=1,2,3
Which is easily seen to be equivalent to the LP for computing the value and the maxminimizer strategy for player 2.
3. Let’s proceed as in the hint. bi is the amount of units of vitamin i you need daily. For simplicity let’s say the bi is measured in “grams-of-vitimin-i” (it doesn’t matter if it is grams or some other unit). Likewise, for simplicity, let us assume that the foods are also measured in units of grams.
The entries aij in the matrix A measure the number of units of vitamin i per unit of food j, or in other words “gram-of-vitamin i/gram-of-food-j”. The number cj is the cost-per-unit of food j, so it is measured in £/gram-of-food-j.
Now, the dual LP is
Maximize bT y Subject to: AT y ≤ c
Since ci is measured in £/gram-of-food-j, the left hand side of each constraint in ATy ≤ c must also be in the same units. So, in particular, the j’th constraint (AT y)j = mi=1 ai,j yi ≤ cj must have each ai,j yi be in units of £/gram-of-food-j. Since ai,j is in units of “gram-of-vitamin i/gram-of-food-j”, we must have yi in units of £/gram-of-vitimin-i. Furthermore, each term biyi in the objective function bT y is thus measured in grams-of-vitimin-i ∗ £/gram-of-vitimin-i = £. So, the objective function is somehow trying to maximize the amount of money (earned), and the variables yi are setting prices per-unit (i.e, per gram) of each vitimin i.
But what are the constraints (AT y)j ≤ cj , saying?
They are saying that the amount of money charged per-unit of each vitamin should be such that, if the number of units of each vitamin i contained in each until of food j is as specified by the entry ai,j in the matrix A, then the cost-per-unit of food j should not be less than the total costs per unit of all the vitamins that are in one unit of food j.
So, we can in effect view this dual problem as the “vitamin seller’s problem”. To be more precise, suppose the only thing that costs money in the production of food j is the cost for the amount of each vitamin that is contained in each unit of food j. (In fact, for simplicity, we can simply assume that each unit of food j consists of nothing other than the units of all the different vitamins that are contained in it.)
Suppose that the price per unit, cj, for each food has been pre-determined somehow. The vitamin seller needs to set a price per-unit for each vitamin, in such a way as
to do both of the following:
• make sure that the total cost-per-unit cj of food j is not strictly less that the total cost that would be required to buy all the units of vitamins that are supposedly contained in each unit of food j.
(These are the constraints AT y ≤ c.)
• maximize bT y, which measures the total income (to the vitamin seller) if the buyer (who is buying the foods), buys just enough of each food to get a total of exactly the minimum required units, bi, of each of the n vitamins.
So, this “Vitamin seller’s” price setting problem is the problem that the dual LP is trying to solve.
It is indeed interesting that (by the strong duality theorem) the maximum income the vitamin seller can achieve for itself by setting these prices while satisfying these constraints (namely, making sure each food can afford the vitamins in it, based on its price-per-unit cj), is the same as the minimum cost incurred by the buyer if it tries to minimize its own cost, subject to getting at least the minimum required bi units of each vitamin i.
Note also that by the “Complementary Slackness” theorem it follows that, in an optimal solution for the buyer and the seller, either the price of a vitamin i is set at 0, or else the amount of food the buyer buys contains exactly the minimum required bi units of vitamin i; and likewise, either the amount of food j purchased by the buyer is 0, or else the total cost of the vitamins contained in each unit of food j (at the prevailing prices of the vitamins) is exactly cj (which is the maximum allowable cost per unit of food j).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com