Что означает игра с нулевой суммой

Игра с нулевой суммой — что это значит

Здравствуйте, уважаемые читатели проекта Тюлягин! В сегодняшней статье мы поговорим про игру с нулевой суммой. В ней вы узнаете что такое и что означает игра с нулевой суммой, в ней также приведены несколько примеров игр с нулевой суммой и напротив с ненулевой суммой, в том числе на примере финансовых и фондовых рынков. Об этом и не только далее в статье про игры с нулевой суммой.

Содержание статьи:

Что такое игра с нулевой суммой?

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

Суть игры с нулевой суммой

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

Согласно теории игр, «игру Пенни» часто называют примером игры с нулевой суммой. В игре участвуют два игрока, A и B, одновременно кладут пенни (монету) на стол. Развязка зависит от того, совпадают ли пенни или нет. Если оба пенни орел или решка, игрок A выигрывает и сохраняет пенни игрока B, если они не совпадают, то игрок Б выигрывает и сохраняет пенни игрока А.

Игра Пенни — это игра с нулевой суммой, потому что выигрыш одного игрока — это проигрыш другого. Результаты для игроков A и B показаны в таблице ниже: первая цифра в ячейках (а) — (г) представляет результат игрока A, а вторая цифра — результат игрока B. Как видно, объединенный результат игры для A и B во всех четырех ситуациях равен нулю.

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

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

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

Теория игр — это комплексное теоретическое исследование в области экономики. Основополагающим текстом является новаторская работа 1944 года «Теория игр и экономического поведения», написанная американским математиком венгерского происхождения Джоном фон Нейманом и написанная в соавторстве с Оскаром Моргенштерном. Теория игр — это исследование процесса принятия решений двумя или более разумными и рациональными сторонами.

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

Теоретически игра с нулевой суммой решается с помощью трех решений, возможно, наиболее заметным из которых является равновесие по Нэшу, предложенное Джоном Нэшем в статье 1951 года под названием «Некооперативные игры». Равновесие Нэша гласит, что два или более соперника в игре — при условии, что они знают о выборе друг друга и что они не получат никакой выгоды от изменения своего выбора, — не отклонятся от своей стратегии.

Примеры игр с нулевой суммой

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

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

Торговля опционами и фьючерсами является наиболее близким практическим примером сценария игры с нулевой суммой, потому что контракты представляют собой соглашения между двумя сторонами, и, если один человек проигрывает, то другая сторона выигрывает. Хотя это очень упрощенное объяснение опционов и фьючерсов, как правило, если цена этого товара или базового актива повышается (обычно против ожиданий рынка) в течение установленного периода времени, инвестор может закрыть фьючерсный контракт с прибылью. Таким образом, если инвестор заработает на этой ставке, возникнут соответствующие убытки, а чистым результатом станет передача богатства от одного инвестора к другому.

Резюме

А на этом сегодня все про игры с нулевой суммой. Надеюсь статья оказалась для вас полезной. Делитесь статьей в социальных сетях и мессенджерах и добавляйте сайт в закладки. Успехов и до новых встреч на страницах проекта Тюлягин!

Источник

ИГРА С НУЛЕВОЙ СУММОЙ

Полезное

Смотреть что такое «ИГРА С НУЛЕВОЙ СУММОЙ» в других словарях:

ИГРА С НУЛЕВОЙ СУММОЙ — (zero sum game) Игра, в которой участники ограничиваются распределением между собой фиксированной общей суммы затрат или доходов. Рыночные доли (market shares), например, равные 100%, означают, по определению, что выигрыш одной фирмы является… … Экономический словарь

ИГРА С НУЛЕВОЙ СУММОЙ — (zero sum game) Игра или пари двух и более человек, при которой выигрыш одного равен проигрышу другого, то есть доходы минус убытки дают нуль. Примером игры с нулевой суммой является вопрос, кто платит за такси: доход одного человека для другого… … Словарь бизнес-терминов

