Game Theory Basics Solutions to Exercises © Bernhard von Stengel 2022 Solution to Exercise 1.1 (a) Let ≤ be defined by (1.7). To show that ≤ is transitive, consider 𝑥, 𝑦, 𝑧 with 𝑥 ≤ 𝑦 and 𝑦 ≤ 𝑧. If 𝑥 = 𝑦 then 𝑥 ≤ 𝑧, and if 𝑦 = 𝑧 then also 𝑥 ≤ 𝑧. So the only case left is 𝑥 < 𝑦 and 𝑦 < 𝑧, which implies 𝑥 < 𝑧 because < is transitive, and hence 𝑥 ≤ 𝑧. Clearly, ≤ is reflexive because 𝑥 = 𝑥 and therefore 𝑥 ≤ 𝑥. To show that ≤ is antisymmetric, consider 𝑥 and 𝑦 with 𝑥 ≤ 𝑦 and 𝑦 ≤ 𝑥. If we had 𝑥 ≠ 𝑦 then 𝑥 < 𝑦 and 𝑦 < 𝑥, and by transitivity 𝑥 < 𝑥 which contradicts (1.38). Hence 𝑥 = 𝑦, as required. This shows that ≤ is a partial order. Finally, we show (1.6), so we have to show that 𝑥 < 𝑦 implies 𝑥 ≤ 𝑦 and 𝑥 ≠ 𝑦 and vice versa. Let 𝑥 < 𝑦, which implies 𝑥 ≤ 𝑦 by (1.7). If we had 𝑥 = 𝑦 then 𝑥 < 𝑥, contradicting (1.38), so we also have 𝑥 ≠ 𝑦. Conversely, 𝑥 ≤ 𝑦 and 𝑥 ≠ 𝑦 imply by (1.7) 𝑥 < 𝑦 or 𝑥 = 𝑦 where the second case is excluded, hence 𝑥 < 𝑦, as required. (b) Consider a partial order ≤ and assume (1.6) as a definition of <. To show that < is transitive, suppose 𝑥 < 𝑦, that is, 𝑥 ≤ 𝑦 and 𝑥 ≠ 𝑦, and 𝑦 < 𝑧, that is, 𝑦 ≤ 𝑧 and 𝑦 ≠ 𝑧. Because ≤ is transitive, 𝑥 ≤ 𝑧. If we had 𝑥 = 𝑧 then 𝑥 ≤ 𝑦 and 𝑦 ≤ 𝑥 and hence 𝑥 = 𝑦 by antisymmetry of ≤, which contradicts 𝑥 ≠ 𝑦, so we have 𝑥 ≤ 𝑧 and 𝑥 ≠ 𝑧, that is, 𝑥 < 𝑧 by (1.6), as required. Also, < is irreflexive, because 𝑥 < 𝑥 would by definition mean 𝑥 ≤ 𝑥 and 𝑥 ≠ 𝑥, but the latter is not true. Finally, we show (1.7), so we have to show that 𝑥 ≤ 𝑦 implies 𝑥 < 𝑦 or 𝑥 = 𝑦 and vice versa, given that < is defined by (1.6). Let 𝑥 ≤ 𝑦. Then if 𝑥 = 𝑦, we are done, otherwise 𝑥 ≠ 𝑦 and then by definition 𝑥 < 𝑦. Hence, 𝑥 ≤ 𝑦 implies 𝑥 < 𝑦 or 𝑥 = 𝑦. Conversely, suppose 𝑥 < 𝑦 or 𝑥 = 𝑦. If 𝑥 < 𝑦 then 𝑥 ≤ 𝑦 by (1.6), and if 𝑥 = 𝑦 then 𝑥 ≤ 𝑦 because ≤ is reflexive. This completes the proof. Solution to Exercise 1.2 (a) In analysing the games of three Nim heaps where one heap has size one, we first look at some examples, and then use mathematical induction to prove what we conjecture to be the losing positions. A losing position is one where every move is to a winning position, because then the opponent will win. The point of this exercise is to formulate a precise statement to be proved, and then to prove it. First, if there are only two heaps recall that they are losing if and only if the heaps are of equal size. If they are of unequal size, then the winning move is to reduce the larger heap so that both heaps have equal size. 1