Построение многошаговой игры для би-кооперативной игры | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 30 ноября, печатный экземпляр отправим 4 декабря.

Опубликовать статью в журнале

Библиографическое описание:

Построение многошаговой игры для би-кооперативной игры / В. В. Прокопова, Д. М. Золоторев, С. В. Наумов [и др.]. — Текст : непосредственный // Молодой ученый. — 2019. — № 18 (256). — С. 81-84. — URL: https://moluch.ru/archive/256/58759/ (дата обращения: 18.11.2024).



Ключевые слова: многошаговая игра, би-кооперативные игры.

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

В данной работе рассматривается би-кооперативная игра как инструмент решения задачи распределения затрат на проведение водопровода. Впервые данная задача была рассмотрена в статье «Bicooperative games» Bilbao J. M. [2] В работе «A value for bi-cooperative games» Labreuche C., Grabisch M. M. [3] представлено решение задачи распределения затрат на водопровод между тремя фермерами с помощью вектора Шепли. Вектор Шепли интересен тем, что распределяет выигрыш каждому игроку с учетом его среднего вклада в общую коалицию в зависимости от ее формирования. В данной же работе будет предложен новый подход к решению би-кооперативных игр.

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

Определение 1.1. [6] Пара (N, v) называется игрой с трансферабельными полезностями, если

N — конечное непустое множество;

v: R — функция, ставящая в соответствие каждой коалиции S ⊆ N ее выигрыш v(S), такая что v() = 0.

Пусть N = {1, …, n} — множество всех игроков. Любое непустое подмножество S ⊆ N называется коалицией.

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

Определение 1.2. [3] Определим Q(N) = {(S, T) | S, T ⊆ N, S ∩ T = ∅} — множество пар непересекающихся коалиций.

Определение 1.3. [3] Пару непересекающихся коалиций (S, T) будем называть парной коалицией.

Определение 1.4. [3] Би-кооперативной игрой будем называть пару (N, v), где N — множество игроков, а v — функция следующего вида: v: Q(N) → R, v(∅, ∅) = 0 где v(S, T) — выигрыш парной коалиции (S, T), где S — коалиция, состоящая из игроков, выбравших позитивный вариант участия, а T — коалиция игроков выбравших негативный вариант.

Определение 1.5. [4] Пара (X, F) называется графом, если X — некоторое конечное множество, а F — отображение X в X.

Каждый элемент множества X называется вершиной графа, а пара элементов (x, y), в которой y ∈ — дугой графа. Для дуги p=(x, y) вершины x и y называются граничными вершинами дуги. Множество дуг графа будем обозначать P. Путем в графе называется такая последовательность p = (, ,..., ,...) дуг, что конец каждой предыдущей дуги совпадает с началом следующей.

Ребром графа G = (X, P) называется множество из двух элементов x, y ∈ X для которых или (x, y) ∈ P или (y, x) P. Под цепью будем понимать последовательность ребер (, ,...) в которой у каждого ребра , одна из граничных вершин является также граничной для , а другая — граничной для . [4]

Цикл в графе — конечная цепь, начинающаяся в некоторой вершине и оканчивающаяся в той же вершине. Граф называется связным, если любые его две вершины можно соединить цепью. [4]

Определение 1.6. [4] Древовидный граф — конечный связный граф без циклов, имеющий не менее двух вершин, в котором существует единственная вершина , такая, что = X Вершина называется начальной вершиной графа G.

Перейдем к определению многошаговой игры с полной информацией на древовидном конечном графе.

Определение 1.7. [4] Пусть G= (X, F) — древовидный граф. Рассмотрим разбиение множества вершин X на n+1 множество $, …, , , , = ∅, k ≠ l, где = ∅ для x. Множество , i= 1, …, n, называется множеством очередности игрока i, а — множеством окончательных позиций. На множестве окончательных позиций определены n вещественных функций $(x), …, (x), x. Функция , i=1, …, n, называется выигрышем игрока i.

Определение 1.8. [5] Однозначное отображение , которое каждой вершине (позиции) x ставит в соответствие некоторую вершину (позицию) y, называется стратегией игрока i.

Множество всевозможных стратегий игрока i будем обозначать . Упорядоченный набор u = (, …, ), где , называется ситуацией в игре, а декартово произведение U = множеством ситуаций. [5]

Функция выигрыша игрока i равняется значению выигрыша в окончательной позиции партии соответствующей ситуации u = (), то есть

(, …, ) = (), i = 1, …, n. [5]

Определение 1.9. [5] Ситуация u* = (, …, ) называется ситуацией равновесия по Нэшу, если для всех , i = 1, …, n, имеет место неравенство

(u*) ≥ (u*||),

где (u*||) = (, …, ).

Определение 1.10. [5] Ситуация равновесия по Нэшу u* = (, …, ) называется ситуацией абсолютного равновесия по Нэшу в игре Г, если для любого z ∈ X ситуация =(, …, , где - сужение стратегии на подыгру , является ситуацией равновесия по Нэшу в подыгре .

Теорема 1. [5] В любой многошаговой игре с полной информацией на конечной древовидном графе существует ситуация абсолютного равновесия по Нэшу.

Рассмотрим пример игры трех игроков. Игрок 1 имеет в своем распоряжении участок железной дороги. Игроки 2 и 3 являются владельцами участков. Игрокам 2 и 3 для полноценного функционирования необходима вода, в то время как первому игроку вода не нужна, и перед ним стоит два выбора: либо он участвует в построении парной коалиции в негативном смысле, то есть разрешает провести водопровод с неудобствами для себя, либо он отказывается сотрудничать с другими игроками и им приходится искать другие, более затратные пути проведения водопровода. Стоимость проведения трубопровода сквозь железнодорожные пути до участка игрока 2 составляет величину b, стоимость проведения трубопровода от участка 2 до участка 3 составляет a, в случае, если трубопровод идет вокруг участка 2 и , если трубопровод идет сквозь участок 2. В случае отказа игрока 1 кооперироваться, трубопровод игроки 2 и 3 ведут из удаленного источника воды, в данном случае стоимость его проведения будет равняться c, c > b + a. Построим характеристическую функцию данной игры:

v(∅, ∅) = v(∅, {1}) = 0,

v({2}, {1}) = v(∅, {1, 2}) = b,

v({2}, ∅) = v(∅, {2}) = v({3}, ∅) = v({3, 2}, ∅) = v({3}, {2}) = c,

v({3}, {1}) = v({2, 3}, {1}) = b + a,

v({3}, {1, 2}) = b +

Так как трубопровод будет идти от источника воды до игроков 2 и 3, очередность игроков определим как их номера.

Первым свой ход совершает игрок 1. Он решает, разрешить ли проводить водопровод под землей. Вторым “ходит” игрок 2, зная решение игрока 1 он решает стоит ли ему разрешать провести трубопровод сквозь его участок, или нет. Игрок 3, в свою очередь не может отказаться от необходимого ему ресурса.

Посчитаем выигрыши игроков.

3.1 = (3a + 4b − 4c), = (2c + b), = (3a + b + 2c),

3.2 = (a + 2b − 2c), = (−a + b + 2c), = (2a + b + 2c),

3.3 = 0, = c, = c,

3.4 = 0, = c, = c.

Упростим систему, оставив только те вершины, которые выберет второй игрок.

Абсолютное равновесие по Нэшу в данной игре будет достигаться в 3.2 и стратегиями соответствующего равновесия по Нэшу будут являться: = 2, = (2, 1), = (1, 1, 1, 1) или = 2, = (2, 2), = (1, 1, 1, 1).

В случае, если игрок 1 решит не кооперироваться с другими игроками его выигрыш будет равен нулю. Однако если игрок 1 разрешит проведение труб, его собственные потери могут быть выше, чем величина = (a + 2b − 2c), которую ему заплатят игроки 2 и 3.

Литература:

  1. Fragnelli V. et al. How to share railways infrastructure costs? // Game practice: contributions from applied game theory. Springer, Boston, MA, 2000, С. 91–101.
  2. Bilbao J. M. et al. Bicooperative games //Cooperative games on combinatorial structures. Kluwer Acad., 2000, С. 131–295.
  3. Labreuche C., Grabisch M. M. A value for bi-cooperative games // Int J Game Theory, 2008, T. 37, No.3, C. 409–438.
  4. Петросян Л. А., Зенкевич Н. А., Шевкопляс Е. В. Теория игр: учебник СПб.: БХВ-Петербург, 2012. С. 159, 187–191.
  5. Петросян Л. А. Принципы оптимальности в многошаговых играх //Соросовский образовательный журнал, 1996, Т. 10, С. 120–125.
  6. Печерский С. Л., Яновская Е. Б. Кооперативные игры: решения и аксиомы. М.: Европейский университет в Санкт-Петербурге, 2004. с.32–47.
Основные термины (генерируются автоматически): игрок, игра, абсолютное равновесие, вершина, древовидный граф, коалиция, многошаговая игра, парная коалиция, ситуация равновесия, Би-кооперативная игра.


Ключевые слова

многошаговая игра, би-кооперативные игры

Похожие статьи

Теория вероятности в азартных играх

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

Эволюция клеточного автомата (игра «Жизнь») на диагональных решетках

В статье автор исследует эволюцию клеточного автомата игра «Жизнь» на диагональных координатных решетках.

Конспект сюжетно-ролевой игры в старшей группе «Поможем друзьям» с использованием строительного материала

В статье приводится пример проведения сюжетно-ролевой игры.

Создание игры в Scratch: «Собачка на прогулке»

Была создана весёлая и простая игра в среде программирования Scratch на зимнюю тему. В данную игру можно играть со своими друзьями.

Создание игры в слова на языке программирования Python (на примере игры «Виселица»)

В статье автор рассказывает о самостоятельном создании игры «Виселица» на языке программирования Python.

Влияние частоты сборки головоломок разного уровня сложности на количество затрачиваемого времени

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

Пороговые криптосистемы как один из вариантов модификации асимметричных криптосистем

Сравнение работы алгоритмов кластеризации

Моделирование комбинаторных систем при помощи сводимости

Статья посвящена моделированию систем, ее реализации в компьютере, в частности с использованием сводимости, в то же время рассматривается теория алгоритмов и возможность ее применения к моделированию.

Комбинаторная теория переобучения: оценка расслоения-связности

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

Похожие статьи

Теория вероятности в азартных играх

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

Эволюция клеточного автомата (игра «Жизнь») на диагональных решетках

В статье автор исследует эволюцию клеточного автомата игра «Жизнь» на диагональных координатных решетках.

Конспект сюжетно-ролевой игры в старшей группе «Поможем друзьям» с использованием строительного материала

В статье приводится пример проведения сюжетно-ролевой игры.

Создание игры в Scratch: «Собачка на прогулке»

Была создана весёлая и простая игра в среде программирования Scratch на зимнюю тему. В данную игру можно играть со своими друзьями.

Создание игры в слова на языке программирования Python (на примере игры «Виселица»)

В статье автор рассказывает о самостоятельном создании игры «Виселица» на языке программирования Python.

Влияние частоты сборки головоломок разного уровня сложности на количество затрачиваемого времени

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

Пороговые криптосистемы как один из вариантов модификации асимметричных криптосистем

Сравнение работы алгоритмов кластеризации

Моделирование комбинаторных систем при помощи сводимости

Статья посвящена моделированию систем, ее реализации в компьютере, в частности с использованием сводимости, в то же время рассматривается теория алгоритмов и возможность ее применения к моделированию.

Комбинаторная теория переобучения: оценка расслоения-связности

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

Задать вопрос