Задачка о трех фирмах и распределении гранта

[Munuvonaza]

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

Фонд готов выделить трем фирмам A, B и C грант объемом 121 у.е.. Фирмы могут распределить грант между собой любым образом в соответствии с договоренностью, которую они должны принять и подписать ДО получения гранта.
Возможен вариант, когда только две фирмы смогли договориться, в таком случае третья не получает ничего, а другие две - в зависимости от того, что это за фирмы. Если сотрудничают A и B - то получают 118 у.е., если A и C - то получают 84 у.е., а если B и C - то получают всего 50 у.е.
Единственная задача каждой фирмы - максимизировать прибыль. Фирмы не связаны какими-то личными отношениями и обязаны принимать вариант сделки, если он выгоднее предыдущего предложенного варианта.
Соглашение считается принятым, когда или все три фирмы договорились, или две фирмы имеют вариант договора, после которого предложение третьей фирмы не поменяет решение ни одной из них.
Если фирмы не смогут договориться за 20 раундов обсуждений, то никто не получит грант вообще.

На первый взгляд кажется, что фирма C в любом случае в проигрыше. При делении поровну между тремя фирмами, каждая получит 40 у.е. (одна из фирм - 41 у.е.), что значительно меньше, чем если A решит сотрудничать с B - в таком случае каждая может получить по 59 у.е., оставив фирму C ни с чем.
Однако фирма C, зная такой расклад, может предложить фирме A, к примеру, 80 у.е., что больше чем в предыдущем случае, и еще оставив себе 4 у.е, однако не проиграв.
Фирма B, не желая проигрывать в таком случае, может предложить фирме A, к примеру 100 у.е, что больше чем в предыдущем случае, оставив себе 18 у.е.
Однако в таком случае фирма C может предложить уже фирме B вариант, к примеру, 46 у.е., оставив себе 4 у.е. И так далее.

Несмотря на то, что при соглашении только двух групп, фирма C имеет самый низкий вариант бюджета гранта, она может его перебить большим значением, чем A или B. Аналогичная логика и с другими фирмами. То есть, следуя такому простому рассуждению можно предположить, что задача не имеет решения - то есть фирмы не смогут договориться. Однако каждая фирма понимает, что если не сможет договориться, то получить ноль, а значит станет договариваться, что противоречит предыдущему утверждению.

Видится, что это хитро сформулированная задача на т.н. Общее знание (Common knowledge), то есть из той же серии, что легендарная задача про голубоглазых и кареглазых островитян. Но как подступиться к ее решению - непонятно - хотелось бы услышать совет. Спасибо

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

[podih]

Munuvonaza в сообщении #1376612 писал(а):

Однако фирма C, зная такой расклад, может предложить фирме A, к примеру, 80 у.е

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

[Munuvonaza]

podih в сообщении #1376616 писал(а):

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

Вероятно формулировка получилась не совсем точной. Фонд гранта не может быть выделен одной фирме - он выделяется или двум, или трем фирмам сразу - на всех вместе. То есть грант делится в любом случае. Как именно будут делить полученный грант между собой фирмы - фонд не знает и его это не интересует.
Условно говоря, в фонд приходят или три или две договорившиеся фирмы, и говорят, что договорились между собой и получают сумму в соответствии с условием задачи. Условно, приходят B и C, говорят что договорились между собой, а с A не смогли договориться, и получают 50 у.е. на двоих.
Однако к моменту прихода в фонд, у них уже должна быть заключенная договоренность, как они будут делить полученные средства. После получения гранта уже нельзя передоговориться или передумать.

podih в сообщении #1376616 писал(а):

Не выигравшая тендер фирма не проигрывает ничего, оставаясь при своих.

По условию предполагается, что это поражение. Могли бы выиграть тендер, а не выиграли. Можно считать, что если фирма не выиграла хотя бы 1 у.е. - она разоряется

podih в сообщении #1376616 писал(а):

Общее знание даёт единственный вариант: А и В подают проекты договоров друг другу, где каждый забирает свою сумму.
Что будет делать С, неважно.

На первый взгляд так и есть. Но ведь фирма C может предложить фирме A, к примеру, 80 у.е. А сколько фирма А получит, сотрудничая с B? Очевидно, $118-X$ единиц, где $X$ это число единиц, отданных B. Если $x>48$, то фирма C может предложить фирме A больше, чем $118-48=72$ единицы. А если $x<48$, то фирма C может предложить фирме B больше, чем 48 у.е., например 49 у.е.

[Null]

