Жызненная задачка из теории игр.
(Видеолекция Алексея Савватеева отлично находится по названию, поэтому не смотрите туда, там спойлер)

В лагере пионеры раздобыли бутылку водки и решили её распить во время лагерного праздника.
Вожатый догадывается о намерениях пионеров.
Распитие возможно в нескольких местах.
Посещение различных мест распития влечёт для вожатого моральные издержки, которые можно измерить количественно (в разных местах они разные).
Если он поймает пионеров за распитием, то получит моральную выгоду, которая тоже измеряется количественно и превышает издержки на посещение любого из мест.
Вожатый обязан проверить хотя бы одно из мест, но не может проверить больше одного.

Для определённости: пусть есть четыре места, издержки для которых составляют 1, 2, 3 и 4 единицы. (Например, каждая единица — это полчаса, т.е. чтобы проверить первое убежище, вожатый потратит мало времени, потому что это где-то близко от общепраздничного сбора, а до последнего убежища придётся лазать по соседнему лесу).
А выгода составляет 5 единиц (столько времени потребуется на то, чтобы возиться с уже пьяными детьми).

Вопрос: какой стратегии должен придерживаться вожатый, чтобы максимизировать свою выгоду минус издержки? Ну и соответственно, что должны предпринять пионеры?

Оба выбора — куда прятаться пионерам и куда идти вожатому — делаются одновременно и однократно.

Здравствуйте, Кодт, Вы писали:

К>Вопрос: какой стратегии должен придерживаться вожатый, чтобы максимизировать свою выгоду минус издержки? Ну и соответственно, что должны предпринять пионеры?

Про выигрыши пионеров от удачного распития в разных местах ты не сказал.

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

Здравствуйте, andyp, Вы писали:

A>Про выигрыши пионеров от удачного распития в разных местах ты не сказал.

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

A>Думаю, что для вожатого будет оптимальным случайный выбор места проверки. Вероятность выбора каждого места должна быть разной. Можно минимизировать как средние так и максимальные потери от проигрыша.

Случайный выбор — это называется смешанная стратегия.

Понятно, что если вожатый проверяет одно место, и пионеры вычислили, какое именно, — то они спрячутся в другом.
И наоборот, если вожатый вычислил, что пионерам надо прятаться в каком-то одном месте, именно туда он и пойдёт. А пионеры, соответственно, именно туда и не спрячутся.

Вопрос в том, как именно выглядит распределение вероятностей.

Здравствуйте, Кодт, Вы писали:

К>Жызненная задачка из теории игр.
К>(Видеолекция Алексея Савватеева отлично находится по названию, поэтому не смотрите туда, там спойлер)
К>В лагере пионеры раздобыли бутылку водки и решили её распить во время лагерного праздника.
К>Вожатый догадывается о намерениях пионеров.
К>Распитие возможно в нескольких местах.
К>Посещение различных мест распития влечёт для вожатого моральные издержки, которые можно измерить количественно (в разных местах они разные).
К>Если он поймает пионеров за распитием, то получит моральную выгоду, которая тоже измеряется количественно и превышает издержки на посещение любого из мест.
К>Вожатый обязан проверить хотя бы одно из мест, но не может проверить больше одного.
К>Для определённости: пусть есть четыре места, издержки для которых составляют 1, 2, 3 и 4 единицы. (Например, каждая единица — это полчаса, т.е. чтобы проверить первое убежище, вожатый потратит мало времени, потому что это где-то близко от общепраздничного сбора, а до последнего убежища придётся лазать по соседнему лесу).
К>А выгода составляет 5 единиц (столько времени потребуется на то, чтобы возиться с уже пьяными детьми).
К>Вопрос: какой стратегии должен придерживаться вожатый, чтобы максимизировать свою выгоду минус издержки? Ну и соответственно, что должны предпринять пионеры?
К>Оба выбора — куда прятаться пионерам и куда идти вожатому — делаются одновременно и однократно.
Все просто: вожатый вызывает взвод полицейских и они вяжут всех во всех возможных местах распития.

Здравствуйте, Кодт, Вы писали:

К>Вопрос в том, как именно выглядит распределение вероятностей.

пусть вероятности выбора пионеров известны и равны w_i

Тогда целевая функция вожатого выглядит как средний выигрыш

