Стратегия в игре с нулевой суммой

[green_fr]

Возвращаясь к подлецу Гарднеру, а точнее (подозреваю) к собственной деградации.
Возьмём простую игру с нулевой суммой. Матрица игры, скажем, такая:

		Игрок А
		Ход А1	Ход А2
Игрок Б	Ход Б1	1	-2
	Ход Б2	-7	8

Т.е. два игрока, у каждого по два варианта хода, в зависимости от хода обоих считается результат игры (положительное число - А выигрывает, отрицательное - Б).
Очевидным образом показывается, что любой из игроков не может просто выбрать выигрышный вариант для своего хода. На любой фиксированный ход одного игрока найдётся ход другого такой, что первый игрок проиграет. Т.е. нужно найти стратегию, точнее - вероятность, с которой нужно ходить первый из доступных ходов, в оставшихся случаях - второй.
В статье пересказывают ответ, не дав решение: нужно посчитать некие коэффициенты, которые дадут вес каждого хода. Для первого игрока это будут |1 - (-2)| : |(-7) - 8|, т.е. 1 : 5. Нужно ходить А2 в пять раз чаще, чем А1. Аналогично для второго - по вертикали таблицы - ответ 4 : 5.

Я тупо не понимаю, как они посчитали это. Википедия (английская) даёт тот же результат, тоже не объясняя (за очевидностью?) его вывод. У меня в голове крутится давно забытое слово "минимакс", но я не могу применить его к этой игре.

Я записываю результат игры в предположении, что игрок А играет А1 с вероятностью a, а игрок Б - Б1 с вероятностью c. Результат получается, естественно, линейным как относительно a, так и относительно c (с их перемножением конечно же). Потуги оптимизировать что бы то ни было относительно одной переменной (чтобы потом оптимизировать относительно другой) не приводят ни к чему - что ты получишь с линейной функции? Оптимум будет всегда либо на нуле, либо на 1.

Короче, СОС. Кто понял, ещё лучше, кто знает ответ :-)

Comments

:)))))))))))))))))))))))

[alexnavfr.livejournal.com]

Вот честно прочитал, все слова знакомы. А вот всё вместе я не понял. :))))

[green-fr.livejournal.com]

Присоединяйся к первой фразе - мерзавец Гарднер!

[green-fr.livejournal.com]

Ты где, кстати, пропал на Пасху? Всё нормально, все живы?

[kalvado.livejournal.com]

Ну чиста конкретна:
Если ты ложишься в экстремум на {1} или {0}, то партнер может предсказать такое поведение, и всегда ходить так чтобы ты проигрывал; значит надо как минимум иногда из экстремума уходить.
Т.е. надо оптимизировать [а(1-б)+б(1-а)]/[аб+(1-а)(1-б)]; и с весовыми коэффициентами к тому же. К тому же итерационно; оптимизация по а для А, по б для Б.. должно сойтись, ИМХО
где-то так, наверное?

[green-fr.livejournal.com]

Нифига, итерационно как раз процесс не сходится. Если ты оптимизируешь по одному параметру, ты падаешь в какой-нибудь из нулей. И аргумент "оттуда надо уходить" - а насколько? Или первую точку выбрать от балды, а потом оптимизировать относительно её, ища, куда сойдётся? Неустойчиво получается - как только вылетает какая-то вероятность в 0, всё начинает шататься.
Мне кажется, решение должно быть каким-то жутко тривиальным. Иначе его бы так не опустили в статье "на усмотрение читателя".

[kalvado.livejournal.com]

ты оптимизируешь по двум параметрам, а не по одному - с учетом оптимизации второго
должно быть седло
шас попробую сделать..

[dalvadorez.livejournal.com]

Да, всегда попадаешь в края, но не всегда _только_ в края. У седла будет "направляющая", там кроме краев все внутренние точки тоже.

[green-fr.livejournal.com]

Его я и искал, но какое седло на линейных функциях? Посмотри, что ниже донна Роза пишет (ты вроде по-английски розумеешь :-Р)

[dalvadorez.livejournal.com]

Седло, седло, минимакс же.. Только в двух координатах - вероятность одного и вероятность другого.

[dalvadorez.livejournal.com]

I mean, graph the following function

z=ab-2b(1-a)-7a(1-b)+8(1-a)(1-b)

This is expected payoff of player A for any possible "mixes". It should produce "sedlo".

[kalvado.livejournal.com]

no
linear vs a for all fixed b
probably win/loss ratio would do it

[dalvadorez.livejournal.com]

Да

Как известно, у седла есть куча линейных касательных, которые лежат в поверхности седла.

Если мне кто-нибудь объяснит, как выложить сюда картинку, покажу. Или могу выслать куда-нибудь в акробате.

[green-fr.livejournal.com]

Пришли мне на почту, а?

[green-fr.livejournal.com]

Кажется понял. Расходились мы в достаточно тонком моменте: ты показала, что у Б нет единой выигрышной стратегии для всех ходов А, но я и не говорил этого, а то, что у А в итоге есть стратегия (5/9), которая оптимальна в смысле минимакса, т.е. максимизирует минимальную прибыль, как бы ни играл Б.
Да, трындец. Зато красиво, и понятно, как обобщать на большее количество вариантов хода у каждого игрока (с некоторой фантазией переходить в большие размерности).
Красиво, спасибо!

[dalvadorez.livejournal.com]

Да не за что.

Прочто эта моя метода обобщается на случай игр с ненулевой суммой тоже, в этом ее прелесть.

[dalvadorez.livejournal.com]

Ничего, что я по-английски? А то я быстро по-русски без клавиатуры русской печатать не умею.