У меня вопрос как можно поделить 1 грант из 100 уе на 2 или 3 чтобы всех устроило, без дополнительных ограничений?
В вашей задаче недостаток информации: фирма А требует 71уе, фирма B 37уе и фирма С 3уе, если кто то потребует больше - остальные заключат парный контракт, столько отдадут без проблем - остальная сумма в точности равна парному контракту, как делить остальные 10уе? отдать в благотворительный фонд?

[lel0lel]

Если руководители соберутся за круглым столом, то справедливое решение найти можно. Примерно так: на основе суждений грантодателя составим систему уравнений $a+b=118, a+c=84, b+c=50$. Решив её, получим относительные рейтинги фирм $r_1=76/126, r_2=42/126, r_3=8/126$. Выигрыш $121$ поделим в соответствующих долях. В реальных условиях велика вероятность закулисья. Кто-то из руководителей (любой из трёх, самый ушлый) предлагает другому разделить выигрыш, приходящийся на их две фирмы, на более выгодных условиях чем те, что обсуждены за столом. Но если добавить условие, что решение руководителей должно быть подписано за столом, то будет реализована указанная выше схема.

[EUgeneUS]

С точки зрения теории игр:

К-ядро - все дележи, когда A получает не менее 71, B - не менее 37, С - не менее 3.
С-ядро - пустое. То есть пусто "множество эффективных распределений выигрыша, устойчивых к отклонениям любой коалиции игроков"

Можно делить по пред-N-ядру (оно существует и единственно).

С точки зрения C выгодно делить по вектору Шепли (получается: доля A, B, C соответственно 57.(3), 40.(3), 23.(3)), но такой дележ не входит в К-ядро и блокируется A.

[EUgeneUS]

UPD. пред-N-ядро, найденное по алгоритму, описанному тут, равно: $\left\lbrace74.(3), 40.(3), 6.(3)\right\rbrace$
То есть конторы получают "свои деньги", а оставшийся профит в 10 уе делят поровну.

[EUgeneUS]

UPD: вектор Шепли двумя постами выше, похоже, посчитан неверно. Но так как интерес к задаче пропал, в том числе и у ТС, пересчитывать не буду.

[Munuvonaza]

EUgeneUS в сообщении #1376863 писал(а):

Можно делить по пред-N-ядру (оно существует и единственно)

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

Единственное, что остается вопрос, как из потенциально бесконечного процесса с действием участников основанных на общем знании, получается закмнутое решение? В упрощенном понимании, имеется общее знание в виде информации о распределении гранта, и знание о знаниях других участников тендера, и так ad infinitum.

Каков алгоритм, или идея алгоритма в общих словах, которая позволяет прийти к верному решению, что необходимо осуществлять разделение по пред-N-ядру, и известно, что оставшиеся участники тендера примут такой же решение и процесс завершится за конечное число шагов, в частности, один шаг при подобном раскладе. Спасибо!

[EUgeneUS]

Munuvonaza
1. Эта тема (кооперативные игры) хотя и рассматривается в тех же курсах, что и общее знание (как это было у меня), к общему знанию отношения не имеет.
2.

Munuvonaza в сообщении #1378532 писал(а):

Каков алгоритм, или идея алгоритма в общих словах, которая позволяет прийти к верному решению, что необходимо осуществлять разделение по пред-N-ядру,

Идея очень проста:
а) пред-N-ядро всегда существует в таких играх и единственно.
б) Оно всегда принадлежит К-ядру, которое всегда существует, но может содержать много решений (дележей).
в) Если существует C-ядро ("устойчивые" дележи), что бывает не всегда, то пред-N-ядро принадлежит С-ядру.
То есть пред-N-ядро - это хороший, надежный способ найти одно из хороших решений (настолько хороших, насколько позволяет игра).

Munuvonaza в сообщении #1378532 писал(а):

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

А вот это никто никому не гарантирует. В данной задаче С-ядро пустое, а значит возможны "сепаратные" переговоры.

-- 26.02.2019, 20:08 --

(пример, как теория игр даёт сбой)

Пример - по памяти из курса по предмету, ссылки на первоисточники, конечно, не помню.

Проводили такую игру:
1. Участники разбиваются случайно на пары.
2. Также случайно в паре выбирается "первый" и "второй".
3. Паре предлагается поделить $100
4. Первый должен предложить дележ.
5. Второй может согласиться, тогда $100 делиться, как предложил первый. Или отказаться, тогда никто ничего не получает.

Из теории игр следует, что второй должен соглашаться на любой дележ, где ему предлагается больше нуля.
Соответственно, первый должен предлагать второму минимальную часть, на которые можно поделить $100 (доллар или цент).
Эксперимент показывает, что если первый предлагает второму меньше 30%, процент отказов приближается к 50%.
(Цифры по памяти, могу ошибаться).