gain(v) = sum((gain_i*w_i — loss_i*(1-w_i))*v_i) = sum((5*w_i — loss_i*(1-w_i))*v_i)

v_i — компоненты вероятности выбранные вожатым,
gain_i = 5 для всех i
loss_i = {1 2 3 4};

Это линейное программирование — нам нужно найти максимум линейной функции при линейных ограничениях. {0<=v_i<=1, sum(v_i) = 1} — выпуклый многогранник, поэтому решение будет либо
a) совпадать с одной из граней
b) ему будет принадлежать одно из ребер
с) будет касаться одной из вершин.

Проверим случай с) как самый простой. Пусть max(gain) НЕ достигается в одной из вершин. Пусть целевая функция в вершинах достигает значений G_i, Рассм. такую вершину j, в которой G_j максимальна среди всех вершин. Тогда пойдя по одному из ребер на шаг e мы получим увеличение gain. Т.е.

(1) gain(0..010..0) = G_j = 5*w_j — loss_j(1-w_j)
(2) gain(0..e(1-e)0..0) = (5*w_j — loss_i(1-w_j)) (1- e) + (5*w_k — loss_k(1- w_k))*e = G_j — eG_j + eG_k = G_j — e(G_j — G_k)


При заданных константах G_k не равно G_j при w_j, w_k неравных 0 (можно рассм. разность, подставив константы).

Поэтому G_j-G_k всегда больше 0 => при уходе по ребру получаем уменьшение целевой функции вместо роста. Пришли к противоречию, значит все-таки c).

Написал простенький скрипт, чтобы это проверить. При случайно выбираемых w_i, всегда скатываемся к одной из точек вида v_i = [0..010..0]

Потом не выдержал и посмотрел кино

Здравствуйте, andyp, Вы писали:

A>пусть вероятности выбора пионеров известны и равны w_i

A>Тогда целевая функция вожатого выглядит как средний выигрыш

A>gain(v) = sum((gain_i*w_i — loss_i*(1-w_i))*v_i) = sum((5*w_i — loss_i*(1-w_i))*v_i)

A>v_i — компоненты вероятности выбранные вожатым,
A>gain_i = 5 для всех i
A>loss_i = {1 2 3 4};

Вожатый несёт издержки в любом случае, поэтому формулу надо поправить. Убрать множитель (1-w_i) от loss_i.

A>Это линейное программирование — нам нужно найти максимум линейной функции при линейных ограничениях. {0<=v_i<=1, sum(v_i) = 1} — выпуклый многогранник, поэтому решение будет либо
A>a) совпадать с одной из граней
A>b) ему будет принадлежать одно из ребер
A>с) будет касаться одной из вершин.

Это не совсем линейное программирование, так как нужно одновременно максимизировать gain по v (это задача вожатого) и минимизировать по w (это злой умысел пионеров).
Ну или искать ответ для функции из 8-мерного пространства (4 вероятности у вожатого и 4 у пионеров) на 2-мерную оценку (выигрыш вожатого, выигрыш пионеров).

Нужно искать равновесие.
То есть, пионеры должны демотивировать вожатого (распределить свои вероятности w так, чтобы вожатому было всё равно, как распределять свои v), а вожатый — демотивировать пионеров.

A>Потом не выдержал и посмотрел кино

Внезапно, да?

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, andyp, Вы писали:

A>>пусть вероятности выбора пионеров известны и равны w_i

A>>Тогда целевая функция вожатого выглядит как средний выигрыш

A>>gain(v) = sum((gain_i*w_i — loss_i*(1-w_i))*v_i) = sum((5*w_i — loss_i*(1-w_i))*v_i)

A>>v_i — компоненты вероятности выбранные вожатым,
A>>gain_i = 5 для всех i
A>>loss_i = {1 2 3 4};

К>Вожатый несёт издержки в любом случае, поэтому формулу надо поправить. Убрать множитель (1-w_i) от loss_i.

Вроде все верно. При пионерских вероятностях w_i вожатый может выиграть с вероятностью w_i или проиграть с вероятностью 1-w_i, если пионеры в эту точку не пойдут. Потом усреднил по вероятностям вожатого, чтобы найти средний выигрыш. Можно минимаксный проигрыш рассматривать тогда целевая линейной быть перестанет, что не очень удобно.


