Теория игр. Континуум стратегий

[atlakatl]

Два игрока одновременно называют числа из отрезка $[4, 10]$. Игрок, назвавший большее число, забирает число второго. Второй игрок забирает половину числа первого. При равенстве чисел игроки остаются при своих.

Например:
1-й игрок: $7$
2-й игрок: $4$
Первый игрок получает $4$, второй получает $7/2=3,5$. В результате первый игрок выигрывает $4-3,5=0,5$

Найти оптимальную стратегию.

Я к чему? В Равновесии Нэша говорится о НАБОРЕ стратегий, т.е. о конечном числе дискретных вариантов.

Так для 3-х стратегий $(4, 7, 10)$ данной игры оптимальным является в $4/7$ игр называть $4$, в $2/7$ - $7$, в $1/7$ - $10$.

В случае 4-х стратегий $(4, 6, 8, 10)$ оптимально равновероятно называть $4$, $6$ и $10$, а $8$ не называть вовсе.

Что видим? Оптимальные стратегии совершенно между собой не схожи.
А что будет при континууме стратегий? Существует ли тогда оптимальная стратегия? Можно ли её найти в виде алгебраического уравнения? А если только численно (каким методом?), то будет ли результат при увеличении числа стратегий сходиться? Или при увеличении числа вариантов он будет неустойчив?

[_Ivana]

Написал программу, ищущую оптимальную стратегию (в моих представлениях) в зависимости от количества N вариантов выбора - отрезок [4, 10] делится на N-1 равных интервалов, в качестве возможных вариантов берутся края интервалов. При анализе N от 3 до 200 решения нашлись только для N = 3, 4, 6 (первый столбец - варианты выбора, второй - вероятности):

X =
    4.0000    0.5714
    7.0000    0.2857
   10.0000    0.1429

X =
    4.0000    0.3333
    6.0000    0.3333
    8.0000         0
   10.0000    0.3333

X =
    4.0000    0.3806
    5.2000    0.0810
    6.4000    0.2227
    7.6000    0.0202
    8.8000         0
   10.0000    0.2955

Первые 2 ответа совпали с цифрами ТС. Может в алгоритме пропускаются возможные стратегии, надо ещё подумать. Может попробовать погонять его на неравномерной сетке вариантов.

(Оффтоп)

ЗЫ интересная задачка, да и тема вообще. Про Нэша только фильм смотрел, больше ничего не знаю

-- 04.10.2012, 00:57 --

UPD при случайной равномерно распределенной на отрезке сетке иногда проскальзывают решения и для большего количества вариантов (в теге оффтопика).

(Оффтоп)

X =
    4.0000    0.4518
    5.2875    0.0352
    6.3674    0.2274
    7.7783    0.0471
   10.0000    0.2386

X =
    4.0000    0.3130
    4.8551    0.0392
    5.0177    0.0154
    5.5410    0.1402
    6.2146    0.0367
    6.8708    0.1058
    7.9706    0.0000
   10.0000    0.3496

X =
    4.0000    0.6465
    5.9798    0.0156
    6.1059    0.0123
    6.9323    0.1471
    8.1984    0.0576
    8.9222    0.0380
   10.0000    0.0828

X =
    4.0000    0.4549
    5.2541    0.0225
    5.3900    0.0000
    5.7370    0.1076
    6.7446    0.1199
    7.6592    0.0491
    8.0252    0.0100
   10.0000    0.2361

X =
    4.0000    0.5525
    5.5837    0.0148
    5.6729    0.0079
    5.9107    0.0497
    6.4954    0.0785
    7.1070    0.0000
    7.7128    0.1385
   10.0000    0.1580

X =
    4.0000    0.5884
    6.0032    0.0790
    6.7531    0.0000
    6.7869    0.0840
    7.5175    0.0455
    7.8453    0.0067
    7.9735    0.0127
    8.1949    0.0197
    8.5904    0.0348
   10.0000    0.1293

X =
    4.0000    0.5545
    5.5612    0.0069
    5.6387    0.0129
    5.8635    0.0422
    6.1852    0.0319
    6.6913    0.0000
    6.9181    0.1147
    7.5976    0.0062
    8.1260    0.0742
   10.0000    0.1564

[_Ivana]

Если сетку сделать равномерной, но со смещением от края интервала, то для 8, 10 точек можно найти зону существования решений, даже некая непрерывность присутствует
http://s49.radikal.ru/i125/1210/0c/ad0c9018dddd.jpg
http://s017.radikal.ru/i443/1210/2e/ecf3e2606800.jpg
Случай четырех точек со смещением сетки во внутренних точках
http://s017.radikal.ru/i415/1210/ef/6b1c709d8d4a.jpg

[atlakatl]