Игра с нулевой суммой — Термин из книги «Теория игр и экономическое поведение» (1944), написанной двумя авторами Джоном фон Нейманом (1903 1957) и Оскаром Моргенштерном (1902 1977). Так авторы книги назвали любую «игру» (включая экономическое и военное соперничество), в … Словарь крылатых слов и выражений

Игра с нулевой суммой — Запрос «Zero sum» перенаправляется сюда. Cм. также другие значения. Антагонистическая игра (игра с нулевой суммой, англ. zero sum) термин теории игр. Антагонистической игрой называется некооперативная игра, в которой участвуют два игрока,… … Википедия

игра с нулевой суммой — Ситуация, при которой выигрыш победителя уравновешивается убытком проигравшего. Например, в области фьючерсной и опционной торговли действует игра с нулевой суммой, потому что на каждого инвестора с выигрышным контрактом приходится… … Финансово-инвестиционный толковый словарь

ИГРА С НУЛЕВОЙ СУММОЙ — Любая игра, ожидаемый выигрыш от кото Рои для всех участников в сумме составляет ноль, то есть игра, где в конечном счете один ожидает проиграть (приблизительно) столько же, сколько другой выиграет. Обратите внимание, что игры и связанные с ними… … Толковый словарь по психологии

Игра с нулевой суммой — любая игра, ожидаемый выигрыш от которой для всех участников в сумме составляет ноль. Существует немало игр с соответственно положительной и отрицательной суммой. Патологические игроки даже в играх с отрицательной суммой, где вероятность выигрыша … Энциклопедический словарь по психологии и педагогике

ИГРА С НУЛЕВОЙ СУММОЙ — (zero sum game) игра или аналогичная социальная ситуация, в которой потерянное одной стороной находится другой (фон Нойманн и Моргенштайн, 1947). См. также Теория игр; Дилемма заключенных … Большой толковый социологический словарь

Игра с нулевой суммой — математическая игра, в которой платежи сорганизованы таким образом, что один игрок выигрывает столько же, сколько другой проигрывает … Социологический словарь Socium

Игра с нулевой суммой — Вид игры, в которой один игрок может выиграть только за счет другого игрока … Инвестиционный словарь

Источник

Игра с отрицательной суммой

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

Предисловие: теория игр

В прикладной математике есть раздел, который называется «теория игр». Методы теории игр используются в экономике, социологии, политологии, психологии, этике и других общественных науках для того, чтобы систематизировать, проанализировать, понять и объяснить бесконечное многообразие механизмов взаимодействия людей в различных ситуациях.

Ключевое понятие теории игр это, разумеется, «игра». Игры делятся на множество типов: кооперативные и некооперативные, симметричные и несимметричные, параллельные и последовательные, с полной или неполной информацией, дискретные и непрерывные игры, а также игры с нулевой суммой и с ненулевой суммой. Нам сейчас важны последние два типа игр.

Игра с нулевой суммой

Игры с нулевой суммой или «антагонистические игры» — самый примитивный из классов игр. В таких играх если один игрок выиграл, то другой обязательно проиграл, двух победителей быть не может. Если у одного плюс, то у другого минус, в сумме — ноль. Отсюда и название — «игры с нулевой суммой».

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

«Всё, что есть у одного, украдено у другого», «Либо мы их, либо они нас», «Было ваше — стало наше», «Кто не с нами, тот против нас», «Своя рубашка ближе к телу», «Нет постоянных союзников, есть лишь постоянные интересы» — это всё про игры с нулевой суммой.

Россия с 1991 года — это одно грандиозное поле для такой игры. Сначала бывшие партийные боссы и просто ловкие проходимцы делили между собой наследие СССР — заводы, фабрики, нефтяные скважины. Приватизировали их, покупали за копейки, отжимали друг у друга.

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