A>>Это линейное программирование — нам нужно найти максимум линейной функции при линейных ограничениях. {0<=v_i<=1, sum(v_i) = 1} — выпуклый многогранник, поэтому решение будет либо
A>>a) совпадать с одной из граней
A>>b) ему будет принадлежать одно из ребер
A>>с) будет касаться одной из вершин.

К>Это не совсем линейное программирование, так как нужно одновременно максимизировать gain по v (это задача вожатого) и минимизировать по w (это злой умысел пионеров).

Оно. Я просто попытался доказать, что при ЛЮБЫХ w_i из симплекса и коэффициентах из условия, получаем v_i в вершинах симплекса для максимума целевой функции вожатого при заданных w_i. Т.е. v_i вида [0..010..0] при максимуме целевой функции вожатого. Ты про про максимум по Нешу пишешь (новое для меня понятие, которое я только что посмотрел в вики и понял из лекции, так как теории игр не знаю совсем)- он тоже относится к максимумам, про которые я говорил (один из них).

К>Ну или искать ответ для функции из 8-мерного пространства (4 вероятности у вожатого и 4 у пионеров) на 2-мерную оценку (выигрыш вожатого, выигрыш пионеров).
К>Нужно искать равновесие.
К>То есть, пионеры должны демотивировать вожатого (распределить свои вероятности w так, чтобы вожатому было всё равно, как распределять свои v), а вожатый — демотивировать пионеров.

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

A>>Потом не выдержал и посмотрел кино

К>Внезапно, да?

Наполовину. Савватеев в первой части к такому же выводу пришел — у него решение для v_i — [1000...], правда без линейного программирования. А так красиво, да

Здравствуйте, andyp, Вы писали:

A>Здравствуйте, Кодт, Вы писали:

К>>Здравствуйте, andyp, Вы писали:

A>>>пусть вероятности выбора пионеров известны и равны w_i

A>>>Тогда целевая функция вожатого выглядит как средний выигрыш

A>>>gain(v) = sum((gain_i*w_i — loss_i*(1-w_i))*v_i) = sum((5*w_i — loss_i*(1-w_i))*v_i)

A>>>v_i — компоненты вероятности выбранные вожатым,
A>>>gain_i = 5 для всех i
A>>>loss_i = {1 2 3 4};

К>>Вожатый несёт издержки в любом случае, поэтому формулу надо поправить. Убрать множитель (1-w_i) от loss_i.

A>Вроде все верно. При пионерских вероятностях w_i вожатый может выиграть с вероятностью w_i или проиграть с вероятностью 1-w_i, если пионеры в эту точку не пойдут.

Тогда надо gain_i = {5-1, 5-2, 5-3, 5-4}, потому что в случае успеха (w_i*v_i) вожатый потратит кучу времени на поиски и сэкономит на вытрезвление.

A>Потом усреднил по вероятностям вожатого, чтобы найти средний выигрыш. Можно минимаксный проигрыш рассматривать тогда целевая линейной быть перестанет, что не очень удобно.

A>>>Это линейное программирование — нам нужно найти максимум линейной функции при линейных ограничениях. {0<=v_i<=1, sum(v_i) = 1} — выпуклый многогранник, поэтому решение будет либо
A>>>a) совпадать с одной из граней
A>>>b) ему будет принадлежать одно из ребер
A>>>с) будет касаться одной из вершин.

К>>Это не совсем линейное программирование, так как нужно одновременно максимизировать gain по v (это задача вожатого) и минимизировать по w (это злой умысел пионеров).

A>Оно. Я просто попытался доказать, что при ЛЮБЫХ w_i из симплекса и коэффициентах из условия, получаем v_i в вершинах симплекса для максимума целевой функции вожатого при заданных w_i. Т.е. v_i вида [0..010..0] при максимуме целевой функции вожатого. Ты про про максимум по Нешу пишешь (новое для меня понятие, которое я только что посмотрел в вики и понял из лекции, так как теории игр не знаю совсем)- он тоже относится к максимумам, про которые я говорил (один из них).

Тут где-то затаилась ошибка в логике.

С одной стороны, — действительно, для любой конкретной смешанной стратегии пионеров оптимум вожатого будет на границе симплекса, и уж по крайней мере одна вершина (т.е. чистая стратегия) там попадётся.