Assume Player A plays A1 with probability a. What is the best strategy of Player B in this case (so-called best reply/response)?
Player B's payoff from his strategy B1 is a-2(1-a)=3a-2
Player B's payoff from his strategy B2 is -7a+8(1-a)=8-15a

Therefore he plays B1 if 3a-2>8-15a, which is equivalent to a>5/9.
He plays B2 if a<5/9
He is indifferent if a=5/9

Similarly, assume Player B plays B1 with probability b.
Player A's payoff from his strategy A1 is -b+7(1-b)=7-8b
Player A's payoff from his strategy A2 is 2b-8(1-b)=10b-8
Therefore he plays A1 if 7-8b>10b-8, which is equivalent to b<5/6.
He plays B2 if b<5/6
He is indifferent if b=5/6

Therefore we can wee that, each player is playing a mix of his strategies when a=5/9 and b=5/6.

The idea here is as follows: you have to choose a and b so that neither of the players has an incentive to play with any other probability (which is called "to deviate" in game theory). So you choose your probability so that it makes the other guy indifferent.
You can also solve it the way you were solving it, and then you will get exactly the conditions written above - e.g, corner solutions for a and b most of the time and indifference in some cases. Just think of how you woould maximize a linear function..

[dalvadorez.livejournal.com]

Черт, опечаток все равно вагон.

[dalvadorez.livejournal.com]

Ok, I am used to the payoffs in the matrix given for the row player, while in your description they are attributed to the column player, right? Therefore you need to revert my answers, but the principle is still the same.

[green-fr.livejournal.com]

Я этого даже не заметил :-)

[dalvadorez.livejournal.com]

Я тоже поздновато заметила :)

[green-fr.livejournal.com]

shit! (ничего, что я тоже по-английски начал?)
Я дошёл в своих рассуждениях до строчки "He is indifferent if a=5/9" и добавил "положим он играет в таком случае B1". Идиот :-)

Но логика какая-то извращённая получается: чтобы мочь играть оба варианта, нужно их играть так, чтобы сопернику было тоже выгодно играть оба варианта.

И как показать, что это - оптимум?

[dalvadorez.livejournal.com]

Это оптимум чего?
Для каждого из игроков это оптимум _given the strategy of the other_! (sorry, I cannot stand Russian fonts). This is the basic principle of Nash Equilibrium, the most cited concept in economics.

Otherwise, what are you optimizing? the sum of payoffs (standard measure of social welfare) is zero everywhere :)

[green-fr.livejournal.com]

Нет, лично я ищу оптимальный алгоритм для любого поведения соперника :-) Т.е. как показать, что вот эти 5/6 дают первому оптимум для любого алгоритма второго? И наоборот, что 4/9 - это оптимум второго для любого поведения первого.

[dalvadorez.livejournal.com]

Такого здесь нет.
Оптимальное поведение - это кусочно-линейное соответствие, описанное выше. Нет поведения (для данной игры), которое лучше всех прочих _что бы не играл противник_. Если хочешь, твой оптимум как игрока А зависит от параметра - стратегии игрока В. И наоборот. И ты потом решаешь систему двух уравнений от двух параметров, подбирая параметры так, чтобы каждый игрок вел себя оптимально.

Бывают игры, где такой оптимум есть. Такие оптимумы тогда называются доминирующей стратегией.

Ты извини за лекторский тон, я просто про это детям и впрямь лекции читаю. :)

[dalvadorez.livejournal.com]

"Дети" - это кодовое название для моих студентов. :) Их доля тяжела, и столь же тяжела моя :).

[green-fr.livejournal.com]

Не отмазывайся. Дети - это не порок :-)

[green-fr.livejournal.com]

Мне кажется ты ошибаешься. Во-первых, в статье чётко сказано, что мы ищем стратегию, которая максимизирует наш минимальный выигрыш, как бы ни играл противник.
Во-вторых, если даже это не так - парадокс получается. Мы подобрали стратегию для А такую, которая оптимизирует что? Его выигрыш, в предположении, что Б играет так, как мы ему положили? Если эта стратегия не оптимизирует выигрыш А относительно любого поведения Б, то кто мешает Б, зная, как играет А, подобрать такую стратегию, при которой А выигрывает меньше?
Нет, идея именно в том, что для них для обоих это - оптимальные стратегии. Для одного - максимизация минимального выигрыша (как бы ни играл оппонент), для другого - минимизация максимального проигрыша. И вот это я бы тоже хотел увидеть, каким образом там получается одна и та же цифра. Хотелось бы прочувствовать решение...

[dalvadorez.livejournal.com]

No, I do not think I am mistaken, I think it is misunderstanding. Look, in the article they are searching for something that maximizes players' _minimal_ payoff, not just payoff. That is, we look for a strategy that can always yield us the highest _minimal_ payoff. What I said above was that there is no unique strategy that maximizes payoff, without "minimal".

Now, to the proof. I'm going to draw a picture and mail it to you, so that you see it visually, but it will take me some time. Otherwise just google for minimax theorem.

[green-fr.livejournal.com]

Уже гуглил. Всеми это подразумевается как само собой разумеющееся :-/

[dalvadorez.livejournal.com]

Пишу уже. Куда тебе слать?

[dalvadorez.livejournal.com]

Or, rather

"in the article they are searching for something that minimizes player' _maximum_ payoff, not just payoff".

Those two are proven to be equivalent for zero-sum games, the second one is just easier to illustrate.

[yuriyag.livejournal.com]

Бросить монетку, да и дело с концом :-Р

[green-fr.livejournal.com]

Естественно. Вопрос: какой формы монетку бросать :-Р Первому вот нагадали, что ныдо бросать кубик.