Затем к власти пришли «siloviki» и переделили всё по-своему. Кто-то из олигархов вовремя сориентировался и встроился в новую систему, кому-то пришлось уехать в Лондон, кто-то попал в тюрьму, а кто-то — на тот свет.

Ещё через какое-то время шальные нефтяные деньги ударили новой элите в голову, и от пьянящего ощущения своей невероятной успешности Кремль решил, что настолько умён и удачлив, что теперь должен сыграть в новую игру по тем же правилам, но с более высокими ставками — в «геополитику».

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

К тому же, проигранная всухую «Холодная война» с Западом толкала оказавшихся у власти выходцев из спецслужб к реваншу, а мир казался им предельно простым и понятным: вот страны в нашей сфере влияния, вот страны под контролем «вероятного противника», а всем остальным в ходе очередной большой игры придётся определиться, на чьей они стороне.

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

А потом Россия влезла на территорию находящейся в состоянии междувластия Украины и аннексировала Крым. Присоединила. Отжала. Отхватила. Урвала. В терминах игры с нулевой суммой — чистая победа.

Сложный мир

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

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

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

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

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

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

Игры с ненулевой суммой

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

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

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

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

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

Это не значит, что они стали безобидными, белыми и пушистыми. Скоре наоборот — более мощной военной силы, чем блок НАТО в его нынешнем виде, не существовало на Земле никогда.

Тем не менее, цель применения военной силы может быть разной: гордо поставить красный флажок посреди разграбленной, выжженной и обезлюдевшей пустыни или добиться с побеждённым прочного и взаимовыгодного мира. Эту разницу очень легко почувствовать, если сравнить судьбу побеждённых Германии, Италии и Японии со странами Варшавского договора после Второй Мировой войны.

В арабских странах это не сработало: Афганистан, Ирак и Ливию после военного вмешательства Запада сложно назвать благополучными странами. Вероятнее всего, дело тут в исламе, но в любом случае Запад стремится не отжимать и захватывать территории, а создавать политические режимы, с которыми можно вести диалог и сотрудничать.

Две игры

И вот тут мы подходим к главному: конфликт России с Западом — это, прежде всего, конфликт двух картин мира. Запад пытается играть в игру с ненулевой суммой, стремясь к выгоде через сотрудничество, а Россия — в игру с нулевой суммой, пытаясь получить выгоды через конфронтацию.

Это как если бы на одной и той же шахматной доске один из игроков играл в шахматы, а второй — в шашки. Запад создаёт, преумножает и объединяет, в то время как Россия отнимает, уничтожает и разобщает.

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

С точки зрения России, действия Запада — подлое лицемерие, попытка усыпить бдительность, окружить со всех сторон ракетами и военными базами, а затем — напасть, уничтожить Россию и отнять её несметные природные богатства. Расширение ЕС и НАТО — явные этому подтверждения. Ну не могут же нормальные страны сами захотеть попасть под каблук Империи! Значит, их подкупили, обманули, заставили — чуть раньше, чем это успели сделать мы. То есть увели их у нас из-под носа, обманули нас.

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

Запад говорит: ОК, ребята, мы лишим вас самого ценного, что у нас есть, — сотрудничества. Мы не будем давать вам кредиты, не будем делиться технологиями, не хотим работать с вашими компаниями, нам не нужны ваши капиталы.

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

Россия не понимает, почему должна бояться санкций, ведь пока у неё есть ракеты, она может продолжать играть в «геополитику», а население пускай жрет лебеду, собирает валежник и лечится корой дуба — это проблема исключительно самого населения.

Запад же никак не может взять в толк, как это Россия собирается бомбить его города, в которых живут семьи российской элиты — от депутатов до чиновников, в которых у них куплена недвижимость и открыты банковские счета.

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

Но, может быть, мы всё-таки играем в более правильные игры, чем Запад, и победа будет за нами?

Игра с отрицательной суммой

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

