«26 сентября 2008 г. Содержание Предисловие 1 1 Вводная лекция 6 Тест для самоконтроля к лекции 1................. 14 I Принятие решений в условиях определённости 16 2 Экстремум функций одной переменной ...»

Рассмотрим теперь некоторые конкретизации понятия –устойчивости для случая игры вида (15.1).

1) Пусть состоит из всех одноэлементных коалиций. Тогда – устойчивость ситуации 0 в игре означает, что для каждого ни в одной ситуации 0, где, не имеет места (0 ) > (0 ), то есть выполняется (0 ) (0 ). Это условие есть, в точности, равновесие по Нэшу для игры (см.п.2).

2) Пусть состоит из единственной коалиции всех игроков. Тогда условие –устойчивости ситуации 0 сводится к тому, что не существует такой ситуации 1, для которой при всех выполняется (1 ) (0 ), причем хотя бы одно неравенство является строгим. Указанное условие есть условие Парето–оптимальности (см.лекцию 5) ситуации в множестве всех ситуаций игры (в качестве оценочной функции критерия = 1,..., здесь выступает функция выигрыша игрока ).

3) Пусть состоит из всех коалиций игры. Тогда условие – устойчивости ситуации 0 соcтоит в том, что для любой коалиции имеет место (0 ) (0 ), причем хотя бы для одного индекса неравенство должно быть строгим. Таким образом, сильная устойчивость ситуации 0 в игре означает отсутствие такой коалиции, которая могла бы преобразовать ситуацию 0 в какую–либо другую при единогласной заинтересованности в этом всех своих членов.

5. Задача № 20: Задача распределения ресурсов.

Предположим, что имеется предприятий, каждое из которых потребляет видов ресурсов. Вектор с неотрицательными компонентами = (1,..., ) рассматривается как вектор ресурсов, потребляемых – м предприятием ( = 1,..., ). Предполагается далее, что для каждого = 1,..., задана функция ( ), которая оценивает эффективность –го предприятия при условии, что оно потребляет ресурсный вектор (например, в качестве можно рассматривать производственную функцию, см. задачу № 2).

Имеется два варианта задачи распределения ресурсов, соответствующих централизованному и децентрализованному распределению. Рассмотрим оба эти варианта.

Вариант 1 (задача централизованного распределения ресурсов). Здесь предполагается, что управляющий орган (центр) обладает некоторым запасом ресурсов, который задается вектором = (1,..., ), где — запас ресурса типа. Пусть — множество всех наборов ресурсных покомпонентное). Вектор интепретируется как ресурсный вектор, выделенный центром –му предприятию. Каждому набору (1,..., ) соответствует вектор эффективностей (1 (1 ),..., ( )). В результате получаем задачу многокритериальной оптимизации (лекция 5), в которой — множество альтернатив, — оценочная функция по критерию = 1,...,. Оптимальное решение такой задачи ищется в множестве ее Парето–оптимальных альтернатив. При некоторых ограничениях на область допустимых альтернатив задача нахождения Паретооптимальных альтернатив может быть сведена к задаче нахождения максимума обобщенного критерия =, где 0 (см. лекцию 5).

Рассмотрим теперь более подробно вариант децентрализованного распределения ресурсов.

Вариант 2 (задача перераспределения ресурсов). В этом случае предполагается, что каждое предприятие = 1,..., обладает начальным запасом ресурсов, задаваемым вектором = (^1,..., ). Предприятие может продавать принадлежащие ему ресурсы, а также покупать любые ресурсы по установленным ценам при единственном ограничении: общая стоимость покупаемых ресурсов не должна превышать общей стоимости начального запаса ресурсов этого предприятия. Пусть = (1,..., ) — вектор цен, где — стоимость единицы ресурса –го типа ( = 1,..., ).

Если предприятие покупает ресурсный вектор = (1,..., ), то общая стоимость покупки есть 1 1 + · · · + ; она представляется в виде скалярного произведения (, ). Аналогично, стоимость начального запаса ресурсов предприятия равна (, ), откуда указанное выше ограничение принимает вид Условие (15.10) называется условием платежеспособности спроса при векторе цен.

Определение. Набор (*,..., *, * ), где * — ресурсный вектор предприятия = 1,...,, а * — вектор цен, называется состоянием экономического равновесия, если выполняются следующие два условия.

1) При каждом = 1,..., ресурсный вектор * максимизирует функцию эффективности предприятия по множеству всех ресурсных векторов этого предприятия, находящихся в пределах его платежеспособного спроса по ценам * :

2) Общий объем потребляемых ресурсов каждого типа не превосходит его первоначального запаса:

где * = *, = (неравенство (15.12) понимается как покомпонентное).

Рассмотрим теперь игру +1 игроков 1,...,, + 1, в которой первыми игроками являются предприятия, а в качестве ( + 1)–го игрока выступает ценообразующий орган. В этой игре стратегиями каждого предприятия являются его ресурсные вектора, а стратегиями ценообразующего органа — вектора цен. Ситуациями игры +1 считаются такие наборы (1,...,, ), в которых каждый вектор является ресурсным вектором предприятия, удовлетворяющим условию платежеспособности спроса при векторе цен. Цель игрока состоит в максимизации функции эффективности ( = 1, ), а цель игрока ( + 1) — в минимизации взвешенного дисбаланса, то есть в минимизации функции Покажем, что экономическое равновесие можно представить как равновесие по Нэшу в игре +1. Действительно, пусть (1,...,, ) — ситуация равновесия по Нэшу в игре +1. Тогда при каждом = 1,..., для всех ресурсных векторов, удовлетворяющих условию (, ) (, ), выполняется неравенство а для игрока + 1 при произвольном векторе цен имеет место Убедимся, что набор (1,...,, ) является состоянием экономического равновесия. Неравенства (15.13) означают, что при каждом = 1,..., ресурсный вектор максимизирует функцию эффективности предприятия по множеству всех ресурсных векторов, находящихся в пределах его платежеспособного спроса по ценам. Таким образом, условие 1) выполнено. Проверим условие 2). Так как набор (1,...,, ) является ситуацией в игре +1, то при всех = 1,..., выполнено условие платежеспособности: (, ) (, ). Суммируя эти неравенства по = 1, и используя линейность скалярного произведения, получаем 0, то есть (, ) 0. Учитывая (15.14), имеем (, ) 0. Ввиду произвольности вектора цен отсюда следует, что, и условие 2) проверено. Итак, всякая ситуация равновесия по Нэшу игры +1 является экономическим равновесием.

Обратно, пусть (*,..., *, * ) — состояние экономического равновесия. Ввиду (15.11) получаем, что в состоянии экономического равновесия отклонение игрока = 1,..., от стратегии * приводит к уменьшению его выигрыша. Остается установить уменьшение, точнее, неувеличение выигрыша игрока + 1 при его одностороннем отклонении от стратегии *. Будем предполагать, что функции эффективности ( = 1, ) являются строго монотонно возрастающими (то есть из >Par следует ( ) > ( )). Тогда в состоянии экономического равновесия не может В этом случае по каждому виду ресурсов дисбаланс равен нулю, поэтому и взвешенный дисбаланс также будет равен нулю при любом выборе вектора цен. Отсюда следует, что в ситуации (*,..., *, * ) замена вектора цен * на другой вектор цен не изменит (а, значит, и не уменьшит) взвешенный дисбаланс.

Итак, в предположении строгой монотонности функций эффективности ( = 1, ) справедлив следующий результат. Множество состояний экономического равновесия совпадает с множеством ситуаций равновесия по Нэшу в игре с добавленным участником, минимизирующим взвешенный дисбаланс.

Тест для самоконтроля к лекции 1. В игре лиц в нормальной форме Г=<, ( ), ( ) >.

Функция выигрыша есть выражение....

2. Биматричная игра, задаваемая парой матриц = ( ), = ( ), где = 1,..., ; = 1,...,, эквивалентна матричной, если для всех = 1,..., ; = 1,..., выполняется....

3. В игре лиц Г=<, ( ), ( ) > ситуация 0 = (0,..., 0 ), для которой при всех, выполняется неравенство называется....

Варианты ответов: Оптимальной ситуацией;

4. Если в игре лиц Г=<, ( ), ( ) > ситуация 0 не является ситуацией равновесия, то найдется игрок и стратегия, для которых....

5. В биматричной игре с матрицами выигрышей игроков = ( ) и = ( ), где = 1,..., ; = 1,..., ситуация (0, 0 ) будет ситуацией равновесия тогда и только тогда, когда....

6. Верно ли, что в биматричной игре, которая эквивалентна матричной, понятие ситуации равновесия равносильно понятию седловой точки?