Но фокус в том, что — помимо стратегии дефолта, то есть, фиксации убытков, — для каждой конкретной стратегии пионеров эта чистая стратегия вожатого будет разная.
Грубо говоря, это argmax(gain_i*w_i-loss_i*(1-w_i)). То есть, посмотреть, куда (взвешенно) пионеры наведываются чаще всего, и именно туда и пойти.
Если argmax неоднозначный, то граница содержит несколько вершин и имеет соответствующую размерность.

Но ведь пионеры тоже не дураки. Если они знают ход мыслей вожатого (и знают, какую именно чистую стратегию в случае неоднозначности он выберет), то они улучшат свою смешанную стратегию, обнулив вероятность соответствующего компонента.
Тогда вожатый пересчитает argmax, выберет другую чистую стратегию, а пионеры и этот компонент обнулят. И так они допрыгаются до того, что и у пионеров будет чистая стратегия, и вожатый прямо к ним в гости направится. И тогда пионерам все дороги из ямы — только вверх, и они для улучшения возьмут любую стратегию — чистую или смешанную — у которой вот именно этот компонент нулевой, на колу мочало, начинай сначала.

Из этого следует, что такой метод последовательных улучшений — основа линейного программирования — неприемлем.
Собственно говоря, это с самого начала было понятно. Игра на противостоянии, и оценочная функция, удовлетворяющая обе стороны, почти всюду равна нулю (кроме стратегий дефолта, когда одна из сторон сдаётся и минимизирует свои убытки).

A>>>Потом не выдержал и посмотрел кино
К>>Внезапно, да?
A>Наполовину. Савватеев в первой части к такому же выводу пришел — у него решение для v_i — [1000...], правда без линейного программирования. А так красиво, да

Это для конкретно этих значений.
А вот если бы вожатый был гораздо сильнее мотивирован найти пионеров, то его равновесный выигрыш E был бы равен
G*w1-L1 = G*w2-L2 = G*w3-L3 = G*w4-L4 = E
4E = G-(L1+L2+L3+L4)
E = (G-(L1+L2+L3+L4))/4
где G — ожидаемый доход при удаче, L1..L4 — безусловные расходы
и если он выше дефолта -min(L1,L2,L3,L4) = -L1, то у вожатого будет смешанная стратегия — с некоторыми вероятностями заглянуть в каждую нычку.

Дальше надо считать систему уравнений, мне немножко лень...

Здравствуйте, Кодт, Вы писали:


К>Тогда надо gain_i = {5-1, 5-2, 5-3, 5-4}, потому что в случае успеха (w_i*v_i) вожатый потратит кучу времени на поиски и сэкономит на вытрезвление.

Да можно и так. Важно что есть Цена выигрыша и цена проигрыша и есть средний выигрыш — собственно сабж для оптимизации. У пионеров просто оптимизировал sum(-v_i*w_i) — по твоему условию (они фактически только за проигрыш платят, когда их спалили).


A>>Оно. Я просто попытался доказать, что при ЛЮБЫХ w_i из симплекса и коэффициентах из условия, получаем v_i в вершинах симплекса для максимума целевой функции вожатого при заданных w_i. Т.е. v_i вида [0..010..0] при максимуме целевой функции вожатого. Ты про про максимум по Нешу пишешь (новое для меня понятие, которое я только что посмотрел в вики и понял из лекции, так как теории игр не знаю совсем)- он тоже относится к максимумам, про которые я говорил (один из них).

К>Тут где-то затаилась ошибка в логике.


Да это в моем тексте неясность — читать нужно так: "Я просто попытался доказать, что при ЛЮБЫХ w_i из симплекса и коэффициентах ВЗЯТЫХ из условия...". Разумеется, в общем случае граница может совпадать с гранью или ребром симплекса, о чем сразу и писал. Жаль, что невнятно вышло. Халява с вершинами была только для твоего (ну может еще каких) наборов циферок.

К>С одной стороны, — действительно, для любой конкретной смешанной стратегии пионеров оптимум вожатого будет на границе симплекса, и уж по крайней мере одна вершина (т.е. чистая стратегия) там попадётся.