Принятое Кремлём решение об аннексии Крыма аукнулось нам санкциями со стороны Западных стран. В результате мы получили более дорогие кредиты и более низкий курс рубля, то есть подорожавшие импортные товары. Мы уже давно едим сыр из пальмового масла и невкусные овощи, а скоро нам придётся лечиться суррогатными лекарствами и настойкой боярышника. То есть на самом деле мы имеем дело не с нулевой суммой игры, а с отрицательной.

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

Власть всё время кивает в сторону «лихих девяностых», противопоставляя их ужас сегодняшней прекрасной «стабильности», но на самом деле девяностые никуда не делись. Эта тяга к примитивным, силовым, сиюминутным решениям — прямиком оттуда.

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

Итоги игры

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

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

Неприятная необходимость тратить огромные деньги на имитацию демократических институтов — парламента, Совета Федерации и судов, а также прикрывать воровство никому не нужными «нацпроектами» возникла не на пустом месте.

Феодал поддерживал свою власть над населением силой, Кремль — обманом. И большая часть того, что когда-то было системой государственного управления, сейчас представляет собой лишь грандиозную мистификацию, ширму, прикрываясь которой элита выносит из закромов Родины последние ценные вещи.

Феодализм практически повсеместно проиграл конкуренцию тогда ещё молодым и несовершенным демократиям. Сейчас наша элита построила экономически ещё менее эффективную модель и вошла в конфронтацию не только с собственным населением, но и с демократическими странами, в сумме обладающими 47% мирового ВВП против наших 1,5%.

Итог этого противостояния предсказать не сложно: пользуясь подавляющим превосходством в области экономики, страны Запада постепенно и аккуратно, чтобы по возможности не причинить вред самим себе, изолируют нас от современных технологий, рынков сбыта и финансовых потоков.

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

И когда эта власть рухнет и мы снова, как это уже бывало, попросим у Запада гуманитарную помощь, они не повторят ошибку 90-х и потребуют взамен как минимум полное разоружение, после которого Россию долго и болезненно будут вновь интегрировать в мировое сообщество.

Если, разумеется, к тому моменту ещё будет, кого интегрировать.

P.S. Друзья, не забудьте, пожалуйста, подписаться на мой YouTube-канал, если вы разделяете мои мысли и идеи. Мне будет очень приятно. Ну и про Телеграм не забывайте!

Если вы заметили ошибку, выделите её и нажмите Ctrl+Enter

Источник

Игры с нулевой суммой и условия Каруша-Куна-Таккера

В этой статье я подробностях разбираюсь с задачей поиска равновесных смешанных стратегий на примере антагонистических игр.

Пусть есть два игрока, A и B, которые многократно разыгрывают некоторую игру. Каждый игрок в каждом розыгрыше придерживается одной из нескольких стратегий — для простоты будем считать, что количество стратегий для обоих игроков совпадает и равняется . При выборе -й стратегии первым игроком и -й стратегии вторым игроком первый игрок получит выигрыш , а второй игрок получит такой же проигрыш — так уж устроены антагонистичные игры. Эти выигрыши можно записать в виде квадратной матрицы :

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

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

Вот поиском таких равновесий мы сейчас и займёмся.

1. Равновесия

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

Например, рассмотрим такую матрицу выигрышей:

В этом случае ни одна из пар чистых стратегий не является равновесием. Пусть, скажем, первый игрок выбирает первую стратегию. Тогда второй игрок хочет захочет также всегда выбирать первую стратегию: это приведёт к меньшему проигрышу (2 против 3). Но, если второй игрок выбирает первую стратегию, первый игрок предпочтёт ответить стратегией номер два: так его выигрыш будет больше (4 против 1). Однако, если первый игрок выбирает вторую стратегию, второй игрок также ответит второй: его проигрыш таким образом уменьшится (1 против 4). Но при выборе вторым игроком второй стратегии первый игрок выберет первую стратегию, и так далее. Итого, при любом выборе чистых стратегий хотя бы один из игроков может изменить свой выбор так, чтобы увеличить собственную выгоду.

