Построение многошаговой игры для би-кооперативной игры



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

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

В данной работе рассматривается би-кооперативная игра как инструмент решения задачи распределения затрат на проведение водопровода. Впервые данная задача была рассмотрена в статье «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.