К>Но фокус в том, что — помимо стратегии дефолта, то есть, фиксации убытков, — для каждой конкретной стратегии пионеров эта чистая стратегия вожатого будет разная.
К>Грубо говоря, это argmax(gain_i*w_i-loss_i*(1-w_i)). То есть, посмотреть, куда (взвешенно) пионеры наведываются чаще всего, и именно туда и пойти.
К>Если argmax неоднозначный, то граница содержит несколько вершин и имеет соответствующую размерность.

Именно поэтому с минимаксом связываться не стал. В стат. радиотехнике оба (средний проигрыш и минимакс) имеют право на жизнь и используются. Либо ты минимизируешь наихудший проигрыш, либо — средний. Я про средний писал.

К>Но ведь пионеры тоже не дураки. Если они знают ход мыслей вожатого (и знают, какую именно чистую стратегию в случае неоднозначности он выберет), то они улучшат свою смешанную стратегию, обнулив вероятность соответствующего компонента.
К>Тогда вожатый пересчитает argmax, выберет другую чистую стратегию, а пионеры и этот компонент обнулят. И так они допрыгаются до того, что и у пионеров будет чистая стратегия, и вожатый прямо к ним в гости направится. И тогда пионерам все дороги из ямы — только вверх, и они для улучшения возьмут любую стратегию — чистую или смешанную — у которой вот именно этот компонент нулевой, на колу мочало, начинай сначала.

Пионеры не то что не дураки. Даже не зная стратегию вожатого (предполагаем, что у нас вероятностная игра) они всегда должны ее оценивать по розыгрышам. Вожатый — аналогично. Т.е. будет получаться, что какое-то время после изменения стратегии одна из сторон сильно проигрывает, потому она адаптируется и минимизирует потери (максимизирует выигрыш, если угодно). Снова имеем равновесие для выбранных стратегий.

К>Из этого следует, что такой метод последовательных улучшений — основа линейного программирования — неприемлем.
К>Собственно говоря, это с самого начала было понятно. Игра на противостоянии, и оценочная функция, удовлетворяющая обе стороны, почти всюду равна нулю (кроме стратегий дефолта, когда одна из сторон сдаётся и минимизирует свои убытки).

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

Это кстати +100 автору аналитического решения для равновесия Не все можно порешать моделированием.

К>Это для конкретно этих значений.

Согласен полностью.

PS
К>А вот если бы вожатый был гораздо сильнее мотивирован найти пионеров, то его равновесный выигрыш E был бы равен
К>G*w1-L1 = G*w2-L2 = G*w3-L3 = G*w4-L4 = E
К>4E = G-(L1+L2+L3+L4)
К>E = (G-(L1+L2+L3+L4))/4
К>где G — ожидаемый доход при удаче, L1..L4 — безусловные расходы
К>и если он выше дефолта -min(L1,L2,L3,L4) = -L1, то у вожатого будет смешанная стратегия — с некоторыми вероятностями заглянуть в каждую нычку.

ИМХО, проще посчитать конкретную целевую функцию в вершинах симплекса (благо, их мало). Если она разная для всех вершин — имеем максимум в вершинах. Одинакова для двух вершин — на ребре, Для 3х — на грани. Многогранник у нас, слава богу, правильный.

Здравствуйте, Кодт, Вы писали:

К>Жызненная задачка из теории игр.
К>(Видеолекция Алексея Савватеева отлично находится по названию, поэтому не смотрите туда, там спойлер)

К>В лагере пионеры раздобыли бутылку водки и решили её распить во время лагерного праздника.
К>Вожатый догадывается о намерениях пионеров.
К>Распитие возможно в нескольких местах.
К>Посещение различных мест распития влечёт для вожатого моральные издержки, которые можно измерить количественно (в разных местах они разные).
К>Если он поймает пионеров за распитием, то получит моральную выгоду, которая тоже измеряется количественно и превышает издержки на посещение любого из мест.
К>Вожатый обязан проверить хотя бы одно из мест, но не может проверить больше одного.

К>Для определённости: пусть есть четыре места, издержки для которых составляют 1, 2, 3 и 4 единицы. (Например, каждая единица — это полчаса, т.е. чтобы проверить первое убежище, вожатый потратит мало времени, потому что это где-то близко от общепраздничного сбора, а до последнего убежища придётся лазать по соседнему лесу).
К>А выгода составляет 5 единиц (столько времени потребуется на то, чтобы возиться с уже пьяными детьми).

