3. Задачи, приводимые к матричным играм.

Задача 1. Игра полковника Блотто.

Полковник имеет в своём распоряжении 5 единиц войска и защищает 2 равноценные позиции А и В. Каждый из противников для защиты и атаки соответствующей позиции может выделять только целое число единиц войска. Считается, что если хотя бы на одной позиции Блотто сосредоточит меньшее число войск, чем его противник, то он проиграет. Во всех остальных случаях он выигрывает. Противники делают свой выбор одновременно и выигрыш равен 1. В этой матричной игре противник (1-ый игрок имеет 5 выборов, а полковник (2-ой игрок)–6 выборов.

А=

Задача 2. (про 3 пальца). Два игрока А и В одновременно показывают один, два или три пальца. Выигрыш решает общее количество пальцев: если оно четное – выигрывает А и получает от В сумму, равную этому числу; ели нечетное, то, наоборот, А платит В сумму, равную этому числу.

Составим матрицу игры.

	1	2	3	min
1	2	-3	4	-3
2	-3	4	-5	-5
3	4	-5	6	-5
max	4	4	6

4. Преобразование матричных игр.

Стратегия А_i называется доминирующей над стратегией A_k, если в строке A_i стоят выигрыши не меньшие, чем в соответствующих клетках A_k и из них по крайней мере один действительно больше, чем в соответствующей клетке строки A_k . Если же все выигрыши строки A_i равны соответствующим выигрышам строки A_k, то стратегия называется дублирующей. Аналогично для стратегий игрока В: доминирующей называется та его стратегия, при которой везде стоят выигрыши не большие, чем в соответствующих клетках другой, и по крайне мере один из них действительно меньше; дублирование означает полное повторение одного столбца другим. Все дублирующие стратегии и те, для которых есть доминирующие, можно отбросить.

ПРИМЕР 5.2.

	В1	В2	В3	В4	В5
A1	4	7	2	3	4
A2	3	5	6	8	9
А3	4	4	2	2	8
A4	3	6	1	2	4
A5	3	5	6	8	9

A₅ дублирует A₂, A₁ доминирует над A₄. Отбросив A₅ и A₄, получим

	В1	В2	В3	В4	В5
A1	4	7	2	3	4
A2	3	5	6	8	9
А3	4	4	2	2	8

В₃ доминирует над В₄ и В₅ (В стремится отдать поменьше), а В₁ над В₂

	В1	В3
A1	4	2
A2	3	6
А3	4	2

_{Удалим дублирующую строку А}3

	В1	В3
A1	4	2
A2	3	6

Упрощая матрицу игры, можно прийти к играм 22, 2n, m2, которые допускают геометрическую интерпретацию, что упрощает поиск оптимальной стратегии.