Нашёл ещё решение при равномерно размещённых ПЯТИ точках:
$P(4)=2/11$
$P(5.5)=4/11$
$P(7)=0$
$P(8.5)=0$
$P(10)=5/11$
Что такое "оптимальная стратегия?
Игрок, её придерживающийся, при ЛЮБОЙ стратегии соперника не проиграет.
В тоже время, если один из игроков СТРОГО придерживается оптимальной стратегии, то второй может не париться с вероятностями, а тупо называть одно из чисел:
Для $N=3$ это $4, 7, 10$
Для $N=4$ это $4, 6, 10$
Для $N=5$ это $4, 5.5, 10$
Для $N=6$ это $4, 5.2, 6.4, 7.6, 10$ && Результат _Ivana
И в общем случае теорема:
Если игрок A строго придерживается стратегии F, то существует по крайней мере одно число, называя которое, игрок B достигает неотрицательного результата. Если выигрыш игрока B равен нулю, то значит стратегия F игрока A оптимальна.
Это даёт способ проверки решения на оптимальность: просто просчитаем выигрыш для каждого числа из достаточно плотной сетки отрезка $[4, 10]$. Если лучший результат неположителен, то стратегия оптимальна.
_Ivana просчитал стратегии аж до $N=10$. Пока системы не видно. Разве что кардинально увеличивая $N$, что-нибудь заметим?
Так всё-таки интересно, существует ли "стратегия Бога" для континуума? Иными словами, может ли игрок A задать такую $F=p(x), x=[4, 10]$, что игрок B не сможет подобрать число, дающее ему положительный выигрыш?

[epros]

atlakatl в сообщении #626112 писал(а):

Первый игрок получает 4, второй получает 7/2=3,5. В результате первый игрок выигрывает 4-3,5=0,5

Упс. Отсюда, наконец, мы начинаем догадываться, что речь идёт об игре с нулевой суммой. Что отнюдь не было самоочевидно из изложенных в первом абзаце условий...

atlakatl в сообщении #626112 писал(а):

В Равновесии Нэша говорится о НАБОРЕ стратегий, т.е. о конечном числе дискретных вариантов.

Впервые слышу об этом. Обычно имеется в виду любое множество стратегий.

atlakatl в сообщении #626112 писал(а):

Так для 3-х стратегий (4, 7, 10) данной игры оптимальным является в 4/7 игр называть 4, в 2/7 - 7, в 1/7 - 10.

В случае 4-х стратегий (4, 6, 8, 10) оптимально равновероятно называть 4, 6 и 10, а 8 не называть вовсе.

Насколько я вижу, сие означает, что смешанные стратегии допустимы условиями задачи. Что, опять же, не было самоочевидно из условий...

atlakatl в сообщении #626112 писал(а):

А что будет при континууме стратегий? Существует ли тогда оптимальная стратегия?

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

-- Чт окт 04, 2012 10:45:22 --

В общем, копните в: Роджер Брюс Майерсон, «Теория игр: анализ конфликта».

[_Ivana]

atlakatl в сообщении #626714 писал(а):

Нашёл ещё решение при равномерно размещённых ПЯТИ точках:
$P(4)=2/11$
$P(5.5)=4/11$
$P(7)=0$
$P(8.5)=0$
$P(10)=5/11$

После работы проверю ваше решение на отсутствие "дыр", ибо есть подозрения в существовании оных Да и ещё погоняю алгоритм.

[_Ivana]

Проверил. Дыр нет А мой алгоритм это решение (и наверное много других) пропустил из-за наличия дыр в нем самом, куда проваливаются существующие решения. Я подозревал об этом, на примере пяти равномерных точек убедился. Буду латать дыры в алгоритме, если получится. Точнее, придется придумывать другой.

[atlakatl]

_Ivana в сообщении #626980 писал(а):

придется придумывать другой

Я программировал матзадачи только в студенчестве. А позже только базы данных на FoxPro.
Сейчас БУКВАЛЬНО нахожусь в глубине сибирских болот. Интернет мобильный и медленный. Поэтому доступа к нормальному ПО не имею. Да и осваивать его долго.
Тем не менее, позволю себе поумничать. Может, что-то натолкнёт на мысли.
Имеем $N$ точек на $[4, 10]$. Сразу определяемся с их положением. Идеально равномерное размещение.
1. Задаёмся распределением вероятностей $p_j$ по всем эти точкам. Просто придаём им неотрицательные значения в некотором диапазоне, а затем перенормировываем, чтобы их сумма равнялась 1.
2. Сканируем по всем точкам:
а) Подсчитываем выигрыш/проигрыш каждой точки по формуле $F_i=\sum(p_j f(i, j))$, где $f(i, j)$ наша функция для i-й и j-й точек.
б) Тогда критерием оптимальности будет $Z=\max(F_i)$, где $i=1, ..., N$ - т.е. максимальный ПРОИГРЫШ при выборе i-й точки.
в) Каким-то методом (каким?) изменяем вероятности $p_j$. Если новый $Z$ будет МЕНЬШЕ прежнего, то запоминаем новый минимум.
г) Так продолжаем, пока достаточно не приблизимся к 0 по $Z$. Оптимальная стратегия найдена.

[_Ivana]