К>Вопрос: какой стратегии должен придерживаться вожатый, чтобы максимизировать свою выгоду минус издержки? Ну и соответственно, что должны предпринять пионеры?

К>Оба выбора — куда прятаться пионерам и куда идти вожатому — делаются одновременно и однократно.

1. Обозначим:
— вероятность похода вожатого в место i через wi
— вероятность распития пионерами в месте i через pi
— количество бонусов, которые получает вожатый при поимке пионеров в месте i через bi (выгода минус издержки)

2. Очевидно, что СУМ wi = 1, СУМ pi = 1

3. Нужно равновесие.
а) матожидание бонуса вожатого во всех местах должно быть одинаково (опять же, мы должны учитывать вероятность того, что в это место пойдут пионеры)
б) вероятность быть пойманным во всех местах должна быть одинакова (конечно, мы должны учитывать вероятность того, что в это место придет вожатый)

3а. Матожидание бонуса вожатого в месте i равно bi * wi * pi (бонус получаем, если вожатый туда пошел и пионеры тоже туда пошли).

Т.к. матожидание всех мест одинаково, то получаем
b1 * w1 * p1 = b2 * w2 * p2 = b3 * w3 * p3 ...

Из этого равенства можно выразить p2, p3 и т.д.
В общем виде pi = (b1/bi) * (w1/wi) * p1

Для упрощения сделаем замену b1/bi = ci получаем pi = ci * (w1/wi) * p1

3б. Вероятность успеха мероприятие пионеров в месте i равно pi * (1 — wi) (пионеры туда пошли, а вожатый нет)

Т.к. вероятность всех мест одинакова, то получаем
p1 * (1 — w1) = p2 * (1 — w2) = p3 * (1 — w3) ...

Из этого равенства можно выразить p2, p3 и т.д.
В общем виде pi = (1-w1) / (1-wi) * p1

3в Приравниваем pi из 3а и 3б

ci * (w1/wi) * p1 = (1-w1) / (1-wi) * p1, сокращаем на p1
ci * (w1/wi) = (1-w1) / (1-wi), выражаем wi через w1

wi = ci * w1 / (1 — w1 + ci * w1)

3г. Очевидно, что сумма всех wi равняется единице, поэтому нужно решить систему уравнений

wi = ci * w1 / (1 — w1 + ci * w1)
СУММА wi = 1

3д Решив систему получим значения wi. Далее аналогично решаем систему для pi (их сумма тоже равна 1)
pi = (1-w1) / (1-wi) * p1
СУММА pi = 1

Получаем ответ

4. Теперь код

import numpy as np
from scipy.optimize import bisect

# исходные данные
b_arr = np.array([1,4]) # бонусы вожатого
c_arr = np.min(b_arr) / b_arr # замена b1/bi

# решение системы уравнений для wi
def calc_wi(w0, ci): 
    return ci * w0 / (1 - w0 + ci * w0)

def goal_sum_wi(w0):
    return np.sum(calc_wi(w0, c_arr)) - 1
w0 = bisect(goal_sum_wi, 0, 1)
w_arr = calc_wi(w0, c_arr)

# решение системы уравнений для pi
def calc_pi(w0, p0, wi):
    return (1-w0) / (1-wi) * p0

def goal_sum_pi(p0):
    return np.sum(calc_pi(w0, p0, w_arr)) - 1
p0 = bisect(goal_sum_pi, 0, 1)
p_arr = calc_pi(w0, p0, w_arr)

# выводим результат
print("Бонусы вожатого:", b_arr)
print("Вероятность выбора для вожатого (стратегия):", w_arr)
print("Вероятность поимки:", p_arr * w_arr)
print("Матожидание бонусов для вожатого:", p_arr * w_arr * b_arr)
print()
print("Вероятность выбора для пионеров (стратегия):", p_arr)
print("Вероятность успешного распития:", p_arr * (1 - w_arr))
print()
print("Итого вероятность поимки:", np.sum(p_arr * w_arr))
print("Итого вероятность успешного распития:", np.sum(p_arr * (1 - w_arr)))

5. Результаты