Варианты ответов: Да, всегда;

7. В биматричной игре игр. ситуациями равновесия являются:....

Варианты ответа: (1, 1), (1, 2), (2, 1), (2, 2).

8. Обладают ли ситуации равновесия свойствами, аналогичными седловым точкам:

(): Совпадение выигрышей во всех седловых точках;

Наличием цены игры;

():

Взаимозаменяемостью компонент;

():

9. Пусть = (1,..., ) и = (1,..., )– смешанные стратегии в биматричной игре с матрицами выигрышей игроков = ( ) и = ( ) ( = 1,.., ; = 1,..., ) Рассмотрим случайные величины:

В смешанном расширении данной биматричной игры выигрыши игроков 1 и 2 определяются как мат. ожидания случайных величин....

10. Теорема Нэша: Всякая биматричная игра имеет... в смешанных стратегиях.

Варианты ответа: Оптимальный исход;

11. Пусть – множество игроков. Всякое подмножество называется....

Варианты ответа: Коалицией;

12. Пусть =<,, ( ), ( ) > – коалиционная структура, – семейство коалиций. Состояние * называется -устойчивым, если для всех....

Варианты ответа: Оно является наиболее предпочтительным 13. Для игры лиц рассмотрим -устойчивость ситуации * в случаях, когда есть:

–семейство всех 1-элементных коалиций;

–коалиция всех игроков;

–семейство всех непустых коалиций;

Расположите в следующем порядке условия (), (), () для ситуации * :

() Ситуация * оптимальна по Парето;

* – ситуация сильного равновесия;

* – ситуация равновесия по Нэшу.

Варианты ответа: (,, ) Лекция Нахождение оптимальных решений биматричных игр в смешанных стратегиях Основные вопросы: 1. Условия равновесности ситуации в смешанных стратегиях в биматричной игре. Описание множества ситуаций равновесия биматричной игры. 2. Ситуации равновесия в биматричных играх формата 22. Задача № 21: Борьба за рынки сбыта. 3. Кооперативный подход к анализу биматричной игры. Противоречие между выгодностью и устойчивостью. 4. Кооперативное решение биматричной игры как задача 2–критериальной оптимизации. 5. Арбитражное решение Нэша для биматричных игр. Задача № 22: Оптимальное распределение прибыли (кооперативное решение игры без разделения полезности).

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

Лемма 16.1. Пусть (,) — биматричная игра формата.

Для того, чтобы ситуация в смешанных стратегиях (0, 0 ) была ситуацией равновесия в игре (,), необходимо и достаочно, чтобы она была устойчивой относительно всех чистых отклонений игроков, то есть чтобы при всех = 1,...,, = 1,..., выполнялись неравенства:

Действительно, необходимость очевидна по определению ситуации равновесия. Докажем достаточность. Пусть = (1,..., ) — произвольная смешанная стратегия игрока 1. Умножим обе части первого неравенства (16.1) на 0 и просуммируем по = 1,. Тогда левая часть полученного неравенства по правилу 13.4 будет равна (, 0 ), а (, ) (, ). Аналогично доказывается, что при произвольной смешанной стратегии выполняется (0, ) (0, 0 ). Получаем, что (0, 0 ) — ситуация равновесия.

Лемма 16.2. (правило дополняющей нежесткости). Пусть (0, 0 ) — ситуация равновесия в смешанных стратегиях в игре (,). Тогда для любых Sp 0, Sp 0 имеют место равенства:

Доказательство. Произвольная ситуация (0, 0 ) является ситуацией равновесия в игре (,) тогда и только тогда, когда функция (, 0 ), рассматриваемая как функция одной пременной, принимает наибольшее значение при = 0, а функция (0, ), рассматриваемая как функция одной переменной, принимает наибольшее значение при = 0. Для доказательства утверждений леммы 16.2 остается воспользоваться правилом 13.6.

Перейдем теперь к описанию множества ситуаций равновесия биматричной игры. Рассмотрим вначале вспомогательную задачу нахождения ситуаций равновесия биматричной игры, имеющих заданный набор спектров. Пусть (,) — биматричная игра с матрицами выигрышей игроков =, = ( = 1, ; = 1, ). Зафиксируем пару непустых подмножеств 1 {1,..., }, 2 {1,..., }. Наша ближайшая задача — найти такие ситуации равновесия (0, 0 ) игры (,), для которых Пусть — –я строка матрицы и — –й столбец матрицы. Обозначим через 1 матрицу, строками которой являются разности строк 1, где 1 — первый (наименьший) номер в 1, 1, = 1 ; через 2 — матрицу, столбцами которой являются разности столбцов 1, где 1 — первый (наименьший) номер в 2, 2, = 1.

Справедливо следующее утверждение.

Лемма 16.3. Если (, ) — ситуация равновесия в игре (,) и Sp = 1, Sp = 2, тогда вектор–строка является решением однородной системы линейных уравнений а вектор–столбец — решением однородной системы линейных уравнений Доказательство. Положим 1 = {1,..., }, 2 = {1,..., }. По правилу дополняющей нежесткости (лемма 16.2) для всех = 1,..., выполняется (, ) = (, ), отсюда (, ) (, 1) = 0 ( = 2,..., ).

Используя разложение функции выигрыша по чистым стратегиям (Правило 13.4), получаем:

Замечая, что последняя сумма может быть представлена в матричной записи в виде произведения вектора–строки на вектор–столбец ( удовлетворяет системе уравнений (16.4). Аналогично проверяется, что вектор удовлетворяет системе уравнений (16.5).

Итак, ситуации равновесия игры (,) следует искать среди пар векторов (, ), где есть решение (16.4), а — решение (16.5).

Для формулировки необходимого и достаточного условия ситуации равновесия с заданными спектрами (1, 2 ), введем матрицу 1, строками которой являются разности строк 1, где 1 ; также матрицу 2, столбцами которой являются разности столбцов 1, Теорема 16.1. Для того, чтобы ситуация в смешанных стратегиях (0, 0 ), где Sp 0 = 1 и Sp 0 = 2 являлась ситуацией равновесия в биматричной игре (,), необходимо и достаточно, чтобы a) вектор 0 был решением системы линейных уравнений (16.4);

b) вектор 0 был решением системы линейных уравнений (16.5);

c) вектор 0 был решением системы линейных неравенств:

d) вектор 0 был решением системы линейных неравенств:

(Неравенство понимается как покомпонентное.) Доказательство. Необходимость условий a) и b) показана в лемме 16.3. Необходимость условий b) и c) проверяется аналогичным образом. Покажем достаточность. Рассмотрим ситуацию (0, 0 ), удовлетворяющую условиям a), b), c), d). На основании а) (0, ) = + 1,...,. Умножая равенство (0, ) = (0, 1) на, суммируя по = 1, и используя правило 13.4, получаем (0, 0 ) = (0, 1), откуда для всех = 1,..., имеем неравенство (0, ) (0, 0 ).

Аналогично устанавливается, что (, 0 ) (0, 0 ) для всех = 1,...,. По лемме 16.1 ситуация (0, 0 ) является ситуацией равновесия в игре (,), что и заканчивает доказательство.

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

Случай 1. Обозначим через [1,2 ] подматрицу матрицы, состоящую из тех элементов, для которых 1 и 2. Аналогичным образом определяем подматрицу [1,2 ] матрицы.

Если матрицы [1,2 ] и [1,2 ] обе оказываются невырожденными, то все решения системы (16.4) и все решения системы (16.5) пропорциональны между собой. В этом случае может быть только одна ситуация (, ), для которой является решением системы (16.4), а — решением системы (16.5). Тогда неравенства (16.6) и (16.7) должны быть проверены для компонент этой единственной ситуации.

Случай 2. Ситуация (0, 0 ) в игре (,) называется вполне смешанной, если спектр 0 состоит из всех чистых стратегий игрока 1 и спектр 0 из всех чистых стратегий игрока 2. При установлении того, что вполне смешанная ситуация (0, 0 ) является ситуацией равновесия, условия c) и d) проверять не надо, так как они выполнены автоматически. Из теоремы 16.1 следует, что биматричная игра (,) имеет вполне смешанную ситуацию равновесия тогда и только тогда, когда системы однородных уравнений (16.4) и (16.5) имеют положительные решения.

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

Зафиксируем два непустых подмножества 1 {1,..., }, 2 {1,..., }.

Пусть 1 (1, 2 ) — множество всех векторов, таких, что (2) является решением системы уравнений (16.4), (3) является решением системы неравенств (16.6).

Пусть 2 (1, 2 ) — множество всех векторов, таких, что (2 ) является решением системы уравнений (16.5), (3 ) является решением системы неравенств (16.7).

