Ключевые слова: многошаговая игра, би-кооперативные игры.
Добыча и распределение ограниченных ресурсов является затратным процессом, поэтому привлечение нескольких игроков облегчает решение данной проблемы с одной стороны. С другой стороны, если игроки решают кооперироваться для решения какой-либо задачи, естественно возникает вопрос о распределении ресурсов и затрат на их добычу. Одной из задач кооперативной теории игр является разрешение этой проблемы. Если в игре возможны побочные платежи внутри коалиций, то эту игру будем называть игрой с трансферабельными полезностями или ТП~игрой. Такой подход применяется при рассмотрении широкого класса проблем, таких как обеспечение водой, электричеством или задача распределение затрат на обслуживание среди группы пользователей.
В данной работе рассматривается би-кооперативная игра как инструмент решения задачи распределения затрат на проведение водопровода. Впервые данная задача была рассмотрена в статье «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.
Литература:
- 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.