Однако в пространстве смешанных стратегий равновесие найдётся. Нетрудно проверить, что равновесием в данном случае будет пара смешанных стратегий , . В таком случае математическое ожидание выигрыша для первого игрока будет равно 2.5.

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

Если смешанные стратегии и образуют равновесие, они оказываются решениями оптимизационных задач:

При этом на сами стратегии распространяются очевидные ограничения:

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

Рассмотрим, например, следующую матрицу выигрышей:

Не вдаваясь в технические детали, скажу, что применение метода множителей Лагранжа с учётом только лишь ограничений в виде равенств

в данном случае приведёт к решению

Это происходит из-за того, что метод множителей Лагранжа не может учесть ограничения в виде неравенств. Тут-то нам и помогут условия Каруша-Куна-Таккера.

2. Условия Каруша-Куна-Таккера

Также эти условия известны как условия Куна-Таккера, а всё потому, что впервые опубликованы они были в работе 1951-го года за авторством Куна и Таккера, и лишь впоследствии обнаружилось, что Каруш уже в 1939-м году сформулировал их в неопубликованной работе.

На время отвлечёмся от теории игр и сформулируем более общую задачу оптимизации следующим образом: необходимо найти минимум некоторой функции

при условии ограничений как в виде равенств, так и в виде неравенств:

Доказывается, что тогда каждая точка, являющаяся решением оптимизационной задачи, удовлетворяет условиям Каруша-Куна-Таккера:

Здесь первое условие очень похоже на соответствующие условие в методе множителей Лагранжа; последние два условия фактически дублируют ограничения исходной оптимизационной задачи.

Второе и третье условия — хитрые. Вместе с условием четыре они означают следующее:

Теперь возникает вопрос о том, а как, собственно, решать такую систему уравнений. Как правило, можно поступать следующим образом:

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

3. Условия ККТ для антагонистических игр

Выше я записал условия ККТ для задачи минимизации. Поэтому нужно сформулировать все условия в терминах задачи минимизации, плюс нужно соблюсти формальность и переписать условия в виде неравенств так, чтобы они были записаны в виде «меньше либо равно нулю».

Условия для :

Условия для :

Теперь выпишем лагранжианы:

Теперь запишем оставшиеся условия Каруша-Куна-Таккера, местами преобразовав в более удобный вид. Для :

Для :

Приравнивая производные лагранжианов нулю, получим следующую систему уравнений:

Здесь переменных и уравнений. Используем теперь условия:

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

Из всех решений нужно будет выбрать только те, которые удовлетворяют оставшимся ограничениям Каруша-Куна-Таккера:

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

Рассмотрим теперь подробнее уравнения, которые получаются после означения некоторых неизвестных нулями. Для примера рассмотрим следующее уравнение для некоторого :

Мы знаем, что может равняться нулю, в таком случае уравнение принимает вид

Если же в соответствии с выбором не равняется нулю, эта неизвестная просто выражается через значения вектора и значение :

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

А ограничения становятся тривиальными:

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

5. В поисках равновесия

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

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

6. Реализация

Весь код реализации я сложил к себе на GitHub: https://github.com/ashagraev/zero_sum_game

В matrix.h лежит простой утилитарный код: прочитать матрицу, транспонировать матрицу, решить СЛАУ. Для решения СЛАУ я использую простейший метод Гаусса с выбором ведущего элемента и тривиальной проверкой на вырожденность. Эту можно было бы реализовать и получше, но суть не в ней.

Реализация описанного алгоритма для решения набора СЛАУ находится в файле kkt.cpp. Для генерации подмножеств используются коды Грея. Чтобы подружить рекурсивный метод генерации кодов Грея с последовательной их обработкой, пришлось немного покуражиться с callback’ами.

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

Источник