Согласно теореме 16.1, множество всех ситуаций равновесия игры (,), имеющих спектр (1, 2 ), есть 1 (1, 2 )2 (1, 2 ). Следовательно, множество ((,) ) всех ситуаций равновесия игры (,) может быть представлено в виде Таким образом, нахождение всех ситуаций равновесия игры (,) в смешанных стратегиях сводится к перебору пар непустых подмножеств (1, 2 ) и нахождению при фиксировнных 1 и 2 множеств 1 (1, 2 ) и 2 (1, 2 ). Практически это осуществимо лишь для биматричных игр небольших форматов.

2. Дадим описание ситуаций равновесия в биматричных играх формата 2 2. Такая игра задается парой матриц где — матрица выигрышей игрока 1, — матрица выигрышей игрока 2. Установим следующее Правило 16.1. Если в биматричной игре формата 2 2 элементы, стоящие в одном столбце матрицы, и элементы, стоящие в одной строке матрицы, попарно различны, то в такой игре ситуации равновесия могут быть либо чистыми, либо вполне смешанными.

Действительно, предположим, что имеется ситуация равновесия, в которой стратегия одного игрока, например, игрока 1, является чистой, а стратегия игрока 2 — смешанной. Тогда по условию дополняющей нежесткости (лемма 16.2) должно выполняться (1, 1) = (1, 2), то есть 1 = 2, что противоречит сделанному предположению.

Найдем теперь условия, при которых вполне смешанная ситуация (, ) будет ситуацией равновесия в игре 22. Согласно теореме 16.1, вектор = (1, 2 ) должен быть положительным решением системы уравнений (16.4); добавляя условия нормировки, приходим к системе:

Эта система эквивалентна системе Полагая = 1 + 2 ) (2 + 1 ), получаем, что система (16.9) имеет (единственное) решение тогда и только тогда, когда 0 < < 1, причем в этом случае решение системы (16.9) есть 1 =, 2 = 1.

Для компонент вектора = (1, 2 ) имеем систему условий Полагая = 1 + 2 ) (2 + 1 ), получаем аналогичным образом, что система (16.11) имеет (единственное) решение тогда и только тогда, когда 0 < < 1, и в этом случае решение системы (16.11) есть 1 =, Итак, если 0 <, < 1, то игра (,) имеет, причем только одну вполне смешанную ситуацию равновесия (0, 0 ), где 0 = (, 1 ), Замечание. Сравнивая полученные выражения стратегии 0 и 0 во вполне смешанной ситуации равновесия с формулами (14.3) и (14.4), видим, что 0 совпадает с оптимальной смешанной стратегией игрока 1 в матричной игре, а 0 — с оптимальной стратегией игрока 2 в матричной игре. Таким образом, во вполне смешанной ситуации равновесия игрок 1 минимизирует ожидаемый выигрыш игрока 2, а игрок 2 минимизирует ожидаемый выигрыш игрока 1. Здесь наблюдается "антагонизм поведения"при отсутствии прямого "антагонизма интересов".

Задача № 21: Борьба за рынки сбыта.

Фирма намерена сбыть партию товара на одном из двух рынков, которые контролируются более крупной фирмой. С этой целью она проводит подготовительную работу, связанную с опреденными затратами. Если фирма разгадает — на каком рынке фирма будет продавать свой товар, то она примет контрмеры и восприпятствует "захвату"рынка (этот вариант означает поражение фирмы ); если нет, то фирма одерживает победу. Предположим, что для фирмы проникновение на первый рынок более выгодно, чем проникновение на второй, но и борьба за первый рынок требует от нее больших средств. Например, победа фирмы на первом рынке приносит ей вдвое большую прибыль, чем победа на втором, но зато поражение на первом рынке полностью ее разоряет.

Составим математическую модель этого конфликта, считая фирму игроком 1, а фирму — игроком 2. Стратегии игрока 1: 1–я — проникновение на рынок 1, 2–я — проникновение на рынок 2; стратегии игрока 2: 1–я — контрмеры на рынке 1, 2–я — контрмеры на рынке 2. Пусть для фирмы ее победа на 1–м рынке оценивается в 2 единицы, а победа на 2-м рынке — в 1 единицу; поражение фирмы на 1–м рынке оценивается в 10, а на 2–м — в 1. Для фирмы ее победа составляет, соответственно, 5 и 1, а поражение 2 и 1.

Получаем в итоге биматричную игру (,) с матрицами выигрышей По правилу 16.1 эта игра может иметь либо чистые, либо вполне смешанные ситуации равновесия. Ситуаций равновесия в чистых стратегиях здесь нет. (Содержателно этот факт можно объяснить следующим рассуждением: если стратегия фирмы была разгадана фирмой, то в этой ситуации отклонение выгодно для фирмы ; в противном случае отклонение выгодно для фирмы.) Убедимся теперь, что данная игра имеет вполне смешанную ситуацию равновесия. Находим:

= (1 2)/(11 3) = 3/14; = (1 + 1)/(6 + 3) = 2/9. Итак, рассматриваемая игра имеет единственную ситуацию равновесия (0, 0 ), где 0 = (2/9, 7/9), 0 = (3/14, 11/14). В данной игре ситуация равновесия не может быть реализована в виде физической смеси чистых стратегий, однако она может быть реализована при многократном разыгрывании этой игры (то есть при многократном воспроизведении описанной ситуации) следующим образом. Фирма должна использовать чистые стратегии 1 и 2 с частотами 2/9 и 7/9, а фирма — чистые стратегии 1 и 2 с частотами 3/14 и 11/14. При отклонении одной из фирм от указанной смешанной стратегии отклонившаяся фирма уменьшает свой ожидаемый выигрыш.

3. Как отмечалось в лекции 15, равновесие является важнейшим принципом оптимальности в бескоалиционных играх, то есть играх, в которых не рассматривается образование коалиций. Коалиция является формой кооперации, направленной на увеличение первональных возможностей игроков, или, в теоретико–игровых терминах, на увеличение их выигрышей. Отметим, что в антагонистической (в частности, в матричной) игре кооперация игроков лишена смысла, так как в такой игре улучшение положения одного из них приводит к ухудшению положения другого. При переходе от матричной игры к биматричной картина меняется: в биматричной игре кооперация игроков может улучшить положение их обоих.

В биматричной игре имеется только одна нетривиальная коалиция (то есть коалиция, состоящая более, чем из одного игрока) — коалиция обоих игроков. Для пояснения отличий между индивидуальным выбором решений обоими игроками и совместным принятием решения коалицией этих игроков, рассмотрим следующий Пример 16.1: Конкурс на реализацию проекта.

Две фирмы участвуют в конкурсе на реализацию некоторого проекта, причем доход от реализации проекта составляет 10 ден. ед. Каждая фирма может либо подать простую заявку на участие в конкурсе (затраты равны 1–й ден. ед.), либо представить программу реализации проекта (затраты равны 3–м ден. ед.). Условия конкурса таковы, что в случае, когда обе фирмы выбирают одинаковый способ действий, заказ на реализацию проекта, а также доход, делится между ними пополам; если же фирмы выбирают различные способы действий, то предпочтение отдается той, которая представила программу.

Представим описанную конфликтную ситуацию в виде биматричной игры. Игроками здесь выступают фирмы 1 и 2; стратегии игроков: — подача заявки, — подача программы. В ситуации (, ) прибыль каждой фирмы равна 5 1 = 4; в ситуации (, ) каждая фирма имеет прибыль 5 3 = 2. Если же одна фирма подает программу, а другая — заявку, то первая получает прибыль в 10 3 = 7, а вторая имеет убытки в 1 ден.

ед. Итак, приходим к биматричной игре, заданной таблицей 16.1.

Здесь имеется единственная ситуация равновесия по Нэшу — ситуация (, ), в которой каждая из фирм получает прибыль в 2 ден. ед. Если игра находится в ситуации (, ), то ни одному из игроков не выгодно одностороннее отклонение от этой ситуации (так как отклонившийся игрок уменьшает свой выигрыш). Но если игроки 1 и 2 оба отклоняются от ситуации (, ), то возникает ситуация (, ), которая является более выгодной для них обоих. Однако переход от ситуации (, ) к ситуации (, ) может произойти только как результат договора между игроками, что осуществимо лишь при создании коалиции {1, 2} этих игроков. Объединение игроков 1 и 2 в коалицию требует, как минимум, возможности обмена информацией между ними. Если же игроки не могут обмениваться информацией, то каждый из них будет опасаться менять выбранную им стратегию на стратегию, так как это приводит к уменьшению выигрыша отклонившегося игрока.

