Некооперативная игра

Некооперативная игра — термин теории игр. Некооперативной игрой называется математическая модель взаимодействия нескольких сторон (игроков), в процессе которого они не могут формировать коалиции и координировать свои действия.

Некооперативная игра в нормальной форме

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

Некооперативная игра в нормальной форме предполагает следующий порядок разыгрывания.

1. Игроки одновременно и независимо друг от друга выбирают из множеств свои стратегии. Вектор стратегий всех игроков представляет собой ситуацию в игре.

2. Каждый игрок получает выигрыш, определяемый значением функции , на этом взаимодействие между ними прекращается.

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

Некооперативная игра в развернутой форме

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

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

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

Начальная и промежуточные позиции образуют множество нетерминальных позиций.

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

Для учета несовершенства информации, имеющейся у игроков, нетерминальные вершины могут объединяться в информационные множества.

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

Игра предполагает следующий порядок разыгрывания:

1. Игра начинается из начальной позиции.

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

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

Принципы оптимальности

Основным принципом оптимальности стратегий для некооперативных игр в нормальной форме является равновесие Нэша, основанное на невозможности отклонений участников от выбранных стратегий. К настоящему времени разработано семейство принципов, основанных на равновесии Нэша, и называемых очищениями равновесия Нэша (Nash equilibrium refinements), наиболее часто используемыми среди которых являются:

• равновесие дрожащей руки;
• собственное равновесие;
• сильное равновесие.

Менее универсальными, используемыми в отдельных классах некооперативных игр, являются следующие принципы:

• ε-равновесие;
• равновесие в доминирующих стратегиях;
• решение игры по доминированию;
• равновесие в осторожных стратегиях.

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

• равновесие, совершенное по под-играм;
• секвенциальное равновесие;
• сильное секвенциальное равновесие.

Примеры

Дилемма заключённого

Трагедия общин

Трагедия общин

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

Термин появился из притчи Вильяма Форстера Лойда в его книге 1833 года о населении. Затем термин популяризировал Гаррет Хардин в 1968 году в статье для журнала Science, так и названной — «Трагедия общин».

Введение

Трагедия общин показывает, как свободный доступ к ресурсу, например, пастбищу, полностью уничтожает ресурс из-за чрезмерного его использования. Это происходит потому, что все, пользующиеся им, получают выгоды (или доход) непосредственно себе, а издержки содержания ресурса ложатся на них всех равномерно.

Примеры.

Пастбище

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

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

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

Прокси-сервер

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

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

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

Поиск по сайту: