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

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

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

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

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



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

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

В данной работе рассматривается би-кооперативная игра как инструмент решения задачи распределения затрат на проведение водопровода. Впервые данная задача была рассмотрена в статье «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.
Основные термины (генерируются автоматически): игрок, игра, абсолютное равновесие, вершина, древовидный граф, коалиция, многошаговая игра, парная коалиция, ситуация равновесия, Би-кооперативная игра.


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

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

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

Теория игр: основные понятия, типы игр, примеры

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

Например, игроки имеют право объединяться в коалиции, но сама игра будет вестись в бескоалиционном стиле.

Аппарат теории кооперативных игр в моделировании...

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

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

Аналогично, с помощью аппарата теории кооперативных игр можно вычислить априорное...

Математическое моделирование банкротства предприятия

Такие игры моделируют ситуации, при которых участники игры, объединяясь, могут

При решении игры банкротства можно использовать различные принципы оптимальности такие

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

Прокопова Виктория Викторовна — Информация об авторе

Построение многошаговой игры для би-кооперативной игры. №18 (256) май 2019 г. Авторы: Прокопова Виктория Викторовна, Золоторев Дмитрий Михайлович, Наумов Сергей Валерьевич, Инишева Дарья Олеговна, Тельбухов Андрей Борисович. Рубрика: Математика. Страницы

Актуальность применения теории игр в процессе конкурсного...

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

Золоторев Дмитрий Михайлович — Информация об авторе

Построение многошаговой игры для би-кооперативной игры. №18 (256) май 2019 г. Авторы: Прокопова Виктория Викторовна, Золоторев Дмитрий Михайлович, Наумов Сергей Валерьевич, Инишева Дарья Олеговна, Тельбухов Андрей Борисович. Рубрика: Математика. Страницы

Инишева Дарья Олеговна — Информация об авторе

Построение многошаговой игры для би-кооперативной игры. №18 (256) май 2019 г. Авторы: Прокопова Виктория Викторовна, Золоторев Дмитрий Михайлович, Наумов Сергей Валерьевич, Инишева Дарья Олеговна, Тельбухов Андрей Борисович. Рубрика: Математика. Страницы

Экономический анализ риска и неопределённости в теории игр

Главная структура игры включает игроков, придерживающихся различных действий и

Залогом успеха в теории игр служит умение участника думать не только о своих целях, но и о

Теория игр приносит в эту ситуацию новый элемент: мы должны увидеть цели и действия...

Логические блоки Дьенеша — всесторонняя развивающая игра

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

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

Теория игр: основные понятия, типы игр, примеры

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

Например, игроки имеют право объединяться в коалиции, но сама игра будет вестись в бескоалиционном стиле.

Аппарат теории кооперативных игр в моделировании...

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

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

Аналогично, с помощью аппарата теории кооперативных игр можно вычислить априорное...

Математическое моделирование банкротства предприятия

Такие игры моделируют ситуации, при которых участники игры, объединяясь, могут

При решении игры банкротства можно использовать различные принципы оптимальности такие

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

Прокопова Виктория Викторовна — Информация об авторе

Построение многошаговой игры для би-кооперативной игры. №18 (256) май 2019 г. Авторы: Прокопова Виктория Викторовна, Золоторев Дмитрий Михайлович, Наумов Сергей Валерьевич, Инишева Дарья Олеговна, Тельбухов Андрей Борисович. Рубрика: Математика. Страницы

Актуальность применения теории игр в процессе конкурсного...

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

Золоторев Дмитрий Михайлович — Информация об авторе

Построение многошаговой игры для би-кооперативной игры. №18 (256) май 2019 г. Авторы: Прокопова Виктория Викторовна, Золоторев Дмитрий Михайлович, Наумов Сергей Валерьевич, Инишева Дарья Олеговна, Тельбухов Андрей Борисович. Рубрика: Математика. Страницы

Инишева Дарья Олеговна — Информация об авторе

Построение многошаговой игры для би-кооперативной игры. №18 (256) май 2019 г. Авторы: Прокопова Виктория Викторовна, Золоторев Дмитрий Михайлович, Наумов Сергей Валерьевич, Инишева Дарья Олеговна, Тельбухов Андрей Борисович. Рубрика: Математика. Страницы

Экономический анализ риска и неопределённости в теории игр

Главная структура игры включает игроков, придерживающихся различных действий и

Залогом успеха в теории игр служит умение участника думать не только о своих целях, но и о

Теория игр приносит в эту ситуацию новый элемент: мы должны увидеть цели и действия...

Логические блоки Дьенеша — всесторонняя развивающая игра

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

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