atlakatl Буквально сейчас реализовал почти то же самое. Идея лежит на поверхности - вместо расчета вероятностей берем их случайное распределение, прогоняем много раз, собираем случаи когда максимальный проигрыш меньше заданного порога. Затем я беру среднее арифметическое этих случаев - думаю это должно приблизить решение к искомому. А вот дальше надо придумать как оптимальнее танцевать вокруг него, уменьшая проигрыш. Наверное суть танца будет сводиться колебании каждой найденной вероятности по нормальному распределению около спрогнозированного матожидания, регулируя дисперсию задаем степень танца.

[atlakatl]

_Ivana в сообщении #627021 писал(а):

Затем я беру среднее арифметическое этих случаев - думаю это должно приблизить решение к искомому

Не понимаю. После моего $2г$, Вашего

_Ivana в сообщении #627021 писал(а):

максимальный проигрыш меньше заданного порога

делать ничего не надо. Оптимум для $N$ точек найден.
Или мы говорим о разных вещах?

[_Ivana]

Речь о получении первоначального приближения к искомому решению, его можно получать разными способами, хоть вашим, хоть моим, на примере 7 точек я его получил. А вот дальше искать минимум методом малых возмущений этого полученного приближения. Сейчас попробую реализовать.

[_Ivana]

На первый взгляд создается ощущение, что даже для конечного набора точек функция максимального проигрыша имеет ненулевые локальные минимумы, попав в который уменьшить их у меня пока не получается. Существует ли всегда минимум равный нулю - вполне вероятно, но вопрос его поиска я пока не решил.
Пример для 10 равномерных точек: первая колонка - варианты выбора, вторая - вероятности моей стратегии, третья - мой проигрыш, если я буду придерживаться своей стратегии, а соперник - постоянно выбирать этот вариант

    4.0000    0.105099736797318    0.0012
    4.6667    0.180587708104869    0.0012
    5.3333    0.056411379525647    0.0015
    6.0000    0.134054253818774    0.0015
    6.6667    0.007193631703335   -0.0803
    7.3333    0.000051376532075   -0.5617
    8.0000    0.000290150339095   -1.0659
    8.6667    0.000024355539202   -1.5701
    9.3333    0.000052097477755   -2.0752
   10.0000    0.516235310161932    0.0009

Меньше $0.0015$ опуститься пока не удалось

[_Ivana]

На текущий момент результаты таковы: уменьшить максимальный проигрыш до нуля не удалось, может неоптимальный алгоритм. Но для каждого количества точек находится относительно небольшой по величине минимум. По ссылкам 4 графика - для 20, 40, 100 и 200 точек, максимальный проигрыш указан в заголовке. Некая тенденция прослеживается, но она может быть вызвана неоптимальностью моего алгоритма, дающего ненулевой проигрыш. Да и единичную сумму вероятностей я выравниваю при возмущениях за счет последнего варианта, может поэтому он так вылетает.
http://s61.radikal.ru/i171/1210/5c/38d0b5bc7991.jpg
http://s55.radikal.ru/i150/1210/eb/fe8618a22680.jpg
http://s018.radikal.ru/i514/1210/66/42f3adc20d6e.jpg
http://s56.radikal.ru/i151/1210/a9/ffb5744d5768.jpg

[_Ivana]

Некоторая шлифовка алгоритма принесла плоды - при 10 точках опустился до уровня проигрыша в $5.2538e-07$

   4.000000000000000   0.095242907207318   0.000000525343307
   4.666666666666667   0.190471629377869   0.000000525375410
   5.333333333333333   0.047619089414647  -0.000010507442107
   6.000000000000000   0.142860945903774   0.000000525374884
   6.666666666666666                   0  -0.079352364945924
   7.333333333333334                   0  -0.587288092978055
   8.000000000000000                   0  -1.095223821010185
   8.666666666666666                   0  -1.603159549042315
   9.333333333333334                   0  -2.111095277074447
  10.000000000000000   0.523806306096392   0.000000525375382

Похоже это и есть оптимальная стратегия. Думаю, для бОльшего количества точек тоже удастся существенно снизить уровни проигрыша, но качественная картина стратегий от этого имхо вряд ли поменяется.

[atlakatl]

Небольшое манипулирование Вашими результатами при $N=10$ дало абсолютно точные значения:
$p(4) = 2/21$
$p(4.6666) = 4/21$
$p(5.3333) = 1/21$
$p(6) = 3/21$
$p(10) = 11/21$
Рассматривая графики при всё больших $N$, можно экстраполировать в континуум следующую функцию:
$p(x)=k$, $x=[4, A]$
$p(x)=0$, $x=(A, 10)$
$p(10)=B$
$k$ - плотность вероятности. Для начала принимаем её за константу на всём $[4, A]$.
Ясно, что $k (A-4) + B = 1$. Отсюда $B = 1 - k (A -4)$.
Таким образом, мы имеем критерий оптимальности по двум независимым переменным $k$ и $A$. Осталось их явно определить. Будет время, займусь таким подсчётом.
А в дальнейшем можно внимательней численно исследовать поведение $k$ на $[4, A]$ при больших $N$.
При $p(10)$, видимо, изолированная точка.