Бонусы вожатого: [1 4]
Вероятность выбора для вожатого (стратегия): [ 0.66666667 0.33333333]
Вероятность поимки: [ 0.44444444 0.11111111]
Матожидание бонусов для вожатого: [ 0.44444444 0.44444444]

Вероятность выбора для пионеров (стратегия): [ 0.66666667 0.33333333]
Вероятность успешного распития: [ 0.22222222 0.22222222]

Итого вероятность поимки: 0.555555555555
Итого вероятность успешного распития: 0.444444444445

Бонусы вожатого: [1 2 3 4]
Вероятность выбора для вожатого (стратегия): [ 0.40865732 0.25680033 0.18722686 0.1473155 ]
Вероятность поимки: [ 0.12704082 0.06352041 0.04234694 0.03176021]
Матожидание бонусов для вожатого: [ 0.12704082 0.12704082 0.12704082 0.12704082]

Вероятность выбора для пионеров (стратегия): [ 0.31087373 0.24735332 0.22617985 0.21559311]
Вероятность успешного распития: [ 0.1838329 0.1838329 0.1838329 0.1838329]

Итого вероятность поимки: 0.264668384659
Итого вероятность успешного распития: 0.735331615347

Бонусы вожатого: [ 1 500]
Вероятность выбора для вожатого (стратегия): [ 0.95719303 0.04280697]
Вероятность поимки: [ 0.91621849 0.00183244]
Матожидание бонусов для вожатого: [ 0.91621849 0.91621849]

Вероятность выбора для пионеров (стратегия): [ 0.95719303 0.04280697]
Вероятность успешного распития: [ 0.04097454 0.04097454]

Итого вероятность поимки: 0.918050926966
Итого вероятность успешного распития: 0.0819490730343

Интересно, что вероятность успеха мероприятия каким-то образом зависит от бонусов вожатого. Вариант бонусов 1-4, сильно отличается от варианта бонусов 1-500. Может есть какая-то ошибка в рассуждениях?

Здравствуйте, Буравчик, Вы писали:

Б>Интересно, что вероятность успеха мероприятия каким-то образом зависит от бонусов вожатого. Вариант бонусов 1-4, сильно отличается от варианта бонусов 1-500. Может есть какая-то ошибка в рассуждениях?

Посмотрел лекцию (правда, мельком).
Действительно, задача чувствительна к бонусам вожатого. Значит, все-таки правильно.

Надеюсь и в остальном не ошибся

Здравствуйте, Кодт, Вы писали:
К>Оба выбора — куда прятаться пионерам и куда идти вожатому — делаются одновременно и однократно.
Интересно. По-моему, задача неразрешима.
Упростим: точек — всего две.
Обе стороны мыслят рационально.
Допустим, вожатый выбирает более дешёвую точку — чтобы максимизировать свою выгоду. Пионеры, думают: ок, вожатый пойдёт в ближний схрон, давайте пить в дальнем.
Вожатый: ежу понятно, что в ближнем они прятаться не будут — пойду-ка я дальний проверю.
Пионеры: ну, он же опытный — таких хитрых, как мы, у него уже десять сезонов было. Давайте напьёмся прямо у него под носом!

Здравствуйте, Кодт, Вы писали:
К>Оба выбора — куда прятаться пионерам и куда идти вожатому — делаются одновременно и однократно.
Как насчёт обратной задачи: при каких стоимостях проверки мест стратегия вожатого будет другой?
При любых ли соотношениях стоимостей/выигрышей достаточно ли добавить в "смесь" место с дешёвой проверкой, чтобы гарантированно защитить пьянку?

Здравствуйте, Sinclair, Вы писали:

S>Упростим: точек — всего две.
S>Обе стороны мыслят рационально.
S>Допустим, вожатый выбирает более дешёвую точку — чтобы максимизировать свою выгоду. Пионеры, думают: ок, вожатый пойдёт в ближний схрон, давайте пить в дальнем.
S>Вожатый: ежу понятно, что в ближнем они прятаться не будут — пойду-ка я дальний проверю.
S>Пионеры: ну, он же опытный — таких хитрых, как мы, у него уже десять сезонов было. Давайте напьёмся прямо у него под носом!

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

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, Кодт, Вы писали:
К>>Оба выбора — куда прятаться пионерам и куда идти вожатому — делаются одновременно и однократно.
S>Как насчёт обратной задачи: при каких стоимостях проверки мест стратегия вожатого будет другой?
S>При любых ли соотношениях стоимостей/выигрышей достаточно ли добавить в "смесь" место с дешёвой проверкой, чтобы гарантированно защитить пьянку?

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

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

