Теория игр в советском кино
В последнее время немного увлёкся теорией игр про аукционы -- в частности, прослушал прекрасный курс ksonin; о введении в экономику, потом пытался начать слушать курс savvateev о теории игр -- к сожалению, пока забросил из-за
нехватки времени (при всей эклектичности Лёшиного мировоззрения, Лёша просто прекрасный лектор и хороший, насколько я могу судить, математик).
Многие помнят советский художественный фильм "Гараж". Вкратце, сюжет там состоит в следующем. У гаражного кооператива случилась неприятность -- выяснилось, что он могут построить на два (или три? не так важно) гаража меньше, чем участников кооператива. Нужно определить несчастных, кто останется без гаража. Сначала они хотели это сделать решением правления, потом всю ночь участники выясняли, как поступить, двух несчастных определили с помощью юридических заморочек, а последнего - жребием.
Если бы участники кооператива прошли бы простейший начальный курс экономики, то они смогли бы догадаться, что наименее болезненных способ определить трёх несчастных -- провести аукцион. Каждый из N участников пишет на бумажке сумму S, с которой он готов расстаться, чтобы не остаться без гаража -- при том, что оставшись без гаража он получил бы компенцацию ( S * (N-3) ) / 3: будущие обладатели скидываются поровну на компенсации оставшимся без гаража; компенсации также делятся поровну. Потом выбирают три самых маленьких числа, написавшие их останутся без гаража и получат компенсацию. Выбираем наибольшее из чисел, написанных получателями компенсации (или, как вариант, наименьшее из чисел, написанных обладателями гаражей) -- и по такой сумме денег берут у обладателей гаражей, а оставшиеся получат компенсацию по ( S * (N-3) ) / 3.
Давайте теперь подумаем, какая должна быть стратегия у участников этой игры. Предположим, что участников всего двое (а гараж один). Оба пишут на бумажке число. Пусть первый участник написал x, второй y. Если x < y, то выигрыш первого участника равен x, если x > y, то его выигрыш равен гараж минус y. Так чему же равна оптимальная ставка?
Казалось бы, каким бы ни был y, нам x стоило бы чуть-чуть увеличить: если x < y, то надо сделать его равным y - epsilon, где epsilon - очень маленькое число, а если x уже больше у, то можно его увеличивать вообще без проблем,
наш выигрыш от этого никак не изменится. Попробуем посчитать более строго.
Предположим, что первый участник оценивает гараж в P. Тогда его выигрыш равен x, если x < y и P - y если x > y.
Если E(y) -- плотность случайной величины "ставка второго игрока", то выигрыш равен
-- если мы получили компенсацию, и --
если мы оставили себе гараж, заплатив деньги сопернику.
Так же, как это сделал ksonin (см. здесь, п.14), мы можем предположить, что E(y) = 1, т.е. мы считаем, что ставка соперника равномерно распределена на отрезке [0;1]. Тогда первый интеграл окажется равным x(1-x), а второй -- Px-x^2/2. Легко посчитать,что максимум этой функции (наша оптимальная ставка) оказывается (P+1)/3.
Получается, что завышать стоимость гаража нужно только если он нам кажется недорогим, а если его цена близка к единице, то скорее ставку лучше сделать меньшей, чем цена гаража.
Ещё круче получается, если мы договорились, что компенсация равна не минимуму, а максимуму из ставок. Тогда (если я нигде не ошибся в выкладках:) ) оптимальная ставка равна P/3. Прослеживается аналогия с английским и голландским аукционами, где меньшая цена, которую участник платит по правилам игры приводит к росту ставок.
Если же вернуться к условиям, как они были в фильме (n > 2 участников), то в наших рассуждениях изменятся E(y) и величина компенсации за гараж будет равна (n - 1) * минимальная_ставка (если есть n-1 гараж, т.е. останется без гаража только один участник). Если все участники делают ставки равномерно на отрезке, то минимальная ставка будет распределена по степенному закону, т.е. плотность вероятности будет E(y)=(n-1)*(y^(n-2)). Таким образом при ставке x, в среднем выигрыш получится --
первое слагаемое отвечает за получение гаража, второе -- за компенсацию.
нехватки времени (при всей эклектичности Лёшиного мировоззрения, Лёша просто прекрасный лектор и хороший, насколько я могу судить, математик).
Многие помнят советский художественный фильм "Гараж". Вкратце, сюжет там состоит в следующем. У гаражного кооператива случилась неприятность -- выяснилось, что он могут построить на два (или три? не так важно) гаража меньше, чем участников кооператива. Нужно определить несчастных, кто останется без гаража. Сначала они хотели это сделать решением правления, потом всю ночь участники выясняли, как поступить, двух несчастных определили с помощью юридических заморочек, а последнего - жребием.
Если бы участники кооператива прошли бы простейший начальный курс экономики, то они смогли бы догадаться, что наименее болезненных способ определить трёх несчастных -- провести аукцион. Каждый из N участников пишет на бумажке сумму S, с которой он готов расстаться, чтобы не остаться без гаража -- при том, что оставшись без гаража он получил бы компенцацию ( S * (N-3) ) / 3: будущие обладатели скидываются поровну на компенсации оставшимся без гаража; компенсации также делятся поровну. Потом выбирают три самых маленьких числа, написавшие их останутся без гаража и получат компенсацию. Выбираем наибольшее из чисел, написанных получателями компенсации (или, как вариант, наименьшее из чисел, написанных обладателями гаражей) -- и по такой сумме денег берут у обладателей гаражей, а оставшиеся получат компенсацию по ( S * (N-3) ) / 3.
Давайте теперь подумаем, какая должна быть стратегия у участников этой игры. Предположим, что участников всего двое (а гараж один). Оба пишут на бумажке число. Пусть первый участник написал x, второй y. Если x < y, то выигрыш первого участника равен x, если x > y, то его выигрыш равен гараж минус y. Так чему же равна оптимальная ставка?
Казалось бы, каким бы ни был y, нам x стоило бы чуть-чуть увеличить: если x < y, то надо сделать его равным y - epsilon, где epsilon - очень маленькое число, а если x уже больше у, то можно его увеличивать вообще без проблем,
наш выигрыш от этого никак не изменится. Попробуем посчитать более строго.
Предположим, что первый участник оценивает гараж в P. Тогда его выигрыш равен x, если x < y и P - y если x > y.
Если E(y) -- плотность случайной величины "ставка второго игрока", то выигрыш равен
-- если мы получили компенсацию, и --
если мы оставили себе гараж, заплатив деньги сопернику.
Так же, как это сделал ksonin (см. здесь, п.14), мы можем предположить, что E(y) = 1, т.е. мы считаем, что ставка соперника равномерно распределена на отрезке [0;1]. Тогда первый интеграл окажется равным x(1-x), а второй -- Px-x^2/2. Легко посчитать,что максимум этой функции (наша оптимальная ставка) оказывается (P+1)/3.
Получается, что завышать стоимость гаража нужно только если он нам кажется недорогим, а если его цена близка к единице, то скорее ставку лучше сделать меньшей, чем цена гаража.
Ещё круче получается, если мы договорились, что компенсация равна не минимуму, а максимуму из ставок. Тогда (если я нигде не ошибся в выкладках:) ) оптимальная ставка равна P/3. Прослеживается аналогия с английским и голландским аукционами, где меньшая цена, которую участник платит по правилам игры приводит к росту ставок.
Если же вернуться к условиям, как они были в фильме (n > 2 участников), то в наших рассуждениях изменятся E(y) и величина компенсации за гараж будет равна (n - 1) * минимальная_ставка (если есть n-1 гараж, т.е. останется без гаража только один участник). Если все участники делают ставки равномерно на отрезке, то минимальная ставка будет распределена по степенному закону, т.е. плотность вероятности будет E(y)=(n-1)*(y^(n-2)). Таким образом при ставке x, в среднем выигрыш получится --
первое слагаемое отвечает за получение гаража, второе -- за компенсацию.