Рассмотренный пример демонстрирует одну важную особенность биматричных игр — возможность наличия противоречия между выгодностью и устойчивостью. Действительно, ситуация (, ) является устойчивой (равновесной), но невыгодной; ситуация (, ) является выгодной для обоих игроков, но неустойчивой. Поэтому, если игроки 1 и 2 заключают между собой договор — придерживаться обоим стратегии, то этот договор будет находится под угрозой нарушения, так как каждому игроку выгодно одностороннее отклонение от него.

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

Проанализируем — как может быть реализована идея выгодности в рамках неантагонистической игры двух лиц. Пусть — множество стратегий игрока 1 и — множество стратегий игрока 2. Если игроки 1 и образуют коалицию {1, 2}, то эта коалиция может создать любую ситуацию (, ) и, следовательно, реализовать любой исход игры.

Возникает вопрос — какой исход игры в этом случае следует считать наиболее выгодным для коалиции {1, 2}, то есть оптимальным для нее?

Скажем, в рамках примера 16.1, игроки 1 и 2, объединившись в коалицию, очевидно, предпочтут исход (4, 4) исходу (2, 2), однако исходы (7, 1) и (1, 7) также являются "кандидатами"на оптимальный исход.

В общем случае для биматричной игры (,) рассмотрение вопроса об ее оптимальном исходе с точки зрения коалиции {1, 2} удобно представить в геометрической форме следующим образом. На координатной плоскости (1, 2 ) изобразим точки, координатами которых являются выигрыши игроков (, ) в каждой возможной ситуации (, ), где = 1,...,, = 1,..., (по оси 1 откладываем выигрыши игрока 1 и по оси 2 — выигрыши игрока 2). При этом возникает "картинка"вроде изображенной на рис. 16.1. Поскольку коалиция {1, 2} может выбрать любой из представленных исходов, то получается фактически задача 2–критериальной оптимизации, где игрок 1 стремится максимизировать критерий 1, а игрок 2 стремится максимизировать критерий Как указывалось в лекции 5, анализ задачи многокритериальной оптимизации содержит 2 этапа. 1–этап базируется на отношении доминирования по Парето. Отбрасывая исходы, доминируемые по Парето, получаем множество Парето–оптимальных исходов (скажем, в примере, представленном на рис. 16.1, Парето–оптимальными исходами будут исходы {4, 9, 11, 12}). Выбор оптимального исхода следует производить из множества Парето–оптимальных исходов. 2–й этап — решение вопроса: какой исход из множества Парето–оптимальных исходов следует рассматривать в качестве оптимального исхода игры?

Отметим, что отбрасывая доминируемые по Парето исходы, игроки выступают как союзники, так как этот шаг выгоден им обоим. Однако при сравнении любых двух Парето–оптимальных исходов игроки из союников превращаются в противников: любые два Парето–оптимальных исхода несравнимы по Парето, следовательно, увеличение выигрыша одного игрока влечет уменьшение выигрыша другого игрока.

Для решения задачи нахождения оптимального исхода коалиции игроков в биматричной игре сделаем еще одно допущение: для коалиции {1, 2} допустим использование не только чистых, но и смешанных стратегий.