Здравствуйте, Sinclair, Вы писали:

S>Пионеры: ну, он же опытный — таких хитрых, как мы, у него уже десять сезонов было. Давайте напьёмся прямо у него под носом!

Проклятый докторишка думал, что мы его перехитрим, а мы на кой чёрт пошли в обход!

Здравствуйте, Буравчик, Вы писали:
Б>Стоимости/выигрыш однозначно определяют с какой вероятностью в определенное место пойдет вожатый и пионеры. Добавление "дешевого места" не позволит гарантировано защитить пьянку, просто снизит вероятность похода вожатого в это место (но снизит не до нуля).
Вы уже знаете правильное решение?
Обратите внимание на то, какая стратегия вожатого оказывается равновесной.

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

Здравствуйте, Sinclair, Вы писали:

S>Вы уже знаете правильное решение?
S>Обратите внимание на то, какая стратегия вожатого оказывается равновесной.

Нет, я не знаю правильного решения. Я предложил свое (и думаю, что оно верное)
Так какая стратегия вожатого оказывается равновесной?

Б>>Все будет иначе, если появится место с отрицательным выигрышем. Вот тогда точно пьянка пройдет, т.к. вожатый туда не пойдет даже если будет точно знать, что пионеры именно там.
S>Не обязательно. По условиям задачи получается, что у вожатого всегда выигрыш отрицателен. Он уже не пытается поймать пионеров, а просто минимизирует потери.

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

Так написано в задаче в начале топика.

Здравствуйте, Буравчик, Вы писали:
Б>Нет, я не знаю правильного решения. Я предложил свое (и думаю, что оно верное)
Б>Так какая стратегия вожатого оказывается равновесной?
Искать пионеров там, где их нету. У него получается гарантированный проигрыш; но матожидание проигрыша при визите в любое из других мест будет ещё хуже.
S>>Не обязательно. По условиям задачи получается, что у вожатого всегда выигрыш отрицателен. Он уже не пытается поймать пионеров, а просто минимизирует потери.
Б>

Б>Если он поймает пионеров за распитием, то получит моральную выгоду, которая тоже измеряется количественно и превышает издержки на посещение любого из мест.

Б>Так написано в задаче в начале топика.
"всегда" имеется в виду "в среднем при множестве повторов при выборе какой-либо стратегии".
Получается так, что матожидание выигрыша в заданных условиях всегда отрицательное. И задача переходит от "поймать пионеров" к "минимизировать расходы на оперативно-розыскные мероприятия".

Здравствуйте, Sinclair, Вы писали:

S>Искать пионеров там, где их нету. У него получается гарантированный проигрыш; но матожидание проигрыша при визите в любое из других мест будет ещё хуже.

Что значит их нет? Они есть одновременно везде (с определенной вероятностью).

Если существует какое-то место, которое более выгодно для вожатого по сравнению с другими, то он, очевидно пойдет туда (вероятность его похода туда увеличится). Но тогда пионеры скорее всего туда не пойдут (вероятность их похода в это место уменьшится). Но тогда это место станет менее выгодным для вожатого. Значит скорее всего он туда не пойдет (вероятность его похода туда уменьшится).

Эти вероятности так и будут прыгать, пока не установится равновесие. А заключается оно в том, что:
— матожидание результата для вожатого в любом месте одинаковое, куда бы он не пошел (при этом учитывается вероятность похода пионеров в каждое место)
— вероятность успешной попойки для пионеров в любом месте одинаковая, куда бы они не пошли (при этом учитывается вероятность похода вожатого в каждое место)

S>"всегда" имеется в виду "в среднем при множестве повторов при выборе какой-либо стратегии".
S>Получается так, что матожидание выигрыша в заданных условиях всегда отрицательное. И задача переходит от "поймать пионеров" к "минимизировать расходы на оперативно-розыскные мероприятия".

При равновесии матожидание выигрыша вожатого в каждом раунде одинаковое. И не зависит от того, какое место он выберет.
Если матожидание какого-то места отличается от других, то равновесие нарушается.