Теория игр. Оуэн (1971) (1186151), страница 32
Текст из файла (страница 32)
Предположим, что игроки должны выбрать один из этих дележей. Можем ли мы найти какой-нибудь критерий, дающий возможность утверждать, что будет выбран один из этих дележей, а не другойр Ясно, что если х не равен у, то найдутся игроки, предпочитающие х (т. е. 1, для которых х, > у;). Однако найдутся и игроки, предпочитающие у, так как оба вектора являются дележами.
Следовательно, недостаточно установить, что некоторые игроки предпочитают выбор х. С другой стороны, не может быть и так, чтобы все игроки предпочитали х (так как сумма компонент, как 'х, так и у, равна о(й7)). В действительности же необходимо, чтобы сторонники х были достаточно сильны, чтобы заставить остальных выбрать этот дележ. Гм 7!П, Игры л лая 168 ЧП1.3.1.
О п р едел ение. Пусть х и у — два дележа и 5— некоторая коалицию Мы говорим, что х доминирует у по коалиции 5 (обозначается х)ву), если (1) хг)уг для всех (ен 5, (1!) Х х, ~ о(5). г в Мы говорим, что х доминирует у (обозначается х) у), если существует такая произвольная коалиция 5, что х )ву. Таким образом, условие (!) означает, что все члены 5 предпочитают х; условие (й) означает, что они в состоянии получить то, что им положено по дележу х. Как легко видеть, отношение )в (для любого заданного 5) является отношением частичной упорядоченности. С другой стороны, хотя отношение ) и иррефлексивно, оно не является ни транзитнвным, ни антисимметричным (так как коалиция 5 в различных случаях может быть различной). Это — серьезная трудность, и впоследствии она сильно усложнит дело.
Так как мы собираемся анализировать игры при помощи отношения доминирования, мы заинтересованы в том, чтобы выяснить, у каких игр множества дележей имеют одинаковую структуру доминирования. ЧШ.З.2. Определение. Две игры п лиц и н о называются изоморфными, если существует функция ), взаимно однозначно отображающая Е(и) на Е(о) таким образом, что для любых х, у е= Е (и) и 5 с: )Ч х )ау ~!(х) )в) (у).
Пользуясь этим определением, довольно трудно выяснить, являются ли две игры изоморфными. Мы имеем, однако, следующий критерий. ЧШ.З.З. Определение. Две игры я лиц и и о называются 5-эквивалентными, если существуют положительное число г и а таких вещественных чисел аы ..., сс„, что для любой 5с: гЧ о (5) = г и (5) + ~ аь гыя По существу, если две игры 5-эквивалентны, мы можем получить одну из другой посредством линейного преобразования на пространствах полезности нескольких игроков.
Нетрудно доказать, что из 5-эквивалентности следует изоморфизм. ЧП1.3.4. Теорема. Если и и о являются 5-эквивалентными, то они ивоморфны.' ИП. 8. доминирование, нормализации 169 Доказательство. Пусть и и о являются Яэквивалентными. Рассмотрим следующую функцию, определенную на Е(и): ) (х) =тх+а, где т и а =(ап..., а ) те же, что и в НП1.3.3. Легко проверить, что если хеЕ(и), то )(х) енЕ(о). Кроме того, ясно, что если х)ву, то )(х))в)(у). Следовательно, 1 и есть искомый изоморфизм. Итак, Я-эквивалентность достаточна для изоморфизма. Хотя обратное утверждение также верно, но доказательство его гораздо сложнее, и поэтому мы не будем его приводить; см. ста- тью (НП1. 5).
Очевидно, что Е-эквивалентность действительно является отно- шением эквивалентности. Интересно выбрать по одной конкретной игре из каждого класса эквивалентности. НШ.33 Определение. Игра о называется игрой в (0,1)- редуцированной форме, если (!) о((1)) =0 для всех (ен Ф, (П) в (Н) = 1. НП1.3,6. Теорема. Любая существенная игра Б-эквивалент- на одной и только одной игре в (О, 1)-редуцированной форме. Теорема Н1П.3.6, доказательство которой мы опускаем (оно тривиально), показывает, что мы можем выбрать игру в (О, 1)-ре- дуцированной форме для представления любого класса эквива- лентности игр. Удобство этого выбора состоит в том, что в такой форме значение о(Е) непосредственно демонстрирует нам силу коалиции Е (т.
е. ту дополнительную прибыль, которую получают члены коалиции, образовав ее), а все дележи являются вероятно- стными векторами. В литературе об играх л лиц использовались также и иные типы нормализации. Часто встречается редукция к форме ( — 1, 0), при которой о(Я) = — 1, а о(У) = О. Мы же в дальнейшем будем рассматривать игры только в (0,1)-форме. Так как мы интере- суемся исключительно существенными играми, это не повлечет за собой потери общности. Множество игр п лиц в (О, 1)-редуцированной форме совпадает с множеством всех вещественнозначных функций о, заданных на подмножествах множества У и удовлетворяющих следующим тре- бованиям: в(Я) -О, (8.3.1) о((1)) =0 для всех 1е= Ф, (8.3.2) о(Н) = 1, (8.3.3) оФ()Т)~ в(Е)+о(Т), если ЗПТ=В, (8.3.4) Гл.
УИ!. Игры л лич Г70 Эти четыре условия определяют (2" — п — 2)-мерное выпуклое множество. Если игра имеет постоянную сумму, то возникает дополнительное условие: о(М ~ 3) = о(Л/) — о(5) для всех 3 ~ 37. (8.3.5) Это дает 2"-' — 1 дополнительных условий и поэтому множество игр с постоянной суммой имеет размерность 2 -1 — п — 1, Мы видим, что размерность множества игр и лиц с постоянной суммой совпадает с размерностью множества всех игр и — 1 лица. На самом деле, эти два множества конгруэнтны. Действительно, пусть и — игра и — 1 лица в (0,1)-редуцирован. ной форме. Мы можем расширить ее до игры и лиц с постоянной суммой о, добавив нового игрока п и положив: о(3)=и(5), если и ФВ, о(3)=! — и()У~Я), если и~3. Легко проверить„что получившаяся игра является игрой с постоянной суммой.
Отметим два частных типа игр, представляющих известный интерес. ЧП!.3.7. Определение. Игра о называется симметричном, если о(5) зависит только от числа элементов в 5. Ч!П. 38. Определение. Игра о в (О, 1)-редуцированной форме называется простой, если для всех о с: 1У либо о(Я) = О, либо о(3) =!. Игра общего вида называется простой, если проста ее (0,1) -редуцированная форма. В сущности, простая игра характеризуется тем, что в ней коалиция является либо выигрывающей (значение 1), либо проигрывающей (значение 0), без каких-либо промежуточных вариантов. Поэтому простые игры приложены в политических науках поскольку этот класс игр включает игры с «голосованием» вЂ” выборы и законодательные процедуры.
У!И. 4. ЯДРО. НМ-РЕШЕНИЯ Перейдем теперь к изучению игр при помощи отношения доминирования. Естественно, во-первых, исследовать недоминируемые дележи. ЧП1.4.1. Определение. Ядром игры о называется множество всех ее недоминируемых дележей, Ядро игры о обозначается через С(о), !71 ИН. 4. Ядро. НМ-решения ЧШ.4.2.
Теорема. Ядро игры о есть множества всех таких и-векторов х, чтв (а) ~ х, = о(5) для всех 5 с: М, ~шз (б) ~~~ х,= о(М). сшя Доказательство, При 5 = (1) условие (а) превращается в х; ~ о((()). Вместе с условием (б) это означает, что все такие векторы являются дележами.
Предположим теперь, что х удовлетворяет (а) и (б) и что у; ) х; при всех (ен5. В сочетании с (а) это означает, что Х Ь>о(5) (и поэтому у не может доминировать х по коалиции 5). Следовательно, х~С(о). Допустим теперь, что вектор у не удовлетворяет (а) или (б). Если у не удовлетворяет (б), то он даже не является дележом и поэтому не может входить в С(о). Пусть теперь существует такое непустое 5 с: У, что Х у;=о(5) — в, (шз где е > О. Пусть а = о (И) — о (5) — ~ч'„', о (И), ю н,з Как легко видеть, из супераддитивности о следует, что сь ~ О.
Наконец, пусть з — число элементов в 5. Определим г, положив у;+ е/з, если 1ен 5, о ((1)) + а/(и — в), если 1 Ф 5. Легко видеть, что вектор х является дележом и что х р-ву. Следовательно, у 4й С(о). Теорема Ч)П.4.2 показывает, что С(о) представляет собой замкнутое выпуклое множество (как множество решений системы нестрогих линейных неравенств). Это весьма интересно, так как классическая экономическая теория обычно именно ядро считала «решением» большинства теоретико-игровых проблем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
