Содержание к диссертации
Введение
Глава I. Индивидуально рациональные исходы в антагонистических играх с упорядоченными исходами 12
1.1 Антагонистические игры с функциями выигрыша 12
1.2 Антагонистические игры с векторными выигрышами 23
1.3 Структура множества индивидуально рациональных исходов в антагонистических играх с упорядоченными исходами 32
1.4 Непустота и единственность множества индивидуально рациональных исходов в антагонистических играх с упорядоченными исходами 50
Глава II. Игры п лиц с квазиупорядоченными исходами 63
2.1 Условия непустоты множества индивидуально рациональных исходов и множества дележей 63
2.2 Условие единственности индивидуально рационального исхода в играх п лиц с квазиупорядоченными исходыми 76
Глава III. Обратные задачи для кооперативных игр с упорядоченными исходами 86
3.1 Задача восстановления антагонистической игры с упорядоченными исходами по множеству индивидуально рациональных исходов 86
3.2 Задача восстановления игры п лиц с квазиупорядоченными исходами по множеству индивидуально рациональных исходов 94
3.3 Задача восстановления игры с квазиупорядоченными исходами по характеристической функции 100
Список литературы 107
- Структура множества индивидуально рациональных исходов в антагонистических играх с упорядоченными исходами
- Непустота и единственность множества индивидуально рациональных исходов в антагонистических играх с упорядоченными исходами
- Условие единственности индивидуально рационального исхода в играх п лиц с квазиупорядоченными исходыми
- Задача восстановления игры п лиц с квазиупорядоченными исходами по множеству индивидуально рациональных исходов
Введение к работе
Актуальность темы. В теоши игр сложилось два подхода к исследованию игры некоопер. ный и кооперативный. При некооперативном подходе анализ игры проводится в предположении независимости действий игроков. При кооперативном подходе, напротив, предполагается, что игроки могут создавать коалиции, наделенные собственными интересами и возможностями воздействия на появление тех или иных исходов игры. В последние десятилетия значительное внимание исследователей, как в нашей стране, так и за рубежом, было привлечено к играм, в котрых предпочтения игроков задаются не функциями выигрыша (функциями полезности), а их отношениями предпочтения. Это объясняется на наш взгляд двумя обстоятельствами. Во-первых, понятие предпочтения является первичным, в то время как понятие функции полезности -производным Во-вторых, построение функции полезности в практических задачах требует большого объема дополнительной информации и связано с преодолением значительных трудностей как технического, так и принципиального характера Среди ученых, внесших значительный вклад в разработку теории игр с отношениями предпочтения, следует отметить Р.Аумана, Б.Пелега, Э.Й.Вилкаса, О.Н.Бондареву, Т.Е. Кулановскую, В.В.Подиновского, В В.Розена.
Можно выделить следующие направления, активно развивающиеся в последние десятилетия в теории игр с отношениями предпочтения: выработка принципов оптимальности для классов игр с отношениями предпочтения; нахождение условий существования ситуации равновестия как в чистых, так и в смешанных стратегиях; перенос важнейших понятий теории игр с функциями выигрышей игроков на игры с отношениями предпочтения (нижняя и верхняя цена игры, обобщение соотношения максимина, ситуации равновесия, характеристическая функция игры, построение смешенного расширения игры и другие). В то же время вопросы кооперативной теории игр с отношениями предпочтения затронуты лишь в отдельных работах Из сказанного ясно, что разработка кооперативной теории для игр с отношениями предпочтения является весьма актуальной.
Цель диссертационной работы состоит в переносе кооперативных принципов оптимальности, известных для стратегических игр с функциями
выигрыша игроков, на более широкий кл ее стратегических игр с квазиупорядоченными исходами, нахождении достаточных условий существования оптимальных решений и описании их структуры.
Методы исследований. При выполнении работы использовались методы теории игр с функциями выигрыша, теории упорядоченных
множеств, отдельные результаты и методы алгебры множеств и алгебры бинарных отношений.
Научная новизна. Для класса антагонистических игр с квазиупорядоченными исходами введены принципы оптимальности принцип К - равновесия, принцип К - допустимости исходов, принцип К -вполне допустимости ситуаций или исходов игры, где к - произвольное семейство коалиций При сужении на подкласс стратегических игр с функциями выигрыша игроков эти принципы оптимальности переходят в известные принципы оптимальности в классической теории игр При этом, как и в теории игр с функциями выигрыша игроков, оптимальные ситуации всех введенных типов характеризуются тем, что они могут быть стабилизированы с помощью простых угроз
Найдены различные достаточные условия непустоты множества индивидуально рациональных исходов для антагонистических игр с упорядоченными исходами. Найдены достаточные условия непустоты множества индивидуально рациональных исходов и множества дележей для игр с квазиупорядоченными исходами Указаны условия существования единственного индивидуально рационального исхода в антагонистических играх с упорядоченными исходами и играх п лиц с квазиупорядоченными исходами Найдена взаимосвязь между существованием единственного индивидуально рационального исхода в играх п лиц с квазиупорядоченными исходами и существованием ситуации равновесия по Нэшу.
Выяснена структура множества индивидуально рациональных исходов в антагонистических играх с упорядоченными исходами, а также в антагонистических играх с векторными выигрышами.
Рассмотрены обратные задачи для класса стратегических кооперативных игр с квазиупорядоченными исходами. В частности, решена задача восстановления антагонистической игры с упорядоченными исходами и задача восстановления игро! п лиц с квазиупорядоченными исходами по ее оценочной структуре и по множеству индивидуально рациональных исходов. Рассмотрена задача восстановления игры с квазиупорядоченными исходами по ее характеристической функции.
Теоретическая и практическая значимость. Работа носит теоретический характер Полученные в работе результаты могут быть использованы при анализе социально-экономических моделей конфликтов, в которых предпочтения участвующих сторон заданы в порядковых шкалах.
Апробация работы. Основные результаты, изложенные в диссертации, докладывались и обсуждались на научных семинарах Саратовского государственного университета, на ежегодных научных конференциях механико-математического факультета 2001-2004гг., на научных
конференциях факультета КНИТ СГУ, на международной конференции памяти проф. А М Богомолова (Саратов 2002), на обьединенном научном семенаре кафедр факультета компьютерных наук и информационных технологий (руководитель проф Д В Сперанский, на научном семенаре по теории игр Санкт-Петербургского государственного университета (руководитель проф. Л.А. Петросян).
Структура множества индивидуально рациональных исходов в антагонистических играх с упорядоченными исходами
Антагонистическая игра с упорядоченными исходами может быть задана как набор объектов где X - множество стратегий игрока 1, Y - множество стратегий игрока 2,/1-множество исходов, со - отношение порядка, выражающее предпочтения игрока 1 (предпочтения игрока 2 выражаются обратным отношением порядка ft/7), F: X х У — А - функция реализации. В дальнейшем будем считать, что 1 1 2, i 2. Для игры G вида (1.3.1) можно построить двойственную ей игру G , которая получается из G переменой мест игроков 1 и 2 и заменой порядка со на со 1 : G = Y,X,A,o) x,F . При изучении кооперативного аспекта игры должны быть заданы предпочтения ее коалиций. В нашем случае имеется всего три коалиции: {1}, {2}, {1,2}, причем первые две отождествляются с игроками 1 и 2, соответственно. Беря в качестве отношения предпочтения коалиций пересечение отношений предпочтения всех входящих в нее игроков, получаем U JU} = СУ ПСУ"1 = Д , где АА - тождественное бинарное отношение. Отсюда получаем следующее. Утверждение 1.3Л Для коалиции {1,2} все исходы являются допустимыми. Действительно, никакие два различных исхода не сравнимы по отношению предпочтения коалиции {1,2}. Отсюда следует Утверждение 1.3.2 Для любой антагонистической игры G с упорядоченными исходами следующие три множества исходов: 1) множества индивидуально рациональных исходов D(G); 3) а-ядро Ca(G) Действительно, выполняется очевидное включение; Для доказательства утверждения 1.3.2 достаточно показать, что /)(G)cCff(C), Пусть а є D{G), то есть исход а допустим и для игрока 1, и для игрока 2. Так как в антагонистической игре G для коалиции {1,2} по утверждению 1.3.1 любой исход является допустимым, то, учитывая, что {1},{2},{1,2} исчерпывают все коалиции игры, получаем, что исход а является допустимым для всех коалиций игры (7, то есть а є Cdfi). 1.3.2 Для анализа антагонистической игры с упорядоченными исходами вводятся характеристические множества . В соответствии с определением 1, в антагонистической игре вида (1.3.1) исход а является гарантированным исходом игрока 1, если существует такая стратегия хеХ , что выполняется (Уу є Y)F(x,y) a,
Если последнее неравенство заменить на строгое, то получится строго гарантированный исход. Множество есть множество гарантированных исходов игрока 1, а множество есть множество строго гарантированных исходов игрока- 1. Множество Z)[ (G) = (JJ{ (Є)У представляет собой множество исходов, допустимых для игрока 1. Исход а является нгзапрещенпым исходом игрока 1, если для любой х стратегии у є Y найдется такая стратегия хеХ, что выполняется F(x, у) а. Множеством незапрещенных исходов игрока 1 является множество множество строго незапрещенных исходов игрока 1, есть (О Множества /, (G), /, (G), Vx(G)t Vx (G) называются характеристическими множествами игрока 1. Для игрока 2 его характеристические множества определяются двойственным образом: множество гарантированных исходов игрока 2. множество строго гарантированных исходов игрока 2. множество незапрещенных исходов игрока 2 . V2\G) = {д є Л : (VJC є X) (Зу є Г) F( ,y) a} -множество строго незапрещенных исходов игрока 2 . Утверждение 1.3.3 Для любой антагонистической игры с упорядоченными исходами справедливы следующие включения: Доказательство следует из определений. Множество D(G) индивидуально рациональных исходов антагонистической игры с упорядоченными исходами задается равенством. 1.3.3 Нахождения характеристических множеств с помощью расширенной таблицы функции реализации. Для задания конечной антагонистической игры G с упорядоченными исходами необходимо задать: 1) множество X = {xlt...,xn} стратегий игрока 1; 2) множество Y = {ylt...,yw} стратегий игрока 2; 3) функция реализации F может быть задана с помощью таблицы вида (1.3.1), в которой номера строк соответствуют стратегиям игрока 1, а номера столбцов стратегиям игрока 2; 4) отношение порядка со может быть задано диаграммой упорядоченного множества (А,СО). Для конечной игры с упорядоченными исходами характеристические множества U k(G), Uk(G), Vk(G), Vk(G), =1,2 удобно находить с помощью построения расширенной таблицы функции реализации, которая получается путем добавления одной строки и одного столбца к таблице функции реализации следующим образом. Для нахождения характеристических множеств строится расширенная таблица, которая получается из таблицы функции реализации путем добавления к ней столбца Ul ={и\ {\),...,и1(п))т и строки С?1 =(U 2(\),...,U 2(m)), где множества С/, (г) (і - \,п) определяются условиями: Таким образом, aeUx(i) тогда и только тогда, когда элемент а строго меньше (относительно порядка со) любого элемента, стоящего в і-й строке таблицы функции реализации. Аналогично находятся характеристические множества Ux (С?) и U2 (G) (строгие неравенства в формулах (1.3.3) и (1.3.4) заменяются на нестрогие). При нахождении характеристических множеств Vx ((7) и V2(G) расширенная таблица получается из таблицы функции реализации добавлением строки Vx = (УХ (1),...,1 (т)) и столбца V2 = (V2 (1),..., V2 (л)) , где множества i (Л (у = l,w) определяются следующим образом: Таким образом, й є Vx (у) тогда и только тогда, когда элемент а меньше или равен относительно порядка со хотя бы одного элемента у-го столбца функции реализации. Двойственным образом определяются множества V2 (О :
Непустота и единственность множества индивидуально рациональных исходов в антагонистических играх с упорядоченными исходами
Теорема 1.4,1. Пусть в антагонистической игре G= X,YtA,a),F с упорядоченными исходами все цепи упорядоченного множества А,со конечны. Тогда множество индивидуально рациональных исходов в игре G непусто: В{С)Ф0 Доказательство. 1-й случай: Так как в упорядоченном множестве А, о все цепи конечны, то в нем выполнено как условие обрыва возрастающих цепей (ОВЦ), так и условие обрыва убывающих цепей (ОУЦ), поэтому каждое непустое подмножество множества А имеет как максимальный, так и минимальный элементы. Пусть а -максимальный элемент подмножества UliCj), b -минимальный элемент подмножества tA((7). Так как a EU (G)7 то найдется стратегия .Я, єА", , при которой Так как Ъ Єlf2(G)y то найдется стратегия ух Є Y t при которой Полагая в соотношении (1.4.1) у=у\ и в соотношении (1.4.2) х=Х\, получаем a F(x]1yi) b . Так как F{x\tyi) а и а - максимальный элемент в U[(G), то ад) tf(G), то есть F(xlfy,)e (Ul(G)y =A(G). Так как Ffc.y,) b\b -минимальный элемент в Ц(С), то F( yx) U2{G), то есть F(xl,y]) d(G)y = ACQ- Следовательно, Таким образом D{G) Ф 0. J-и случаи: этом случае для игрока 2 все исходы будут допустимыми, то есть D2(G) = A, откуда Так как U[{G)&Q3 и в упорядоченном множестве А,со все цепи конечны, то в подмножестве U[(G) существует максимальный элемент а1. Ввиду того, что d Є U[((7), существует такая стратегия х2 є/, при которой (Vy =F) F(x2,y ) а\ Зафиксируем произвольно УеУ; имеем Дх2,У) д\ Так как элемент а1 максимальный в подмножестве U[(G), то из последнего соотношения следует, что F{x2,У) U (G), то есть откуда 4-м случаи. В этом случае любой исход игры является допустимым для обоих игроков, так как Теорема 1.4.2 В антагонистической игре G= X,Y,A, со, F с упорядоченными исходами, в которой миооїсества стратегий игроков конечны, множ-естно индивидуально рациональных исходов непусто. Для доказательства теоремы введем следующее определение. Определение 1.4.1.
Игра с упорядоченными исходами G = Х, У, А со F называется порядковым расширением игры с упорядоченными исходами G= X, У, А, со, F , если существует такое отображение Р А — A t что: а) p является изоморфным вложением упорядоченного множества А,(о в упорядоченное множество АуО) Б) F pF. Доказательство леммы 1.4.1. Если D(G) 0t то в игре G существует исход о. є А, допустимый для обоих игроков. Покажем, что исход р(о) допустим для обоих игроков в игре G. Предположим, что (р(р) недопустим для игрока 1 в игре G, то есть Учитывая, что по условию в) F\X ,у) = р F{xty) из соотношения (1.4.3) получаем Учитывая, что изоморфное вложение р удовлетворяет при любых а (і2єА условию: flj я2 Ф 0) ФІ ), из (1 -4.4) получаем Соотношение (1.4.5) означает, что исход а является недопустимым для игрока 1 в игре G в противоречие с предположением. Итак, исход (pifl) будет допустимым для игрока 1 в игре G. Аналогично, исход р{а) будет допустимым для игрока 2 в игре G. Следовательно (p(a)eD(G)t откуда D(G) 0, что и доказывает лемму 1 .4. 1. Доказательство теоремы 1,4.2. Положим С? = Х, Y, А, (о\ F где A =pr2F = {F(x,y):x:X)y&Y} множество значений функции Ft of -индуцированное отношение порядка на А0. Так как множества X и Y по условию теоремы 1.4.2 конечны, то множество pr2F также будет конечным. Таким образом, в игре G множество исходов конечно, поэтому для игры G0 выполнены условия теоремы 1.4.1. По теореме 1.4.1 О(С?)ф0. Далее, игра G0 является порядковым расширением игры G (в качестве (р надо взять тождественное отображение р,гр : — Л) по лемме 1.4.1 получаем D(G) 0t что и доказывает теорему 1.4.2 . 1.4.2 Условие единственности индивидуально рационального исхода в антагонистических играх с упорядоченными исходами Если в антагонистической игре с упорядоченными исходами множество исходов является конечной цепью, то справедливо следующее утверждение. Утверждение 1.4.1 В случае, когда (А,со)- конечная цепь, условия единственности индивидуально рационального исхода и существования седловой точки эквивалентны между собой. Действительно, по следствию 2 теоремы 1.1.2 (учитывая, что конечную п элементную цепь можно перенумировать числами 1,...,п так, что игра превращается в матричную игру). Однако во всем классе игр с упорядоченными исходами эти условия независимы, как показывают следующие примеры. Пример 1.4,1 Рассмотрим антагонистическую игру с функцией выигрыша h\ заданную таблицей 1.4.1.
Условие единственности индивидуально рационального исхода в играх п лиц с квазиупорядоченными исходыми
Для таких игр находится условие единственности индивидуально рационального исхода. Вначале введем несколько определений. полагаем г{х \ xi) — {хх,..,х ,х.,хм,хп)). естественной эквивалентностью игры G. Далее дается характеризация игр с квазиупорядоченными исходами, имеющих единственный индивидуально рациональный исход с точностью до естественной эквивалентности. Теорема 2.2.1 Пусть G игра с квазиупорядоченными исходами вида (2.2.1), в которой каждое квазиупорядоченное множество AyCOi удовлетворят условию обрыва возрастающих цепей (ОВЦ). Для того, чтобы исход С Є А был единственным с точностью до эквивалентности є индивидуалыю рациональным исходом в игре G, необходимо и достаточно чтобы выполнячись следующие условия: 3) для любого исхода а є А, не эквивалентного относительно є исходу с , найдется такой индекс IGN, для которого а с . Доказательство. Необходимость. 1) Зафиксируем І є N. Пусть я є Uf (G). В силу условия ОВЦ для квазиупоря ценного множества А,0)( элемент а мажорируется некоторым максимальным элементом а подмножества V. (G), то а есть a ajt где cii eMAXU G). Зафиксируем для тех j i, для которых максимальные элементы а, а для остальных игроков І є N зафиксируем стратегии Xj є X j. Так как при всех k Q S = {i Q N .Uj (G) Ф 0} имеет место йк є Uк (G)t то по определению множества строго гарантированных исходов для любого к є N найдется такая стратегия Xj е X\, что в произвольной ситуации хє X выполняется щ F(x xk) ак Таким образом, в ситуации X єдг соотношение выполняется для всех к є S. Так как ak - максимальный элемент подмножества U\{G) (keS), из (2.2.2) следует, что для всех keS имеет место F(x)Uk(G)y то есть F(x)eDk(G). Так как для всех IGN\S справедливо U, (G) = 0, то для игроков 1 =N\S исход F(x ) является допустимым, откуда f(x ) є f) Dt (G) = Z) (G). По условию единственности индивидуально рационального исхода получаем F{x ) с и согласно (2.2.2) имеем при к = І : откуда а с . 2) Включение слева направо выполняется в силу 1). Обратно, пусть исход а а принадлежит правой части доказываемого равенства, то есть а с для некоторого / є N. Предположим, что о. \JU (G). Тогда « є (\JU (G)y= D(G) и По условию единственности индивидуально рационального исхода я с , откуда а с , что несовместимо с условием а с . 3) Пусть исхода а є Л не эквивалентен относительно исходу с .
Тогда по условию единственности индивидуально рационального исхода имеем а & D(G), то есть исход а недопустим для одного из игроков: я є V . (G) при некотором щ і є N .В силу условия 1) получаем а с . t Достаточность. Пусть в игре G вида (2.2.1) для исхода с Є А выполнены условия I), 2), 3). Предположим, что исход с не является допустимым для игрока і Є N. Тогда с є U{ (С?) и согласно 1) получаем с с , что невозможно. Итак, исход с допустим для всех игроков, то есть с Є D(G). Возьмем любой исход а D(G) . Предположим, что исхода а є А не эквивалентен относительно є исходу с . Тогда согласно 3) для некоторого ieN будет а с и по условию 2) а є V -(G) для некоторого j є N ,то есть исход о недопустим для игрока у. Это противоречит тому, что а є D{G) ,что и завершает доказательство теоремы 2.2.1. Следующий результат устанавливает связь между условием единственности индивидуально рационального исхода и равновесием по Нэшу специального типа. Установим вначале одно вспомогательное утверждение. Лемма 2.2.1 Пусть х є X - ситуация равновесия по Нэшу в игре G. ТогОа для любого і є N справедливо включение: Доказательство. Пусть сі є /. (G) , Тогда существует такая стратегия х , при которой в любой ситуации х є X выполняется F{x хі) аі в частности F(x Х:) а . Так как х - ситуация равновесием по Нэшу, то F{x х. ) F(x ). Из последних двух соотношений получаем F(x ) а, что доказывает лемму 2.2.1 Следствие Исход в ситуации равновесия по Нэшу является индивидуально рациональным. В силу леммы 2.2.1 для любой ситуации равновесия по Нэшу х выполнено включение: Определение 2.2.4 Ситуацию равновесия по Нэшу назовем специальной, если для нее в (2.2.4) выполнено равенство. Замечание 2.2.1 В антагонистической игре с упорядоченными исходами всякая ситуация равновесия по Нэшу (то есть седловая точка) является специаіьной. Действительно, так как в антагонистической игре ситуация равновесия по Нэшу (х0,У0) есть седловая точка, то по лемме 1.4.2 Откуда то есть по определению 2.2.4 ситуация (x0,y0) является специальной ситуацией равновесия по Нэшу. Теорема 2.2.2 Для того, чтобы игра G вида 2.2.1, в которой множество исходов А конечно, имела единственный с точностью до эквивалентности є индивидуально рациональный исход, необходимо и достаточно, чтобы н ней существовача специальная ситуация равновесия по Нэшу х , для которой выполняется следующее дополнительное условие: для любого исхода а не эквивалентного по є исходу F{x ) найдется такой игрок і є N, для которого Доказательство.
Пусть с - единственный с точностью до эквивалентности к индивидуально рациональный исход. Для игроков ІЄ S CL Nу для которых и.1{С)Ф0, зафиксируем U; eMAXU G) и пусть X. - стратегия игрока /, строго гарантирующая ему исход а{ {і є N) . Для остальных игроков j є N\S , для которых CJj(G) = 0, зафиксируем /Ї- недоминируемые стратегии Xj (они существуют в силу конечности множества А). Как показано в доказательстве теоремы 6.1, исход в ситуации х = (Х; )ieN является индивидуально рациональны м и по условию единственности F{x ) С . Возьмем Xj єХ;. Исход в ситуации xf будет допустимым для всех исходов jФІ. Может быть 2 случая. 1) Исход в ситуации X Xs является допустимым для игрока (. Тогда є F(x Xj)& D(G) и по условию единственности F(x х.) с , откуда F(xI X;)-F(x), следовательно, F(x x, ) F(x). 2) Исход в ситуации X Xt не допустим для игрока /. Тогда t (0 F(x\ Xj) є U i (G), и по условию 1) теоремы 2.2.1 получаем F(x xi) c . Е Єі Ввиду того, что с F(x ), при любом ieN выполняется с F(x ), откуда F(x xi ) F(x). Итак, в любом случае будет F(x \х{ ) F(x), то есть X - ситуация равновесия по Нэшу. Так как F(x ) с , то согласно теореме 2.2.1 будут выполнены условия З ) для любого исхода а не эквивалентного по є исходу F(x ) найдется щ о такой игрок / Є JV , что a F(x ), откуда получаем доказательство необходимости. Обратно, пусть х - специальная ситуация равновесия по Нэшу, для которой выполнено (2.2.5). Тогда для с = F(x ) выполняются все условия теоремы 2.2.1, откуда с - единственный индивидуально рациональный исход, что и требовалось доказать. Замечание 2.2.2 Теоремы 2.2.1 и 2.2.2 дают также решение вопроса о существовании единственного дележа в играх с квазиупорядоченными исходами благодаря следующему утверждению Утверждение 2.2.1 Пусть G игра с квазиупорядоченными исходами вида (2.2.1). 1. Если а единственный с точностью до естественной эквивалентности к индивидуально рациональный исход, тогда а будет и единственным с точностью до эквивалентности є дележом. 2. Если а - единственный с точностью до эквивалентности є делезіс в игре G, в которой квазиупорядоченные множества /1,; (/ е Л ) удовлетворяют условию ОВЦ, то а будет также единственным с точностью до эквивалентности є индивидуально рациональным исходом. Доказательство. 1) Пусть а - единственный с точностью до эквивалентности є индивидуально рациональный исход. Покажем, что а будет также дележом. Предположим противное, то есть, что исход а является недопустимым для коалиции N. Это означает, что существует такая ситуация х є XNy в которой
Задача восстановления игры п лиц с квазиупорядоченными исходами по множеству индивидуально рациональных исходов
Указанная в заголовке задача формулируется в следующем виде. Задача 3.2Л Пусть А - множество на котором заданы отношения квазипорядка й р(У2,..,& „ и выделено подмножество Z)c , Найти необходимые и достаточные условия при которых D совпадает с множеством индивидуально рациональных исходов в некоторой стратегической игре G с квазиупорядоченными исходами вида Для решения поставленной задачи будем использовать следующие обозначения. Для произвольного подмножества В с А любого элемента й є А полагаем; МАХ.В -множество максиммальных элементов подмножества В относительно квазиорядка (О. {і Є N) . МШ}В- множество минимальных элементов \подмножества В относительно квазипорядка о?і (і N). М- (й) = {а1 є А : а% а) -множество строгих мажорант элемента а относительно квазипорядка (Ot (і є N) Ulj mXa) — 1я е : (1 о)- множество строгих минорант элемента а, относительно квазипорядка со, (ieN). Задача 3.2.1 решена здесь для случая конечного множества А, и ее решение сформулировано в следующей теореме. Теорема 3.2.1. Пусть А- конечное множество па котором заданы отношения квазипорядка Wl,d)2,..,COn и зафиксировано некоторое подмно), а е А , и выполнено включение Mfa) с Л/Дя1). Покажем, что « et/f(G). В самом деле, принадлежность й є (/,. (G) означает существование такой стратегии Х{ є Л",., для которой По предположению поэтому из F(X; І у) а следует щ F(%i У) а- Таким образом, выполняется Отсюда х{ - возражение игрока / на исход а , то есть я є Vi (G) = Ct, Достаточность. 1-й случай, Сь...,Ся 0. Построим игру G с квазиупорядоченными исходами вида (3.2,1), в которой С, = Ux {G),...,Clt = Un (G). Для построения G надо задать: А) множества стратегий игроков Xf (І є N); Так как подмножества Сх,...,Сп по предположению непусты, то множества их максимальных элементов относительно соответствующих квазипорядков также непусты. Полагаем для любого і є N причем первые rnj элементов множества Xt будут находится во взаимно однозначном соответствии с элементами elv..,rtm_. Функцию реализации F определим следующими правилами. (1). Если игрок / выбирает стратегию из подмножества {Яр "» ,,.}, а каждый игрок / є N\i выбирает свою стратегию из подмножества ІУтм -- У,п1+ )»то (2),Если каждый игрок ieN выбирает свою стратегию из подмножества стратегий {у тІЛ " У ті К т0 исходы в образуемых ситуациях должны являться минимальными элементами множества А относительно одного из порядков »i,...,u)n; при этом должно выполняться следующее дополнительное условие: для любой стратегии Ук. (/я; +1 к. т. + р) игрока / Є N существуют стратегии у\, (/ є N \ і) жество D Z.A. Для того, что бы подмножество D совпадаю с множеством индивидуально рациональных исходов в некоторой игре G вида (3.2.1) необходимо и достаточно, чтобы его дополнение D =A\D допускало представление в виде объединения п подмножеств С1У..,Сп, удовлетворяющих следующим условиям. 2)
Пусть прн некотором і Є N выполняется а є U, (G), а е А , и выполнено включение Mfa) с Л/Дя1). Покажем, что « et/f(G). В самом деле, принадлежность й є (/,. (G) означает существование такой стратегии Х{ є Л",., для которой По предположению поэтому из F(X; І у) а следует щ F(%i У) а- Таким образом, выполняется Отсюда х{ - возражение игрока / на исход а , то есть я є Vi (G) = Ct, Достаточность. 1-й случай, Сь...,Ся 0. Построим игру G с квазиупорядоченными исходами вида (3.2,1), в которой С, = Ux {G),...,Clt = Un (G). Для построения G надо задать: А) множества стратегий игроков Xf (І є N); Так как подмножества Сх,...,Сп по предположению непусты, то множества их максимальных элементов относительно соответствующих квазипорядков также непусты. Полагаем для любого і є N причем первые rnj элементов множества Xt будут находится во взаимно однозначном соответствии с элементами elv..,rtm_. Функцию реализации F определим следующими правилами. (1). Если игрок / выбирает стратегию из подмножества {Яр "» ,,.}, а каждый игрок / є N\i выбирает свою стратегию из подмножества ІУтм -- У,п1+ )»то (2),Если каждый игрок ieN выбирает свою стратегию из подмножества стратегий {у тІЛ " У ті К т0 исходы в образуемых ситуациях должны являться минимальными элементами множества А относительно одного из порядков »i,...,u)n; при этом должно выполняться следующее дополнительное условие: для любой стратегии Ук. (/я; +1 к. т. + р) игрока / Є N существуют стратегии у\, (/ є N \ і) остальных игроков, такие, что (3). Во всех остальных ситуациях значения функции реализации выбираются из множества которое непусто по условию 1) теоремы. Итак, построена игра с квазиупорядоченными исходами вида (3.2,1), функция реализации F которой определена правилам (1)-(3) построения функции реализации,