Определение. Смешанной стратегией коалиции {1, 2} в биматричной игре (,) будем называть всякий вероятностный вектор =, на множестве чистых ситуаций этой игры (предполагается, что, 0, Замечание. Предположим, что игрок 1 использует смешанную стратегию = (1,..., ), а игрок 2 — смешанную стратегию = (1,..., ). Тогда на множестве ситуаций игры возникает вероятностный вектор =,, где, = · ( = 1, ; = 1, ); он будет по определению смешанной стратегией коалиции {1, 2}. Однако вектора указанного вида реализуют лишь независимые вероятностные распределения на множестве чистых ситуаций игры. Возможность реализации произвольного, а не только независимого распределения на множестве чистых ситуаций игры — есть проявление "эффекта кооперации"применительно к смешиванию стратегий игроков.

Допущение смешанных стратегий коалиции {1, 2} приводит к тому, что вместе с двумя исходами (1, 2 ), (, ) коалиция {1, 2} может реализовать также исход (1, 2 )+(1)(, ) = (1 +(1), 2 +( )2 ), где 0 1. С геометрической точки зрения это означает, что множество исходов биматричной игры (,) превращается в многоугольник, вершинами которого будут точки (, ) ( = 1, ; = 1, ). При этом исходы, оптимальные по Парето, составляют "северо–восточную границу"этого многоугольника, см. рис. 16.2. Задача нахождения кооперативного решения биматричной игры сводится теперь к построению правила, которое для каждого такого многоугольника исходов указывает единственный оптимальный исход, принадлежащий его "северо– восточной границе". Рассмотрим решение этой задачи, известное в теории игр как арбитражное решение Нэша.

5. Арбитражное решение представляет собой некоторую систему требований (аксиом), с помощью которых для любой игры выделяется ее единственное решение — оптимальный исход этой игры.

Для биматричной игры (,) обозначим через область на плоскости (1, 2 ), которая совпадает с множеством исходов этой игры в смешанных стратегиях; пусть — цена матричной игры, — цена матричной игры в смешанных стратегиях. При этом точка 0 (, ) называется точкой status quo. Арбитражное решение Нэша для каждой области с выделенной точкой 0 указывает единственную точку * (*, * ) области, которая интерпретируется как оптимальный исход.

Математически арбитражное решение Нэша определяется как отображение, которое каждой паре вида (, (, )) ставит в соответствие точку (*, * ), причем отображение удовлетворяет следующим аксиомам.

Требование коллективной рациональности есть не что иное, как оптимальность исхода (*, * ) по Парето.

(2) Индивидуальная рациональность: *, *.

Требование индивидуальной рациональности означает, что при оптимальном исходе каждый игрок должен получить не меньше, чем его максимальный гарантированный выигрыш (не меньше "своего"максимина, совпадающего с ценой соответствующей игры).

(3) Линейность: Пусть область получается из с помощью линейного преобразования вида Смысл аксиомы линейности состоит в том, что оптимальное решение не должно зависеть от выбора начала отсчета и масштаба измерения выигрышей.

(4) Симметрия: Если множество исходов симметрично относительно биссектрисы первого координатного угла и =, тогда * = *.

Эта аксиома постулирует равноправие игроков.

(5) Независимость от посторонних альтернатив: Пусть 1 и (, (, )) 1. Тогда Эта аксиома требует, чтобы арбитражное решение для данного множества исходов являлось также арбитражным решением для любого своего подмножества, в которое оно попадает. Другими словами, добавление новых исходов не должно менять предпочтения старых.

Результат, доказанный Нэшем, состоит в следующем: отображение, удовлетворяющее аксиомам 1–5, существует и единственно.

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

Задача № 22: Оптимальное распределение прибыли (кооперативное решение игры без разделения полезности).

Имеется две фирмы: первая может выпускать одно из изделий 1 или 2, вторая — одно из изделий 1, 2 или 3, которые затем продаются на одном рынке. Если первая фирма выпускает изделие ( = 1, 2), а вторая — изделие ( = 1, 2, 3), то прибыль этих фирм (зависящая оттого, являются эти изделия взаимнодополнительными или конкурирующими), определяется таблицей 16.2. Считая, что фирмы заключают между собой договор, найти справедливое распределение прибыли, используя арбитражное решение Нэша.

Метод решения.

1. В декартовой системе координат строим многоугольник исходов, вершинами которого являются точки, координаты которых заданы в таблице 16.2. (рис. 16.3).

2. Выделяем в этом многоугольнике множество Парето–оптимальных исходов (северо–восточную границу).

Замечание. Так как игра имеет седловую точку в чистых стратегиях, ее цена совпадает с исходом в седловой точке, откуда = 1. Цена игры может быть найдена графоаналитическим методом (лекция 14, п.2); = 15/8.

4. Вводим новую систему координат, перенося начало в точку (, ).

Арбитражное решение Нэша есть та точка * (*, * ) построенного многоугольника, которая лежит в первой координатной четверти новой системы координат и обращает в максимум произведение координат.

Для нахождения точки * заметим, что линия, для которой произведение координат имеет постоянное значение, определяется уравнением 1 · 2 = и, следовательно, является равнобочной гиперболой, асимптотами которой служат оси новой декартовой системы координат. Таким образом, * есть та точка, в которой гипербола данного семейства касается прямой. Приближенно точку * можно найти с помощью рис. 16.3. Координаты точки * (в старой системе координат) дают арбитражное решение Нэша для поставленной задачи; в нашем случае * 2.6, * 3.4. Для нахождения точных значений координат точки * надо составить систему из уравнения прямой и уравнения гиперболы нашего семейства; параметр находится из условия единственности решения такой системы (дискриминант квадратного трехчлена, полученного при подстановке одного уравнения в другое, должен быть равен нулю).

первого уравнения во второе, получаем квадратное уравнение 8( ) 251 + 8 = 0. Решение этого уравнения, получающееся при обращении дискриминанта в нуль, есть = 25/16; из первого уравнения системы получаем = 25/16. Переходя к старой системе координат, находим координаты точки * : * = + = 41/16, * = + = 55/16.

Итак, "правильное"распределение прибыли (оптимальное решение), диктуемое арбитражным решением Нэша, таково: игрок 1 получает 41/ ден.ед., а игрок 2 получает 55/16 ден. ед.

Реализация оптимального решения осуществляется некоторой смешанной стратегией коалиции {1, 2}. Чтобы найти смешанную стратегию коалиции {1, 2}, реализующую исход (*, * ), надо "смешать"ситуации (1, 1 ) и (2, 2 ), приводящие к исходам (3, 3) и (1, 5), в некоторой пропорции так, чтобы выполнялось равенство: (3, 3)+(1)(1, 5) = (41/16, 55/16), откуда = 25/32, 1 = 7/32. Итак, для получения "справедливой"доли фирмы 1 и 2 должны воспроизводить ситуацию (1, 1 ) с частотой 25/32, ситуацию (2, 2 ) с частотой 7/32, а остальные ситуации не воспроизводить совсем.

Замечание 1. Рассматриваемое здесь кооперативное решение биматричной игры предполагает "неделимость"выигрышей игроков (в частности, невозможность передачи части выигрыша от одного игрока к другому). В теории игр такое решение называется кооперативным решением без разделения полезности.

Замечание 2. Арбитражное решение Нэша может быть использовано для решения задачи многокритериальной оптимизации для случая, когда критерии являются несравнимыми между собой (в частности, когда невозможно нахождение локального коэффициента замещения). В этом случае в качестве точки status quo выступает точка, координатами которой являются минимально допустимые значения критериев.

Тест для самоконтроля к лекции 1. Для того, чтобы в биматричной игре Г(,) формата ситуация в смешанных стратегиях (0, 0 ) была ситуацией равновесия, необходимо и достаточно, чтобы при всех = 1,..., и = 1,..., выполнялось....

2. Пусть в биматричной игре Г(,) формата 2 2 элементы, стоящие в одном столбце матрицы, и элементы, стоящие в одной строке матрицы, попарно различны. Тогда ситуации равновесия....

Варианты ответа: Отсутствуют;

3. Фирма может продавать товары 1, 2, а фирма – товары 1, 2.

В зависимости от сочетания продаваемых товаров прибыль этих фирм задается таблицами:

В полученной биматричной игре ситуация равновесия по Нэшу есть (*, * ), где....

Варианты ответов: (): * = ( 5, 1 ) 4. Пусть в биматричной игре (0, 0 )– ситуация равновесия по Нэшу.

Могут ли оба игрока увеличить свои выигрыши при одновременном отклонении от ситуации равновесия?

Варианты ответа: Да, всегда;

5. В биматричной игре Игрок Ситуацией равновесия по Нэшу является....

Варианты ответа: (1, 1), (1, 2), (2, 1), (2, 2).

6. В биматричной игре(зад. 5) ситуациями, оптимальными по Парето, являются....

Варианты ответа: (1, 1), (1, 2), (2, 1), (2, 2).

7. Смешанной стратегией коалиции {1, 2} в биматричной игре Г(, ) называется....

Варианты ответа: Вероятностный вектор на множестве 8. В биматричной игре Г(, ) коллективная рациональность исхода (*, * ) означает, что....

Варианты ответа: * есть наибольший выигрыш игрока 1;

9. В биматричной игре Г(, ) индивидуальная рациональность исхода (*, * ) означает, что..., где – цена игры Г, – цена игры Г.

Варианты ответа: * =, * = 10. Смысл аксиомы линейности в арбитражном решении Нэша состоит в независимости оптимального решения от....

Варианты ответа: Цен игр Г и Г ;

11. Независимость от посторонних альтернатив означает, что арбитражное решение должно быть также решением....

Варианты ответа: Для любого своего подмножества;

12. В явном виде арбитражное решение Нэша для задачи (,, ) есть точка (*, * ), для которой....

Варианты ответа: Сумма выигрышей игроков (1 + 2 ) достигает Лекция Кооперативные игры Основные вопросы: 1. Коалиции. Характеристическая функция игры лиц. Свойство супераддитивности. 2. Эквивалентность кооперативных игр. Величина кооперативного эффекта коалиции. 3. Существенные и несущественные игры. 0 1 редуцированная форма игры. 4. Дележи.

Условия существенности и несущественности игры в терминах дележей.

5. Задача № 23: Рынок трех лиц.

1. Кооперативный аспект игры связан с возможностью образования в ней коалиций игроков. Частично этот вопрос уже затрагивался нами при рассмотрении кооперативного решения биматричной игры (лекция 16). Однако наиболее существенные проблемы, связанные с образованием коалиций, возникают для игр с числом игроков больше двух.

Рассмотрим игру лиц в нормальной форме (см. лекцию 15) Определение. Коалицией в игре называется произвольное подмножество игроков = {1,..., }. В частности, одноэлементное множество {}, состоящее из единственного игрока, по определению считается коалицией. Допускается также пустая коалиция и коалиция, содержащая всех игроков.

Сформулируем основные предположения, касающиеся возможностей кооперативного поведения игроков в игре.

(1) Возможно образование любых коалиций.

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

Формально это условие означает, что множеством стратегий коалиции (3)Суммарный выигрыш, полученный всеми игроками коалиции, может быть распределен между ее членами любым способом.

Это условие включает в себя, во–первых, "безграничную делимость"полезностей игроков и, во–вторых, возможность "передачи полезности"от одного игрока к другому (как говорят в теории игр — возможность "побочных платежей").

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

В кооперативной игре возможности коалиции можно охарактеризовать одним числом (), представляющим собой максимальный гарантированный суммарный выигрыш игроков коалиции в наиболее неблагоприятных для нее условиях — когда все остальные игроки также объединяются в коалицию с противоположными интересами. Формально () есть цена антагонистической игры коалиции против коалиции остальных игроков. Так как множеством стратегий коалиции является, множеством стратегий коалиции является и функция выигрыша коалиции есть =, то цена построенной антагонистической игры определяется равенством:

где Замечание 1. В случае, когда множества стратегий игроков конечны, операторы sup и inf превращаются, соответственно, в max и min;

равенство (17.2) дает тогда нижнюю цену получающейся матричной игры.

Замечание 2. Суммирование выигрышей разных игроков имеет смысл лишь тогда, когда они измеряют свои полезности в одной шкале. Поэтому, если первоначально это условие не выполнено, то при переходе к кооперативному варианту игры необходимо "пересчитать"функции выигрыша игроков, приведя их к единой шкале.

Определение. Функция, которая каждой коалиции ставит в соответствие число (), определенное равенством (17.2), называется характеристической функцией игры. Пара,, где — множество игроков и — характеристическая функция игры, называется кооперативной игрой, построенной для игры.

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

Теорема 17.1. Характеристическая функция обладает следующими основными свойствами:

(1) () = 0 (персональность);

(2) Если 1 2 =, то (1 ) + (2 ) (1 2 ) (супераддитивность).

Доказательство. Свойство (1) очевидно из определения. Докажем (2). Пусть 1 2 =. По определению супремума для любого > найдутся такие стратегии 1 1 и 2 2, что в любой ситуации будут выполнены неравенства: 1 (1 ) (1 ), 2 (2 ) (2 ). Определим стратегию 1 2 коалиции 1 2, для которой ее –я компонента совпадает с –й компонентой стратегии 1, если 1 и с –й компонентой стратегии 2, если 2 (такая стратегия существует ввиду условия 1 2 = ). Замечая, что (1 2 ) = (2 )1 = (1 )2, получаем при произвольной ситуации :

Складывая эти неравенства и учитывая, что 1 + 2 = 1 2, получаем откуда следовательно, Свойство супераддитивности по индукции распространяется на любое число коалиций, а именно, для произвольного семейства ( )=1, попарно непересекающихся коалиций имеет место В частности, представляя произвольную коалицию в виде семейства одноэлементных коалиций {}, где, получаем Свойство супераддитивности характеристической функции имеет следующий содержательный смысл. Соединяя свои возможности, коалиции 1 и 2 получат во всяком случае не менее того, что они получили бы в сумме, действуя порознь. Для непересекающихся коалиций 1 и разность (1 2 ) ((1 ) + (2 )) есть неотрицательное число, показывающее дополнительную выгоду, которую получают коалиции 1 и от объединения в "единое целое". В частности, если эта разность равна нулю, то объединение коалиций 1 и 2 в одну коалицию 1 2 не приносит этим коалициям никакой дополнительной выгоды.

Замечание. В теории игр рассматриваются также характеристические функции, не связанные непосредственно с игрой лиц. А именно, под абстрактной характеристической функцией над множеством игроков = {1,..., } понимается произвольное отображение, которое каждой коалиции ставит в соответствие определенное число ().

Если абстрактная характеристическая функция обладает указанными в теореме 17.1 свойствами персональности и супераддитивности, то пара, называется кооперативной игрой. В конкретных случаях число () имеет разный содержательный смысл, например, оно может характеризовать силу коалиции; ее гарантированные возможности; величину полезности, получаемой этой коалицией; "вклад"в некоторое предприятие (как положительный, так и отрицательный); "уровень притязаний"и т.п. Примеры характристических функций, не связанных непосредственно с игрой общего вида, будут даны ниже.

2. Введем отношение эквивалентности кооперативных игр, рассматриваемых над одним и тем же множеством игроков. Возьмем кооперативную игру,. Зафиксируем положительное число > 0 и чисел ( = 1, ). Положим Убедимся, что также харктеристическая функция, то есть что она удовлетворяет условиям теоремы 17.1.

(2) Установим супераддитивность функции. Для любых двух непересекающихся коалиций 1, 2 имеем:

Определение. Две коопертивные игры, и, называются эквивалентными, если существует положительное число > 0 и чисел ( = 1, ), при которых выполняется равенство (17.5).

Нетрудно проверить, что отношение эквивалентности кооперативных игр является отношением эквивалентности в теоретико–множественном смысле, то есть оно рефлексивно, симметрично и транзитивно.

За счет подбора констант > 0 и ( = 1,..., ) можно от заданной кооперативной игры, перейти к эквивалентной ей кооперативной игре с теми или иными дополнительными свойствами. В частности, полагая = 1 и = (), получаем эквивалентную игру с характеристической функцией 0, имеющей следующий вид:

Согласно (17.4), функция 0 неотрицательна, то есть 0 () 0 для любой коалиции. С другой стороны, любая неотрицательная супераддитивная функция множества () является изотонной, так как условие (1 ). Таким образом, для характеристической функции 0 выполняется Для фиксированной коалиции неотрицательное число 0 () = () будем называть величиной кооперативного эффекта коалиции в игре,. Число 0 () показывает тот дополнительный выигрыш, который получают игроки при объединении их в коалицию.

В терминах кооперативного эффекта условие (17.7) формулируется следующим образом: при увеличении коалиции величина кооперативного эффекта возрастает (не уменьшается).

3. Дадим характеризацию кооперативных игр, в которых не возникает кооперативного эффекта.

Теорема 17.2. Для кооперативной игры, следующие условия эквивалентны между собой:

(a) Характеристическая функция аддитивна (то есть для любых двух непересекающихся коалиций 1, 2 выполняется (1 2 ) = (1 )+ (2 ));

Доказательство. Из (a) следует (b), так как в предположении (a) (a). Докажем равносильную импликацию: из отрицания условия (a) следует отрицание условия (c). Отрицание условия (a) означает, с учетом супераддитивности функции, что для некоторых непересекающихся коалиций 1 и 2 выполняется (1 2 ) > (1 ) + (2 ). Используя это неравенство и (17.4), получаем:

Таким образом, для коалиции 1 2 величина кооперативного эффекта оказывается строго положительной, тогда в силу его изотонности отрицание условия (c).

Кооперативная игра,, удовлетворяющая одному из эквивалентных между собой условий (a), (b), (c) теоремы 17.2 называются несущественной. Наиболее простым для проверки является условие (c). Условие (a) носит чисто математический характер. Условие (b) с помощью функции 0 может быть переписано в виде 0 () = 0; оно означает, что для любой коалиции величина ее кооперативного эффекта равна нулю.

Поскольку множество кооперативных игр, рассматриваемых над фиксированным множеством игроков, разбито на классы эквивалентности, возникает задача выбора в каждом таком классе наиболее простой в некотором смысле игры. С этой целью введем следующее Определение. Говорят, что кооперативная игра, имеет 0 1– редуцированную форму, если Теорема 17.3 Каждая существенная кооперативная игра эквивалентна некотрой кооперативной игре, имеющей 0 1–редуцированную форму.

Доказательство. В силу условия существенности игры выполняется (), = (). Тогда игра, эквивалентна игре,, причем Замечание. В явном виде характеристическая функция * может быть представлена в виде.

Правая часть равенства (17.8) имеет следующий содержательный смысл:

она показывает отношение величины кооперативного эффекта для коалиции к величине кооперативного эффекта для коалиции всех игроков. Ввиду того, что при увеличении коалиции коопертивный эффект возрастает, это отношение не превосходит единицы.

4. Рассмотрим кооперативную игру,. Будем интерпретировать число () как сумму, гарантированно получаемую коалицией. Тогда коалиция всех игроков может гарантированно получить сумму () и затем распределить ее любым способом между всеми игроками. Всякое такое распределение будем трактовать как возможный исход игры,.

Формально указанное распределение есть вектор = (1,..., ) R, –я компонента которого понимается как та сумма, которая достается игроку. Какой исход кооперативной игры, следует считать оптимальным ("правильным "справедливым")?

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

(1) () для всех (индивидуальная рациональность);

Замечание. Требование индивидуальной рациональности означает, что игрок получает при распределении не меньше той величины, которую он может получить гарантированно, действуя в одиночку. Поясним требование коллективной рациональности. Предположим, что (). Тогда разность = () будет положительной. Рассмотрим положительных чисел 1,...,, для которых 1 + · · · + =.

Распределение = (1,..., ), где = +, будет более выгодным, чем распределение, для всех игроков ; тем самым распределение не будет удовлетворять условию оптимальности по Парето. Если же > (), то такой вектор не достижим для коалиции ; таким образом, в этом случае игроки "делят больше, чем имеют".

Определение. Вектор R, удовлетворяющий условиям индивидуальной и коллективной рациональности, называется дележом в кооперативной игре,.

Итак, при поиске оптимального исхода кооперативной игры, мы должны ограничиться только теми распределениями, которые являются дележами. Рассмотрим вначале некоторые формальные свойства дележей. Из условий 1 и 2 следует Правило 17.1. Для того, чтобы вектор = (1,..., ) R был дележом в кооперативной игре,, необходимо и достаточно, чтобы он был представим в виде:

Пояснение. Числа имеют прозрачную интерпретацию: — это добавка игроку 1 к его гарантированной сумме () при разделе "дополнительной прибыли возникающей в результате кооперативного эффекта.

Отметим несколько следствий, вытекающих из правила 17.1.

Следствие 1. Всякая несущественная кооперативная игра имеет единственный дележ: = ((1),..., ()).

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

Следствие 2. Всякая существенная кооперативная игра имеет бесчисленное множество дележей.

Следствие 3. Для кооперативной игры в 0 1–редуцированной форме вектор = (1,..., ) R является дележом тогда и только тогда, когда 0 ( = 1,..., ), Таким образом, для игры в 0 1–редуцированной форме множество ее дележей совпадает с множеством –компонентных вероятностных векторов. В этом случае содержательный смысл –й компоненты вектора — это доля –го игрока при распределении общей полезности, принятой за единицу.

5. Задача № 23: Рынок трех лиц.

Рассмотрим классическую модель рынка, в которой участвует один продавец и два покупателя. Предположим, что у продавца имеется неделимый товар (например, компьютер), который он оценивает в денежных единиц, а первый и второй покупатели оценивают этот товар в и денежных единиц, соответственно (считаем ). Необходимое условие участия всех троих в сделке — выполнение неравенств < и <.

Итак, <. Проанализируем эту ситуацию как игру, считая продавца игроком 1, первого покупателя — игроком 2 и второго покупателя — игроком 3. Характерной особенностью этой игры является возможность совместных действий игроков, то есть возможность образования в ней коалиции (коалиция продавца с покупателем интерпретируется как сделка между ними). Построим характеристическую функцию этой игры, рассматривая () как гарантированную прибыль коалиции ; при этом прибыль коалиции считается равной сумме прибылей всех ее участников. Очевидно, что прибыль возможна лишь для коалиции, содержащей продавца, поэтому (2) = (3) = ({2, 3}) = 0. Далее, (1) = 0, так как продавец, действуя в одиночку, не может обеспечить себе никакой прибыли. Найдем теперь ({1, 2}). Создание коалиции {1, 2} означает, что игроки 1 и 2 вступают в сделку, то есть продавец (игрок 1) продает товар первому покупателю (игроку 2). Сделка "устраивает"обоих игроков только в том случае, когда цена продажи заключена между и, то есть. В этом случае прибыль продавца равна (так как он оценивал свой товар в денежных единиц, а получил денежных единиц); прибыль первого покупателя равна (так как он оценивал товар в денежных единиц, а потратил на его покупку денжных единиц). Общая прибыль коалиции {1, 2} равна ( ) + ( ) =.

Аналогичным образом получаем, что общая прибыль коалиции {1, 3} равна.

Коалиция всех трех игроков {1, 2, 3} может интерпретироваться здесь как сделка всех троих, осуществляемая следующим образом: игрок 3 покупает товар игрока 1 по цене, где < и разность ( ) игроки 2 и 3 делят между собой (то есть игрок 3 отдает часть своей прибыли игроку 2 за его "неучастие в покупке что способствует снижению цены продажи товара). В этом случае общая прибыль коалиции {1, 2, 3} равна. Получаем окончательно:

(1) = (2) = (3) = ({2, 3}) = 0, ({1, 2}) =, ({1, 3}) = ({1, 2, 3}) =.

Приведем эту игру к 0 1–редуцированной форме. Имеем:

Содержательно число * () представляет собой отношение величины кооперативного эффекта для коалиции к величине кооперативного эффекта для коалиции {1, 2, 3} всех игроков.

Тест для самоконтроля к лекции 1. В игре лиц Г=<, ( ), ( ) >. Множеством стратегий коалиции является =....

Варианты ответа:

2. В антагонистической игре коалиции против дополнительной коалиции функция выигрыша коалиции есть =....

Варианты ответа:

3. Значение характеристической функции для коалиции определяется равенством: () =....

Варианты ответа: (, ) 4. Свойство супераддитивности характеристической функции состоит в том, что....

5. Две характеристические функции и над множеством игроков называются эквивалентными, если....

Варианты ответа: () = () для некоторого ;

6. Рассмотрим условия:

() (1 2 ) = (1 ) + (2 ) для любых коалиций 1 2 = ;

Имеют место следующие отношения между этими условиями:....

Варианты ответа: 7. Игра <, > игроков = {1,..., } имеет 0-1 – редуцированную форму, если....

8.... эквивалентна некоторой игре, имеющей 0-1 – редуцированную форму.

Варианты ответа: Всякая игра <, >;

9. Характеристическая функция игры 3-х игроков задается равенствами:

(1) = 2, (2) = (3) = 0, (1, 2) = 2, (1, 3) = 3, (2, 3) = 2, (1, 2, 3) = 5.

Найдите 0-1 – редуцированную форму этой игры.

Варианты ответа:

10. Условие индивидуальной рациональности вектора = (1,..., ) состоит в том, что....

11. Условие коллективной рациональности вектора = (1,..., ) состоит в том, что....

Варианты ответа: = ();

12. Дележом в кооперативной игре <, > называется вектор, удовлетворяющий условиям:

Варианты ответа: > () для всех = 1,..., ;

13. Сколько дележей имеет несущественная кооперативная игра лиц?

Варианты ответа: 0, 1, n,.

14. Множество дележей всякой существенной кооперативной игры....

Варианты ответа: Пусто;

Лекция Оптимальные исходы в кооперативных играх Основные вопросы: 1. Отношение доминирования дележей и его простейшие свойства. 2. –ядро. Критерий принадлежности дележа к –ядру. Задача № 24: Оптимальное распределение прибыли (кооперативное решение игры с разделением полезности). 3. Вектор Шепли, его аксиоматическое обоснование и явное выражение. 4. Вектор Шепли для простых игр. Задача № 25: Оценка "силы"держателей акций.

1. Основной задачей данной лекции является обсуждение вопроса — какие исходы кооперативной игры следует рассматривать в качестве ее оптимальных исходов? Для кооперативной игры, будем интерпретировать число () как некоторую полезность (например, денежную сумму), которую коалиция может гарантированно получить и затем распределить любым способом среди своих членов. Под исходом игры, понимается распределение между всеми ее игроками полезности (). Предварительные условия, накладываемые на такое распределение, состоят в том, что оно должно удовлетворять условиям индивидуальной и коллективной рациональности, то есть должно быть дележом (см.

лекцию 17, п. 4). Однако в существенной кооперативной игре имеется бесконечное множество дележей, поэтому следующий этап определения оптимального исхода кооперативной игры состоит в сужении множества дележей (ср. с определением оптимального исхода в задаче многокритериальной оптимизации, лекция 5).

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

Для произвольной коалиции и дележа = (1,..., ) через () будем обозначать общую сумму, получаемую коалицией в дележе Определение. Говорят, что дележ доминирует дележ по коалиции (записывается ), если Пояснение. Условие (a) означает, что для всех членов коалиции дележ лучше, чем дележ. Условие (b) выражает достижимость (реализуемость) дележа для коалиции.

Определение. Говорят, что дележ доминирует дележ (записывается ), если существует непустая коалиция, для которой. Формально отношение есть объединение отношений по всем непустым коалициям.

Замечание. Отношение доминирования дележей, вообще говоря, не является транзитивным: из того, что и не следует, что.

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

Установим теперь несколько простых свойств отношения доминирования дележей.

Свойство 1) Доминирование дележей по 1–элементной коалиции невозможно.

Свойство 2) Доминирование дележей по коалиции всех игроков невозможно.

Свойство 3) В игре 2–х лиц доминирование дележей невозможно.

