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