ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЕГАЗОВЫЙ УНИВЕРСИТЕТ»

ИНСТИТУТ КИБЕРНЕТИКИ, ИНФОРМАТИКИ И СВЯЗИ

ОТДЕЛЕНИЕ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Задание на курсовой проект

Студент __________________________________________________________

(Ф.И.О., группа)

Тема курсового проекта: Кооперативные игры

Перечень вопросов подлежащих исследованию и разработке:

1 Арбитражные схемы.

2 Классические кооперативные игры

3 Кооперативные игры с бесконечным числом игроков

Руководитель курсового проекта _____________________________

(подпись, дата)

Зав. отделением ИТВТ _____________________________

(подпись, дата)

Задание принял к исполнению _____________________________

(подпись, дата)

АРБИТРАЖНАЯ СХЕМА

АРБИТРАЖНАЯ СХЕМА - правило, по которому каждой игре с дележами ставится в соответствие единственный дележ этой игры, называется арбитражным решением. Первоначально А. с. были рассмотрены Дж. Нэшем для случая игры двух лиц. Пусть

u = {u(u₁, ..., u_n)} - множество дележей, d = (d₁, ..., d_n) - точка status quo, т. е. точка, соответствующая случаю, когда никакой дележ не осуществляется, [R, d] - игра с дележами, u - ее арбитражное решение. Дележ u* наз. решением Нэша, если

Решение Нэша и только оно удовлетворяет следующим аксиомам:

1) если f - линейное неубывающее преобразование, то fu¯ есть арбитражное решение игры [fR, fd] (инвариантность относительно преобразований полезности); 2) u¯ ≥ d, u¯ ∈ R и нет такого u ∈ R, чтобы u ≥ u¯ (оптимальность по Парето); 3) если R' ⊂ R, d' = d, u¯ ∈ R', то u¯ ' = u¯ (независимость несвязанных альтернатив); 4) если d_i = d_j, i, j = 1, ..., n и R симметрична, то u¯_i = u¯_j, i, j = 1, ..., n (симметрия).

Другую А. с. с характеристич. функцией v(S), S ⊂ N = (1, ..., n) для игр n лиц дал Л. С. Шепли [2]. Решение Шепли φ (v) = (φ₁ (v), ..., φ_n (v)), где

γ_n (s) = (s - 1)!(n - s)!/n!, s - число элементов множества S, также удовлетворяет аксиоме симметрии, кроме того, ∑_i φ_i (v) = v(N) и для любых двух игр u и v выполняется φ (u + v) = φ (u) + φ (v). Были также рассмотрены А. с. для случая сравнимых индивидуальных выигрышей (см. [3]).

Арбитражные схемы Дж. Нэша и Л. С. Шепли обобщил Дж. Харшаньи [4]. Решение Харшаньи, кроме соответствующих четырех аксиом Нэша, удовлетворяет еще двум аксиомам: 1) решение монотонно зависит от обоснованных требований игрока, 2) если u* и u** - решения, то решением будет и u¯,

если только u¯ принадлежит границе множества R.

А. с. непрерывно зависят от параметров игры, если в R имеются лучшие дележи, чем точка status quo.

Арбитраж

Итак, математик сделал своё дело и уходит в сторону, а игроки торгуются. Чем окончится торг - неизвестно. Хорошо, если они люди сговорчивые и покладистые. К сожалению, встречаются люди (и не только люди, а целые государства), которые, желая получит себе возможно больше, торгуются очень упорно, пуская в ход всё, даже угрозы. В результате переговоры оканчиваются ничем, угрозы приводятся в исполнение… Чем это кончается можно очень часто наблюдать в жизни.

Одним из выходов из этой ситуации является приглашение со стороны некоторого арбитра, который бы одинаково относился к обеим сторонам, и предложить ему указать совместную стратегию “по справедливости”. Если арбитр действительно “справедливый” и “беспристрастный”, он может вынести устраивающее обоих игроков решение. Но что означает “справедливый” и “беспристрастный”?

Достаточно очевидно, что к такому арбитру должны быть предъявлены следующие требования.

1. Арбитражное решение должно быть элементом переговорного множества.

2. Арбитражная схема должна быть независимой от имён или обозначений игроков.

3. Если две игры близки между собой в каком-то смысле, то и арбитражные решения должны быть близки.

4. Арбитражное решение должно отражать действенность угроз игроков.

В теории игр для решения подобных задач часто используют аксиоматический метод, когда подобные требования пытаются формализовать в виде математических аксиом. Ниже мы изложим систему таких аксиом, принадлежащую Дж. Нэшу. В дальнейшем считается, что игрок № 1 имеет

ходов, игрок номер 2 -

ходов, платёжная матрица имеет вид

. Через

мы будем обозначать выпуклую оболочку точек

- переговорное множество,

- точка status quo,

- решение арбитра.

Аксиома 1.(Оптимальность по Парето). Точка

должна быть элементом переговорного множества, то есть

;

4. в

нет точки

, отличной от точки

, такой, что

Аксиома 2.(Симметрия). Пусть игра обладает следующими свойствами:

;

2. если точка

то и точка

Тогда должно выполняться условие

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

Следующие две аксиомы далеко не столь очевидны, как предыдущие.

Аксиома 3.(Инвариантность относительно линейного преобразования). Пусть имеются две игры с одинаковым числом ходов для каждого игрока и с платёжными матрицами, связанными соотношениями

Тогда арбитражные решения для них также должны быть связаны соотношениями

Аксиома 4. (Независимость несвязанных альтернатив). Если к игре добавить новые ходы для игроков с добавлением новых элементов платёжных матриц таким образом, что точка status quo не меняется, то либо арбитражное решение также не меняется, либо оно совпадает с одной из добавленных сделок.

Дж. Нэш показал, что существует единственная арбитражная схема, удовлетворяющая этим четырём аксиомам. Арбитражное решение должно выносится из условия

то есть “справедливое” решение арбитра

должно удовлетворять условию

<для всех точек

принадлежащих переговорному множеству.

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

Муж и жена должны ходить вместе на футбол или в театр одинаково часто (например, по очереди).

Кооперативные игры

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

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

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

Кооперативные игры 2 (стр. 1 из 3)

АРБИТРАЖНАЯ СХЕМА