Доказательство. 1) Предположим, что. Тогда по условию доминирования (a) > ; в то же время по условию (b) должно быть (), откуда < () в противоречие с тем, что вектор является дележом.

2) Предположим, что. Тогда по условию (a) > для всех рациональности для дележа выполняется () = (), () = () и получаем () > () — противоречие.

Свойство 3) непосредственно следует из 1) и 2).

Важным свойством эквивалентных кооперативных игр является наличие изоморфизма между их отношениями доминирования. Точнее, имеет место следующее Утверждение 18.1. Пусть и — характеристические функции над Тогда отображение = + = 1,..., устанавливает взаимно однозначное соответствие между множеством дележей игры, и множеством дележей игры,, при котором из следует.

Замечание 1. Таким образом, для любой фиксированной коалиции указанное отображение осуществляет изоморфизм отношений доминирования по коалиции. Следовательно, данное отображение является также изоморфизмом отношений доминирования дележей.

Доказательство. Убедимся вначале, что вектор = (1,..., ) является дележом. Используя, что — дележ в игре,, получаем:

Итак, — дележ в игре,. Предположим теперь, что имеет место, то есть выполнены соотношения: > ( ), () ().

Проверим условия доминирования по коалиции для пары (, ).

Итак,. Взаимная однозначность отображения вытекает из существования обратного отображения (обратным будет отображение = / /).

