«26 сентября 2008 г. Содержание Предисловие 1 1 Вводная лекция 6 Тест для самоконтроля к лекции 1................. 14 I Принятие решений в условиях определённости 16 2 Экстремум функций одной переменной ...»
Отметим, что условия "справедливости"дележа, выражаемые аксиомами (A1)–(A3), являются вполне приемлемыми с содержательной точки зрения. Аксиома (A4) не столь естественна, как предыдущие три аксиомы. Тем не менее, справедлив следующий результат, установленный Шепли в 1953 г.
Теорема 18.2. Существует и притом только одна функция, удовлетворяющая аксиомам (1)–(4).
Вектор () = (1 (),..., ()) называется вектором Шепли для игры,. Вектор Шепли является дележом игры, и в явном виде определяется равенством Приведем одну интерпретацию компонент вектора Шепли. Предварительно рассмотрим следующую комбинаторную задачу. Зафиксируем игрока и коалицию, содержащую этого игрока. Найдем вероятность того, что в случайной перестановке элементов множества все элементы множества {} окажутся до, а все элементы множества — после (считая все перестановки равновероятными). Число интересующих нас перестановок по комбинаторному правилу произведения равно (||1)!(||)!, а так как общее число всех перестановок есть !, то искомая вероятность равна. Далее, будем считать, что "вклад"игрока в содержащую его коалицию равен () ({}), а вероятность присоединения игрока к коалиции {} совпадает с найденной выше вероятностью того, что в случайной перестановке множества {1,..., } игроками, оказавшимися в этой перестановке до, будут, в точности все игроки из {}. Тогда правая часть (18.5) представляет собой математическое ожидание выигрыша игрока в условиях данной рандомизационной схемы.
Наглядно указанную схему рандомизации можно представить следующим образом. Предположим, что игроки 1,..., прибывают к определенному месту друг за другом случайным образом. Если игрок, прибыв к указанному месту, застанет там игроков {}, то он считается присоединившимся к коалиции {}, причем его "вклад"в эту коалицию будет равен тому дополнительному выигрышу, который он вносит в нее, то есть () ({}). Тогда () совпадает с математическим ожиданием (средним значением) выигрыша игрока в условиях данной теоретико–вероятностной схемы.
Таким образом, получаем следующее правило подсчета компонент вектора Шепли:
Правило 18.1. –я компонента вектора Шепли () есть среднее арифметическое разностей () ({}) по всевозможным перестановкам множества {1,..., }, причем в каждой перестановке в качестве коалиции выступает множество игроков, расположенных в ней до индекса.
Пример 18.1. Найдем с помощью правила 18.1 компоненты вектора Шепли для произвольной кооперативной игры 3–х лиц {1, 2, 3} с характеристической функцией, заданной в 0 1–редуцированной форме.
Полагаем ({1, 2}) = 3, ({1, 3}) = 2, ({2, 3}) = 1. Для любой перестановки множества {1, 2, 3} и фиксированного индекса = 1, 2, положим () = () ({}), где — коалиция игроков, расположенных в перестановке до индекса включительно. Составим таблицу 18.2, в которой указаны все перестановки игроков {1, 2, 3} и соответствующие им значения разностей (1). По правилу 18.1 получаем:
Циклируя в равенстве (*) индексы 1, 2, 3, приходим к общей формуле:
где,, — попарно различные индексы из {1, 2, 3}.
Например, для игры рынка трех лиц (см. задачу № 23) согласно (18.6) находим:
Итак, "справедливая"доля продавца составляет более половины общей прибыли (что может быть объяснено его монопольным положением). С другой стороны, как нетрудно подсчитать, 3 () 2 () = 2().
Так как по условию <, то 3 () > 2 (), что согласуется со здравым смыслом: 2–й покупатель обладает большей "конкурентноспособностью поэтому его доля общей прибыли должна быть большей, чем доля 1–го покупателя.
Замечание. Рассмотренные в данной лекции два принципа оптимальности для кооперативных игр — –ядро и вектор Шепли — имеют разные "идейные основания". А именно, оптимальность, заключенная в понятии –ядра, основана на идее устойчивости дележа, а оптимальность в форме вектора Шепли — на идее справедливости дележа. При этом устойчивость дележа определяется внутренним образом — на языке отношения доминирования дележей; справедливость дележа постулируется внешним образом в форме некоторой системы требований (аксиом).
В общем случае вектор Шепли может не принадлежать –ядру, то есть указанные принципы оптимальности приводят к разным решениям.
4. В заключение данной лекции рассмотрим один полезный способ нахождения вектора Шепли для кооперативных игр, характеристическая функция которых принимает только два значения: 0 и 1 (такие игры называются простыми). Для простой игры, все ее коалиции, для которых () = 1, называются выигрывающими. Ясно, что характеристическая функция простой игры полностью определяется перечислением ее выигрывающих коалиций. Будем предполагать здесь, что коалиция, содержащая выигрывающую коалицию, также является выигрывающей. Для простой игры разность () ({}) будет равна 1 тогда и только тогда, когда — выигрывающая коалиция, а {} — еще не выигрывающая; во всех остальных случаях эта разность будет равна нулю.
Определение. Пусть — некоторая перестановка игроков {1,..., }.
Назовем игрока ведущим в данной перестановке, если коалиция игроков {}, расположенных до него в этой перестановке, не выигрывающая, а коалиция — выигрывающая.
На основании правила 18.1 получаем Правило 18.2. Для простой игры с характеристической функцией ее –ая компонента вектора Шепли () есть отношение числа перестановок, в которых игрок является ведущим, к общему числу всех перестановок.
При небольших значениях подсчет компонент вектора Шепли, основанный на правиле 18.2, удобно осуществлять следующим образом. Выпишем все перестановки множества {1,..., } и в каждой из них отметим ведущего игрока (то есть того единственного игрока, который "превращает"невыигрывающую коалицию игроков, стоящих в этой перестановке до него, в выигрывающую). Подсчитывая для каждого фиксированного число перестановок, в которых игрок является ведущим, определяем –ю компоненту вектора Шепли (). Используем указанный прием для решения следующей задачи.
Задача №25: Оценка "силы"держателей акций.
Акции некоторой акционерной компании распределены между четырьмя акционерами, причем 1–й акционер обладает 10% всех акций, 2–й акционер — 20%, 3–й — 30% и 4–й — 40%. На общем собрании акционеров решение принимается по правилу простого большинства (одна акция = одному голосу). Найти оценку "силы"акционеров при данной схеме голосования.
Решение. Выпишем все перестановки игроков {1, 2, 3, 4} и в каждой из них отметим ведущего игрока (то есть того, присоединение которого ко всe предыдущим "создает"более половины голосов, см. таблицу 18.3).
Находим:
игрок 1 является ведущим в 2–х перестановках;
игрок 2 является ведущим в 6–ти перестановках;
игрок 3 является ведущим в 6–ти перестановках;
игрок 4 является ведущим в 10–ти перестановках.
По правилу 18.2 получаем:
Заметим, что вектор Шепли здесь не совпадает с вектором процентного соотношения акций (то есть "вес Шепли"для игрока не пропорционален числу его акций). Например, игрок 4 имеет вдвое больше акций, чем игрок 2, однако соотношение их весов Шепли равно 5/12 : 1/4 = 5 : 3.
Еще более примечательным является совпадение "сил"игроков 2 и 3. Хотя игрок 3 имеет в полтора раза больше акций, чем игрок 2, у игрока 3 нет никаких преимуществ перед игроком 2: оба являются ведущими в 6–ти перестановках. Впрочем, совпадение "сил"игроков 2 и 3 видно уже из того факта, что они симметрично входят в выигрывающие коалиции данной игры. В самом деле, выигрывающими коалициями здесь будут:
{2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}. Перестановка, меняющая местами игроков 2 и 3, а всех остальных оставляющая на месте, сохраняет множество выигрывающих коалиций, и, следовательно, является автоморфизмом построенной игры.
Тест для самоконтроля к лекции 1.В кооперативной игре <, > дележ доминирует дележ по коалиции ( ), если....
Варианты ответа: > для всех ;
2. Пусть для дележей,, выполнено и. Имеет ли место 3. Пусть, – дележи в кооперативной игре <, >. Расставьте логические значения высказываний:
4. Пусть и – характеристические функции над множеством игроков, связанные соотношением:
Введем отображение между дележами этих игр по формуле:
Будут ли при произвольной коалиции условия равносильными между собой?
Варианты ответа: Да, всегда;
5. – ядром кооперативной игры называется....
Варианты ответа: Среднее всех ее дележей;
6. Для того, чтобы дележ кооперативной игры <, > принадлежал ее –ядру, необходимо и достаточно, чтобы для любой коалиции выполнялось условие:
Варианты ответа: () = ();
7. Множество дележей, принадлежащих –ядру игры лиц, где > 3, представляет собой... в симплексе всех дележей.
Варианты ответа: Конечное число точек;
8. В игре трех игроков –ядро представляет собой... в 2-мерном симплексе всех дележей.
Варианты ответа: Точку;
9. Составьте систему условий для дележей, принадлежащих –ядру игры 3-х лиц, характеристическая функция которой определена ниже. Дайте истолкование в терминах распределения общей прибыли.
(1) = (2) = (3) = 0, (1, 2) = 0, 2, (1, 3) = 0, 6, (2, 3) = 0, 7, (1, 2, 3) = 10. Найдите вектор Шепли для игры 3-х лиц, характеристическая функция которой определена в зад. 9. Дайте истолкование в терминах распределения общей прибыли.
Варианты ответа: Ф() = ( 60, 20, 25 );
11. В магазине встречаются три покупателя, первый из которых имеет намерение приобрести товар на сумму 600 ден. ед., второй – на сумму ден. ед. и третий – на сумму 800 ден. ед.. В магазине действует правило, согласно которому при покупке на сумму свыше 1000 ден. ед. предоставляется скидка в 10%, а при покупке на сумму свыше 2000 ден. ед. в 20% от суммы покупки. Считая выигрышем коалиции покупателей величину скидки, которую получит эта коалиция(действующая как единый покупатель), составьте характеристическую функцию этой игры.
Варианты ответа:
12. Приведите характеристическую функцию игры в зад. 11 к 0-1 – редуцированной форме.
Варианты ответа:
13. Для игры зад. 11 составьте систему условий для дележей, принадлежащих ее –ядру. Дайте истолкование в терминах распределения общей прибыли.
14. Для игры зад. 11 найдите ее вектор Шепли. Дайте истолкование в терминах распределения общей прибыли.
Варианты ответа: Ф() = ( 27, 28, 29 );
15. Акции некоторой акционерной компании распределены между четырьмя акционерами, причем акционер 1 обладает 10% всех акций, акционер 2 – 20%, акционер 3 – 30% и акционер 4 – 40%. На общем собрании акционеров решение принимается квалифицированным большинством, т.е. если за него будет подано не менее 2/3 всех голосов(1 акция=одному голосу). С помощью вектора Шепли оцените "силу"держателей акций.
Варианты ответа: Ф= ( 10, 10, 10, 10 );
Ф= ( 12, 12, 12, 12 );
Ф= ( 12, 12, 12, 12 );
Ф= ( 12, 12, 12, 12 );
РЕЗЮМЕ И ЗАКЛЮЧИТЕЛЬНЫЕ
ЗАМЕЧАНИЯ K РАЗДЕЛУ III
I. Игра представляет собой математическую модель совместного принятия решения несколькими сторонами (называемых игроками или лицами), имеющими несовпадающие интересы. Игра общего вида может быть задана в виде следующего набора объектов: =, ( ), ( ), где — множество игроков, — множество стратегий игрока, — функция выигрыша игрока. Полагаем далее = {1,..., }. Если каждый игрок выбрал стратегию, то складывается ситуация = (1,..., ); число () представляет собой оценку полезности ситуации с точки зрения игрока и в теоретико–игровых терминах называется выигрышем игрока в ситуации. Считается, что целью каждого игрока является максимизация своей функции выигрыша. Так как цели игроков различны, игра представляет собой принятие решения в условиях конфликта.II. Игра называется антагонистической, если в ней число игроков равно двум и их интересы прямо противоположны. В случае, когда множества стратегий игроков конечны, антагонистическая игра может быть задана матрицей вида = ( = 1,, = 1, ), называемой матрицей выигрышей или платежной матрицей; такая игра обозначается далее через. В игре с платежной матрицей стратегии игрока 1 отождествляются с номерами строк, стратегии игрока 2 — с номерами столбцов, число рассматривается как выигрыш игрока 1 и одновременно проигрыш игрока 2 в ситуации (, ).
Ситуация (0, 0 ) называется седловой точкой в игре, если при всех = 1,, = 1, выполнено двойное неравенство Седловая точка может рассматриваться как оптимальное совместное решение в игре, где оптимальность ситуации выражается в ее устойчивости: ни один из игроков не заинтересован в одностороннем отклонении от седловой точки, так как при таком отклонении его выигрыш уменьшается. Необходимым и достаточным условием существования в матричной игре седловой точки является наличие у нее цены, то есть выполнение равенства 1 = 2, где 1 = max min, 2 = min max.
К сожалению, не всякая матричная игра имеет цену. Преодоление этого недостатка может быть осуществлено с помощью перехода к смешанным стратегиям, когда каждая чистая стратегия выбирается с некоторой наперед заданной вероятностью. Основным результаттом теории матричных игр является теорема фон Неймана, утверждающая, что всякая матричная игра имеет седловую точку в смешанных стратегиях.
Под решением матричной игры в смешанных стратегиях понимается тройка (0, 0, ), где (0, 0 ) — седловая точка и — цена игры в смешанных стратегиях (при этом стратегия 0 является оптимальной (максиминной) стратегией игрока 1 и 0 — оптимальной (минимаксной) стратегией игрока 2). Аналитическое (формульное) решение существует только для игр формата 2 2. Если один из игроков имеет ровно две стратегии, то решение матричной игры может быть найдено графоаналитическим методом. В общем случае нахождение решения матричной игры может быть сведено к решению пары двойственных задач линейного программирования.
III. Игра общего вида называется бескоалиционной, если в ней запрещено образование коалиций игроков. В бескоалиционных играх основным принципом оптимальности является принцип равновесия (равновесия в смысле Нэша), состоящий в следующем. Ситуация игры называется ситуацией равновесия, если при одностороннем отклонении от нее отклонившийся игрок уменьшает (точнее, не увеличивает) свой выигрыш.
Игра, в которой участвуют два игрока и множества их стратегий конечны, называется биматричной игрой. Такая игра может быть задана парой матриц (, ), где =, = — матрицы одного формата. При этом в ситуации (, ) выигрыш игрока 1 равен и выигрыш игрока 2 равен. Матричную игру можно рассматривать как частный случай биматричной игры, когда =. Принцип равновесия является обобщением принципа седловой точки при переходе от класса матричных игр к более широкому классу биматричных игр.
В классе биматричных игр принцип равновесия реализуется в смешанных стратегиях — это важное утверждение есть теорема Нэша, доказанная им в 1951 г.
Задача нахождения ситуаций равновесия биматричной игры в общем случае является достаточно сложной. Для игр небольших форматов нахождение их ситуаций равновесия основано на так называемом свойстве дополняющей нежесткости, которое позволяет свести нахождение ситуации равновесия с заданной парой спектров к решению двух систем однородных линейных уравнений.
IV. Если в игре общего вида возможно образование коалиций, то ее ситуации равновесия могут не обладать устойчивостью относительно отклонений коалиций игроков. В связи с этим в теории игр рассматриваются различные усиления понятия равновесия, одним из которых является понятие –устойчивости, где — некоторый фиксированный набор коалиций. Содержательно –устойчивость ситуации означает, что в ней реализуется "баланс интересов и возможностей"для всех коалиций. При этом, если состоит из всех 1–элементных коалиций игры, то ее –устойчивость "превращается"в равновесие по Нэшу; если состоит из единственной коалиции всех игроков, то –устойчивость ситуации эквивалентна ее оптимальности по Парето.
Для биматричной игры существует единственная нетривиальная коалиция — коалиция обоих игроков {1, 2}. В такой игре –устойчивость ситуации для = {{1}, {2}, {1, 2}} означает, что эта ситуация является одновременно ситуацией равновесия по Нэшу и оптимальной по Парето.
Однако в биматричной игре может иметься ситуация равновесия по Нэшу, которая не является оптимальной по Парето — это обстоятельство называется противоречием между выгодностью и устойчивостью.
Если руководствоваться только идеей выгодности ситуации для коалиции {1, 2}, то игра теряет свой стратегический аспект и превращается в разновидность задачи 2–критериальной оптимизации, где критериями служат функции выигрыша игроков. В этом случае нахождение оптимального решения биматричной игры сводится к выбору исхода из множества Парето–оптимальных исходов. Нэшем была предложена система аксиом, которая для любой биматричной игры определяет единственный оптимальный исход в множестве ее оптимальных по Парето исходов; это решение носит название арбитражного решения Нэша. Арбитражное решение Нэша может быть реализовано некоторым вероятностным распределением на множестве чистых стратегий коалиции {1, 2}.
V. Кооперативный аспект игры связан с возможностью образования в ней коалиций. Формально коалиция в игре общего вида с множеством игроков определяется как произвольное подмножество. Если допустить для игры возможность образования в ней любых коалиций, возможность выбора членами коалиции любых совместных действий, а также возможность любого распределения суммарного выигрыша коалиции между составляющими ее игроками, то тогда получается, так называемая, классическая кооперативная игра.
Зафиксируем в игре некоторую коалицию. Пусть () — наибольший гарантированный суммарный выигрыш игроков коалиции, который она в состоянии получить в самых неблагоприятных для нее условиях — когда остальные игроки объединяются в коалицию с противоположными интересами. Число () является простой, но весьма важной характеристикой возможностей коалиции в игре. Отображение, которое каждой коалиции ставит в соответствие число (), называется характеристической функцией игры. Основными свойствами характеристической функции являются следующие.
1) () = 0 (персональность);
2) (1 2 ) (1 ) + (2 ) для 1 2 = (супераддитивность).
Всякая функция, определенная на всех подмножествах множества и обладающая свойствами персональности и супераддитивности, называется (абстрактной) характеристической функцией над множеством.
Некоторые задачи теории игр приводят к построению характеристической функции безотносительно игры. Пара,, где — произвольное множество и — характеристическая функция над множеством, называется кооперативной игрой.
VI. Свойство супераддитивности характеристической функции имеет ясный экономический смысл — оно отражает эффект кооперации, состоящий в том, что суммарные возможности коалиции превосходят сумму возможностей составляющих ее членов. В частности, для коалиции всех игроков выполняется () () (случай равенства означает отсутствие кооперативного эффекта и приводит, к так называемой, несущественной кооперативной игре).
Для существенной кооперативной игры положительная величина () () может быть интерпретирована в экономических терминах как дополнительная прибыль, полученная участниками игры за счет их кооперации. При этом возникает важная задача оптимального ("правильного") распределения этой дополнительной прибыли между игроками. В данном курсе рассматриваются два подхода к решению этой задачи: 1–й подход основан на идее устойчивости распределения и формализуется в понятии –ядра; 2–й подход основан на идее справедливости распределения и формализуется в понятии вектора Шепли.
1–й шаг при определении оптимального распределения состоит в формулировке бесспорных требований к такому распределению; эти требования включают в себя индивидуальную рациональность (состоящую в том, что каждый игрок должен получить не меньше того, сколько он может получит самостоятельно), и коллективную рациональность (сводящуюся к оптимальности по Парето). Распределение, удовлетворяющее условиям индивидуальной и коллективной рациональности, называется дележом. Однако для существенной кооперативной игры имеется бесконечное множество дележей (для игры лиц оно может быть отождествлено с симплексом –компонентных вероятностных векторов). Поэтому 2–й шаг при определении оптимального распределения должен состоять в сужении множества дележей (в идеале — до одного дележа). Разные методы осуществляют указанный шаг по–разному.
Сформулируем два принципа выбора дележа — принцип –ядра и принцип Шепли.
VII. Принцип –ядра основан на введении отношения доминирования дележей. Доминирование дележа дележом по коалиции содержательно означает, что, во–первых, для каждого члена коалиции дележ лучше, чем дележ, и, во–вторых, что коалиция может обеспечить дележ своими силами, независимо от действий других игроков.
Предположим, что реализуется (или предлагается к реализации) дележ и вместе с тем дележ доминирует дележ по коалиции. Тогда коалиция, будучи заинтересованной в замене дележа дележом и имеющая возможность обеспечить дележ, выступает в качестве потенциальной угрозы осуществлению дележа. Если мы хотим найти такое распределение, которому не угрожает ни одна коалиция, то мы должны ограничиться недоминируемыми дележами, которые и составляют как–раз –ядро кооперативной игры. В экономических терминах выбор дележа из –ядра можно интерпретировать как "предостережение от экономического сепаратизма".
К сожалению, принцип –ядра обладает рядом недостатков. Основные из них: a) Для некоторых кооперативных игр –ядро оказывается пустым; b) В случае непустоты –ядро содержит, как правило, множество дележей.
«