Замечание 2. Утверждение 18.1 позволяет при рассмотрении отношения доминирования дележей переходить от заданной кооперативной игры к любой эквивалентной ей игре, в частности, для существенной игры — к ее 0 1–редуцированной форме.

2. Естественный путь сужения множества дележей основан на их сравнении, которое осуществляется на базе отношения доминирования. Предположим, что игрокам предлагается дележ и в то же время существует такой дележ, что. Последнее означает существование такой непустой коалиции, что, во–первых, дележ является более предпочтительным для всех членов коалиции, чем дележ, и, во–вторых, что дележ может быть реализован коалицией независимо от действий остальных игроков. Поэтому попытка введения дележа должна встретить противодействие со стороны коалиции, имеющей "желание"получить вместо, а также возможность это желание осуществить. Из этих рассуждений можно сделать следующий вывод: предложение дележа может быть принято всеми коалициями игры только тогда, когда этот дележ не является доминируемым.

Определение. Множество недоминируемых дележей кооперативной игры называется ее –ядром.

Следующая теорема характеризует дележи кооперативной игры, попадающие в ее –ядро.

Теорема 18.1. Для того, чтобы дележ кооперативной игры, принадлежал ее -ядру, необходимо и достаточно, чтобы для любой коалиции выполнялось Доказательство. Предположим, что дележ не принадлежит –ядру.

Тогда существует такой дележ, что для некоторой коалиции. Согласно условию доминирования (a) () = (), а согласно условию доминирования (b) () (). Получаем () < (), что противоречит (18.1). Таким образом, достаточность установлена.

Доказательство необходимости проведем вначале при дополнительном предположении: () = 0 для всех. Если для какой–либо коалиции неравенство (18.1) не выполнено, то для нее имеет место () < (). Построим дележ = (1,..., ), полагая (Смысл формулы (18.2) весьма позрачен. Положительная величина () () делится игроками коалиции поровну и добавляется к компонентам "старого"дележа, в результате чего коалиция имеет в сумме (); оставшаяся часть () () делится поровну между игроками, не принадлежащими коалиции.) Заметим, что построенный вектор действительно является дележом, так как все его компоненты неотрицательны и их сумма равна (). Кроме того, выполняется, так как > для всех и () (). Итак, дележ не принадлежит –ядру, что доказывает необходимость.

Наконец, следует заметить, что дополнительное условие, наложенное на характеристическую функцию, не нарушает общности рассуждения. Действительно, для выполнимости указанного условия достаточно перейти к эквивалентной кооперативной игре с характеристической функцией 0 () = () () и воспользоваться замечанием 2 к утверждению 18.1. При этом надо учесть, что неравенства (18.1) инвариантны относительно преобразования, переводящего игру, в эквивалентную игру, 0.

Система неравенств (18.1), определяющая –ядро, задает некоторый многогранник в множестве всех дележей (который иногда может вырождаться в пустое множество). Рассмотрим подробней — что представляет собой –ядро кооперативной игры с малым числом игроков. Напомнм, что в игре 2–х лиц отношение доминирования дележей пусто (см. свойство 3 в данной лекции), поэтому принцип –ядра имеет смысл для игр с числом игроков 3. Возьмем кооперативную игру 3–х лиц, заданную в 0 1–редуцированной форме. В этом случае достаточно задать значения характеристической функции для 2–элементных коалиций; положим: ({1, 2}) = 3, ({1, 3}) = 2, ({2, 3}) = 1. Так как для игры 3–х лиц в 0 1–редуцированной форме множество дележей есть множество вероятностных векторов вида (1, 2, 3 ), где 1, 2, 3 0 и 1 + 2 + 3 = 1, оно геометрически может быть представлено в виде треугольника 1 2 3, причем дележ (1, 2, 3 ) отождествляется с точкой = 1 1 + 2 2 + 3 3 этого треугольника. По теореме 18.1 дележ (1, 2, 3 ) принадлежит –ядру тогда и только тогда, когда выполняется система линейных неравенств:

Так как 1 = 1 (2 + 3 ), то на основании (18.3) будет 1 1 1 ;

аналогично 2 12, 3 13. Построив прямые 1 = 11, 2 = 2, 3 = 1 3, получим искомое –ядро, имеющее вид многоугольника, содержащегося в треугольнике 1 2 3 (некоторые варианты такого многоугольника представлены на рис. 18.1).

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

Задача № 24: Оптимальное распределение прибыли (кооперативное решение игры с разделением полезности).

Имеются три предприятия, специализирующихся на выпуске комплектующих деталей или одинаковой стоимости, причем изделие собирается из одной детали и одной детали. Возможности предприятий по выпуску этих деталей указаны в таблице 18.1. Так как ни одно из предприятий не в состоянии самостоятельно производить данное изделие, то они заключают между собой договор с последующим распределением прибыли. Какое распределение прибыли между этими тремя предприятиями будет оптимальным?

Рассмотрим описанный "производственный конфликт"как игру трех предприятий {1, 2, 3}. Составим характеристическую функцию этой игры, значения которой интерпретируются как число изделий, которое в состоянии произвести соответствующая коалиция. Так как ни одно из предприятий в отдельности, а также коалиция предприятий 1 и 2 не в состоянии производить изделие, то (1) = (2) = (3) = ({1, 2}) = 0.

Далее, предприятия 1 и 3 вместе могут произвести 900 изделий, следовательно ({1, 3}) = 900; аналогично ({2, 3}) = 600. Коалиция всех трех предприятий обеспечивает выпуск 1000 изделий, откуда ({1, 2, 3}) = 1000.

. Находим: * ({1, 2}) = 0, * ({2, 3}) = 0.6, * ({1, 3}) = 0.9.

Согласно приведенного выше описания –ядра игры 3–х лиц, получаем, что в нашем случае –ядро определяется системой неравенств:

Итак, оптимальным решением данной задачи, полученным на основе понятия –ядра, будет любое распределение прибыли, при котором 1–е предприятие получает не более 40% общей прибыли, 2-е – не более 10% и 3–е — все остальное.

Всякое такое распределение будет устойчивым: никакая коалиция предприятий не сможет ему ему эффективно противодействовать.

И обратно, всякое распределение прибыли, не удовлетворяющее условиям (18.4), не будет устойчивым. Возьмем в качестве примера такое распределение прибыли, при котором прибыль делится пропорционально числу деталий, которое предприятие в состоянии произвести. Соответствующий дележ задается вектором (0.36, 0.24, 0.4), который не принадлежит –ядру. Если будет предложено указанное распределение прибыли, то предприятия 1 и 3 смогут ему эффективно противодействовать с помощью объединения своих возможностей (то есть созданием коалиции {1, 3}). Действительно, так как * ({1, 3}) = 0.9, то в этом случае коалиция {1, 3} получает 90% всей прибыли против 76% прибыли, имеющейся при дележе (0.36, 0.24, 0.4).

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

Сделаем еще два замечания, относящихся к задаче № 24.

Замечание 1. Построенная в задаче № 24 математическая модель конфликта в виде кооперативной игры может считаться адекватной только в случае наличия возможности "разделения полезности"между предприятиями; например, такое разделение возможно, если полезность имеет денежный характер, но невозможно, если полезность представляет собой некоторый неделимый продукт. (Рекомендуем читателю сравнить рассматриваемую задачу с задачей № 22 оптимального распределения прибыли без ее разделения.) Замечание 2. Вопрос о выборе конкретного дележа из –ядра (в случае его непустоты) остается открытым. Выбор единственного оптимального дележа из –ядра требует дополнительной информации о свойствах оптимального дележа. Здесь ситуация аналогична выбору оптимального исхода из множества Парето–оптимальных исходов для задачи многокритериальной оптимизации (см. лекции 5–7).

3. Концепция оптимальности решения кооперативной игры, воплощенная в понятии –ядра, обладает при всей своей естественности, рядом недостатков, одним из которых является то, что в некоторых играх –ядро оказывается пустым. Поэтому в теории игр изучались и другие принципы оптимальности исходов кооперативных игр. Важнейшим из них является принцип, предложенный американским математиком Л.Шепли; он основан на построении так называемого вектора Шепли.

Концепция оптимальности, предложенная Шепли, базируется на следующем подходе. Каждой кооперативной игре, ставится в соответствие –компонентный вектор () = (1 (),..., ()), –я компонента которого понимается как справедливый выигрыш, назначаемый игроку в соответствии с его "вкладом"в игру. Таким образом, вектор Шепли можно рассматривать как "справедливое"распределение общей прибыли, полученной коалицией всех игроков в результате кооперативного эффекта (см. лекцию 17). Далее Шепли формулирует ряд аксиом, заключающих в себе определенное понимание "справедливого распределения полезности". Эти аксиомы (в эквивалентной формулировке) состоят в следующих требованиях.

(A1) Аксиома симметрии: () = () для любого автоморфизма игры,.

Пояснение. Под автоморфизмом игры, понимается такая перестановка множества, что () = () для любой коалиции.

Аксиома симметрии выражает тот факт, что игроки, входящие в игру симметрично, должны получить одинаковые выигрыши.

(A2) Аксиома эффективности:

Эта аксиома означает, что распределению подлежит вся сумма ();

формально она выражает условие групповой рациональности исхода, то есть его оптимальности по Парето.

(A3) Аксиома болвана: Если игрок 0 таков, что для любой коалиции выполнено равенство ( {0 }) = (), то 0 () = 0.

Пояснение. Игрок 0, участвующий в формулировке аксиомы (A3), в теоретико–игровой терминологии называется болваном. Из свойства супераддитивности функции сразу же следует, что ({0 }) = 0. Таким образом, игрок 0 не может обеспечить себе никакого выигрыша и никак не влияет на выигрыши коалиций, к которым он присоединяется. Аксиома (A3) требует, чтобы игрок, являющийся болваном, ничего не получал при распределении.

(A4) Аксиома агрегации (линейности): Если и — характеристические функции над множеством, тогда для характеристической функции = + выполняется () = () + ().

Смысл аксиомы агрегации состоит в том, что при участии игрока в двух играх (что соответствует сложению характеристических функций), его выигрыши должны складываться.