САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Прикладная математика и информатика
Исследование операций и принятие решений в задачах оптимизации, управления и
экономики
Грецова Мария Вадимовна
Модели формирования коалиций
Бакалаврская работа
Научный руководитель:
канд.физ.-мат. наук Наумова Н.И.
Рецензент:
канд.физ.-мат. наук Бухвалова В.В.
Санкт-Петербург
2016
SAINT-PETERSBURG STATE UNIVERSITY
Applied Mathematics and Computer Science
Operation Research and Decision Making in Optimisation, Control and Economics
Problems
Gretcova Mariia
Models of forming coalitions
Bachelor’s Thesis
Scientific supervisor:
ass. prof. Natalia Naumova
Reviewer:
ass. prof. Vera Bukhvalova
Saint-Petersburg
2016
Оглавление
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.
Основные определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.1.
Определение гедонистической игры . . . . . . . . . . . . . . . . . . . .
4
1.2.
Cвойства решений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.3.
Концепции решения основанная на групповом отклонении . . . . . .
6
1.4.
Концепции решений основанные на одиночном отклонении игроков
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.
Задача «об устойчивом браке» . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.
Аддитивно-сепарабельные гедонистические игры . . . . . . . . . . . . . . . . 14
4.
Игры с общим порядком предпочтений . . . . . . . . . . . . . . . . . . . . . . 17
5.
B,W и T OP–игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.1.
Определение B и W–игр . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2.
T OP–игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.3.
Алгоритм «Top covering» . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Приложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1
Введение
Теория игр – это математическая дисциплина, в которой изучаются ситуации столкновения интересов, их свойства и особенности, и разрабатываются методы оптимального в
том или ином смысле поведения игроков в таких ситуациях. Кооперативной называется
игра, в которой группы игроков – коалиции – могут объединять свои усилия.
Люди часто объединяются в группы из соображений личной выгоды. Например,
когда они организуют фирму с целью производства каких-то товаров, или клуб по интересам. В таких ситуациях каждый индивид имеет личные предпочтения относительно того, какой группе он хочет принадлежать. Обычно его интересует размер группы,
другие входящие в нее индивиды и то чем группа занимается. Подобные ситуации неоднократно анализировались в рамках теории кооперативных игр.
В 1962 году Дэвид Гейл и Ллойд Шепли сформулировали задачу распределения студентов по колледжам [8]. Она заключается в том, чтобы каждого студента из заданного
множества определить в один из нескольких колледжей, если известны предпочтения
студентов среди колледжей и колледжей среди студентов с учетом того, что каждый
колледж может принять ограниченное число абитуриентов и каждый абитуриент может попасть только в один колледж. При рассмотрении этой задачи Гейл и Шепли
ввели понятия устойчивого и неустойчивого разбиения, а также рассмотрели задачу
«об устойчивом браке».
Игры, в которых задача каждого игрока – попасть в наиболее приятную для себя
коалицию, называются гедонистическими [7]. Они были определены в самостоятельный
класс игр Жаком Дзеном и Джозефом Гринбергом в 1980 году. Такое название было выбрано не случайно. Гедонизм(греч. hedone–наслаждение) – это этико-психологическое
учение, возникшее в античности, утверждающее, что наслаждение является высшим
благом, целью личности, критерием истинности и целесообразности, основным мотивом ее поведения [20].
За последние 30 лет гедонистические игры стали объектом изучения многих ученых. Наиболее практически-значимые результаты были получены в работах Элвина
Рота, сумевшего связать задачу о поиске устойчивого паросочетания с теорией коалиционных игр. В США при его участии были изменены многие общественные механизмы
распределения, в том числе механизмы распределения интернов по больницам, система распределения учащихся по школам округов Нью-Йорк и Бостон. Помимо этого,
Э.Рот совместно с Тайфуном Сомезом построили научный фундамент системы обмена
2
донорскими органами. В 2012 году Ллойд Шепли и Элвин Рот были удостоены Нобелевской премии по экономике «за теорию устойчивого распределения и практики дизайна
рынка».
Целью данной работы является изучение принципов устойчивости для коалиционных структур в гедонистических играх с использованием практических примеров. На
сегодняшний день, не существует материалов на русском языке по теории гедонистических игр. В качестве основы для исследования была взята обзорная работа [2].
В первой главе приведены основные понятия, связанные с гедонистическими играми,
и разобраны поясняющие примеры.
Вторая глава посвящена задаче «об устойчивом браке» [8], поставленной Гейлом и
Шепли в 1962 году – приведена ее формулировка, а также алгоритм решения и практические примеры реализации этого алгоритма.
Далее рассмотрены игры с различными принципами формирования предпочтений.
В третьей главе рассказывается о гедонистических играх с аддитивно-сепарабельными
предпочтениями. Для симметричной аддитивно-сепарабельной игры объясняется способ нахождения устойчивого по Нэшу решения, приведенный в работе Анны Богомольной и Мэттью Джексона [4], приводятся примеры нахождения таких решений.
В четвертой главе разобран алгоритм нахождения решения из ядра, для игр с общим
порядком предпочтений, созданный Варутом Саксомпонгом [14].
Пятая глава рассказывает о B, W и T OP–играх. Помимо основных определений,
взятых из [2], в ней выводится взаимосвязь между этими видами игр. Приводится алгоритм «Тop covering», который находит разбиения из ядра для T OP–игр [1], а также
доказательство его корректности [5].
Алгоритм «Тop covering» был реализован на языке C#. Текст программы приведен
в приложении.
3
1.
Основные определения
1.1.
Определение гедонистической игры
Определение 1.1. Пусть N – множество игроков.
Коалицией называется непустое подмножество N.
Пусть Ni ={S ⊆ N ∶ i ∈ S} – множество всех коалиций, в которых содержится i ∈ N .
Коалиционной структурой называется разбиение множества игроков N на непересекающиеся коалиции.
Отношением предпочтения (или предпочтением) ≿i игрока i на множестве
Ni называется полное, транзитивное бинарное отношение, заданное на Ni .
Гедонистической игрой формирования коалиций называется
пара (N, ≿), где ≿= (≿1 , ... ≿∣N ∣ ) – набор предпочтений всех игроков.
Решением гедонистической игры будем называть коалиционную структуру, удовлетворяющую определенным свойствам.
Пусть S, T ∈ Ni
S ≻i T означает, что для игрока i строго предпочтительнее S, чем T ;
S ∼i T означает, что для игрока i коалиции S и T одинаково предпочтительны;
S ≿i T означает, что для игрока i коалиция S нестрого предпочтительнее T , т.е.
возможны оба вышеперечисленные варианта;
Для коалиционной структуры π и игрока i, π(i) – коалиция из π, которая содержит
i.
Пример 1.1. В гедонистической игре участвует три игрока 1, 2, и 3, их предпочтения среди коалиций, перечислены ниже.
Все игроки предпочитают коалицию из двух человек, а не из одного или трех.
Для каждого игрока предпочтительнее состоять в коалиции одному, чем втроем.
Для игрока 1 предпочтительнее быть с 2, чем с 3
Для игрока 2 предпочтительнее быть с 3, чем с 1
Для игрока 3 предпочтительнее быть с 1, чем с 2
Результатами игры могут быть разбиения всех игроков на коалиции:
{123},{12}{3},{13}{2},{23}{1} и {1}{2}{3}.
Игрок может покинуть коалицию, чтобы присоединиться к другой коалиции или,
чтобы играть самостоятельно. Это явление называют одиночным отклонением иг4
рока. Говорят, что у игрока есть причины для одиночного отклонения, если существует
коалиция, которая для него строго предпочтительнее текущей. Такое одиночное отклонение называют предпочтительным. Какие-то одиночные отклонения могут быть
запрещены и называться запрещенными. Не запрещенные одиночные отклонения называют разрешенными.
Определение 1.2. Коалиционная структура π называется устойчивой относительно класса разрешенных одиночных отклонений, если ни один из игроков не имеет
предпочтительного разрешенного одиночного отклонения.
Допустим, что в Примере 1.1. разрешены любые одиночные отклонения. Очевидно,
что если коалиция не двухточечная, то её игроки имеют причины для отклонения. Получается, что все коалиционные структуры содержат хотя бы одного игрока, имеющего
причины для отклонения, то есть не являются устойчивыми.
При сокращении класса разрешенных одиночных отклонений устойчивость коалиционной структуры слабеет, т.е. если в результате запрета некоторых отклонений какая-то
коалиционная структура стала устойчивой, то ее устойчивость считается слабее устойчивости тех коалиционных структур, которые уже были устойчивы до запрета.
Допустим, что в Примере 1.1 игрокам запрещено выходить из коалиции без разрешения(одобрения) всех её участников. Тогда все разбиения, содержащие двухточечные
коалиции будут устойчивы, так как оставшемуся в одиночестве игроку из двухточечной коалиции хуже быть одному, чем вдвоем, и он запретит отклонение второго. При
одноэлементном разбиении любое отклонение разрешено, потому что оно приводит к
разбиению на одно и двухточечные коалиции. Получается, что одноэлементное разбиение является неустойчивым. Если же разбиение состоит из одноточечных множеств,
то разрешено любое одиночное отклонение, и все игроки хотят создать двухточечную
коалицию, поэтому это разбиение тоже является неустойчивым.
В игре могут быть запрещены некоторые разбиения. В этом случае, решение выбирается из класса разрешенных разбиений.
1.2.
Cвойства решений
1)Индивидуальная рациональность.
Определение 1.3. Разбиение π является индивидуально рациональным (ИР),
если для каждого игрока i ∈ N коалиция π(i) не менее предпочтительна, чем коалиция
{i}, т.е. ∀i ∈ N, π(i) ≿i {i}.
5
Индивидуальная рациональность весьма слабое свойство. Оно включается во многие
концепции решения, потому что является необходимым условием устойчивости.
В Примере 1.1 все разбиения, кроме {123}, являются индивидуально рациональными.
2)Совершенность
Определение 1.4. Разбиение π является совершенным, если каждый из игроков
i ∈ N находится в одной из своих наиболее предпочтительных коалиций.
Совершенное разбиение устойчиво по отношению к любому отклонению, но существует редко.
В Примере 1.1 для каждого из игроков множество наиболее предпочтительных игроков
одноточечно: {12},{23} и {31} для 1,2 и 3 - соответственно. Объединение этих коалиций
не является разбиением, поэтому для этой игры нет совершенного разбиения.
3)Оптимальность по Парето
Определение 1.5. Разбиение π оптимально по Парето (ПО), если не существует разбиения π ′ , такого, что π ′ (j) ≿j π(j) для каждого j и π ′ (i) ≻i π(i) хотя бы для
одного i.
(Т.е. не существует разбиения которое было бы не хуже для всех игроков и лучше
хотя бы для одного.)
В Примере 1.1 разбиение π = {12}{3} является Парето-оптимальным.
Действительно,
если π ′ = {13}{2}, то {13} ≿̸1 {12};
если π ′ = {23}{1}, то {1} ≿̸3 {12};
если π ′ = {123}, то {123} ≿̸1 {12}.
По-аналогии, Парето-оптимальными являются решения {13}{2} и {23}{1}.
В литературе свойство оптимальности по Парето иногда называют свойством групповой
стабильности.
1.3.
Концепции решения основанная на групповом отклонении
Определение 1.6. Сильно блокирующей коалицией называется S ⊆ N, S ≠ ∅
такое, что ∀i ∈ S ∶ S ≻i π(i).
Разбиение π находится в слабом ядре, если дня него не существует сильно блокирующей коалиции, т.е. ∀S ∶ S ⊆ N, S ≠ ∅∃i ∈ S ∶ π(i) ≿i S.
6
То есть коалиция S сильно блокирует разбиение π, если для каждого игрока i ∈ S
коалиция S строго предпочтительнее его текущей коалиции π(i) в разбиении π, а разбиение находится в ядре, если для него нет сильно блокирующей коалиции. В дальнейшем,
слабое ядро будем называть просто ядром.
Примере 1.1 не существует разбиения с сильным ядром. Каждая двухточечная коалиция является наиболее предпочтительной только для одного из ее участников, поэтому
коалиция, более предпочтительная для второго будет блокировать двухэлементное разбиение, содержащее вышеназванную коалицию. Любая двухточечная коалиция сильно
блокирует одноэлементное разбиение и разбиение, состоящее из одноточечных коалиций.
Определение 1.7. Говорят, что коалиция S ⊆ N слабо блокирует разбиение π,
если для каждого игрока i ∈ S коалиция S слабо предпочтительнее его текущей коалиции π(i) в разбиении π, и существует хотя бы один игрок j ∈ S для которого коалиция
S строго предпочтительнее π(j), т.е. ∀i ∈ S ∶ S ≿i π(i), ∃j ∈ S ∶ S ≻j π(j).
Разбиение π находится в сильном ядре, если для него не существует слабо блокирующей коалиции, т.е. ∀S ∶ S ⊆ N, S ≠ ∅∃j ∈ S ∶ π(j) ≻j S.
Замечание 1.1. Каждая сильно блокирующая коалиция является слабо блокирующей,
а каждая коалиция из сильного ядра содержится в слабом.
1.4.
Концепции решений основанные на одиночном отклонении
игроков
Разбиение π устойчиво по Нэшу , когда ∀i ∈ N
π(i) ≿i S ∪ {i} ∀S ∈ π ∪ {∅}, то есть
ни одному из игроков не выгодно отклониться.
В Примере 1.1 ни одно разбиение не является устойчивым по Нэшу, так как во всех
разбиениях есть игроки, которые не состоят в двухточечных коалициях, но хотят состоять.
Разбиение π индивидуально-устойчиво, когда
∀i ∈ N если ∃S ∈ π ∪ {∅} ∶ S ≠ π{i}, S ∪ {i} ≻i π(i), то ∃j ∈ S ∶ S ≻j S ∪ {i}, то есть ни
одном из игроков не может отклониться в более выгодную для себя коалицию, если это
не выгодно хотя бы одному из участников этой коалиции.
Индивидуальная устойчивость слабее устойчивости по Нэшу, так как достигается на
более узком классе разрешенных одиночных отклонений.
7
Разбиение π контрактно-устойчиво, когда
∀i ∈ N , если ∃S ∈ π ∪ {∅} ∶ S ≠ π(i), S ∪ {i} ≻i π(i) , то ∃j ′ ∈ π(i) ∶ π(i) ≻j ′ π(i) ∖ {i}, то есть
ни один из игроков не может покинуть коалицию, если это невыгодно хотя бы одному
из ее участников.
Контрактная устойчивость по Нэшу является более слабой, чем устойчивость по Нэшу,
так как достигается на более узком классе разрешенных одиночных отклонений. Если
в Примере 1.1 запретить выход из коалиции без одобрения одного из ее участников,
то, как уже было разобрано, все разбиения содержащие двухточечные коалиции будут
контрактно-устойчивыми.
Разбиение π контрактно-индивидуально устойчиво, когда
∀i ∈ N , если ∃S ∈ π ∪ {∅} ∶ S ≠ π(i), S ∪ {i} ≻i π(i) ,
то ∃j ∈ S ∶ S ≻j S ∪ {i} или ∃j ′ ∈ π(i) ∶ π(i) ≻j ′ π(i) ∖ {i}
Очевидно, что контрактно-индивидуальная устойчивость еще слабее чем индивидуальная и контактная устойчивости и слабее устойчивости по Нэшу.
Пример 1.2. Различные виды устойчивости удобно иллюстрировать на брачных отношениях. В этом случае класс разрешенных разбиений состоит из одиноких игроков
и разнополых пар.
Рассмотрим гедонистическую игру, в которой игроками будут герои романа Михаила
Шолохова «Тихий Дон» – Григорий, Аксинья, Наталья и Степан.
Обозначим игроков по первым буквам имен.
N = {Г, А, С, Н}
Будем считать, что Григорий, в характерной для себя манере, не может выбрать
между Аксиньей и Натальей и не хочет быть один. Аксинья не хочет жить со Степаном и мечтает соединиться с Григорием. Наталья и Степан пытаются сохранить
свои семейные отношения с Григроием и Аксиньей соответственно и не рассматривают друг друга в качестве возможных спутников жизни.
Таким образом, предпочтения игроков cреди коалиций выглядят следующим образом:
{ГА} ∼Г {ГН} ≻Г {Г};
{ГА} ≻А {А} ≻А {СА};
{СА} ≻С {С} ≻С {СН};
{ГН} ≻Н {Н} ≻Н {СН}.
Класс разрешенных разбиений состоит из следующих разбиений:
{ГА}{СН}, {СА}{ГН}, {Г}{А}{СН}, {ГА}{С}{Н}, {СА}{Г}{Н}, {С}{А}{ГН}, {Г}{А}{С}{Н}.
8
Оценим устойчивость этих разбиений.
1)В разбиении {ГА}{СН} Степан и Наталья имеют причины для отклонения в одноточечные коалиции, поэтому оно не устойчиво по Нэшу . Так как отклонение в одноточечную коалицию означает присоединение к пустой коалиции, в которой нет игроков, которые могли бы этому препятствовать, поэтому разбиение не индивидуальноустойчиво. Степан и Наталья – единственные, кто хочет отклониться – состоят
в одной коалиции, и они не будут препятствовать отклонению друг друга, поэтому
разбиение не контрактно-устойчиво.
Коалиции {С} и {Н} сильно блокируют разбиение, поэтому оно не принадлежит
слабому ядру .
2)При разбиении {СА}{ГН}, Аксинья хочет отклониться в одноточечную коалицию,
поэтому оно не устойчиво по Нэшу и не индивидуально-устойчиво. Отклонение Аксиньи не желательно для Степана, поэтому он будет ему препятствовать
и разбиение будет контрактно-устойчиво.
Коалиция {А} сильно блокирует разбиение, что означает, что оно не принадлежит
слабому ядру .
3)Разбиение {Г}{А}{СН} не устойчиво по Нэшу по целому ряду причин. Во-первых,
Аксинья и Григорий хотят объединиться, поэтому разбиение не индивидуально
устойчиво. Во-вторых, Степан и Наталья не хотят быть вместе, поэтому разбиение не контрактно-устойчиво.
Для этого разбиения есть целый ряд сильно блокирующих коалиций: {Г, А}, {Г, Н},
{С}, {Н}.
Оно не принадлежит слабому ядру .
4)При разбиении {ГА}{С}{Н} никто из игроков не имеет причин для одиночного отклонения, поэтому оно устойчиво по Нэшу . Сильно блокирующих коалиций нет,
но коалиция {Г, Н} будет слабо блокирующей, поэтому разбиение лежит в слабом
ядре, но не в сильном.
5)В разбиении {СА}{Г}{Н} у Аксиньи, Григория и Натальи есть причины для отклонения, причем и Григорий, и Наталья имеют причины для соединения, поэтому
разбиение не будет устойчиво по Нэшу, не индивидуально устойчиво и не
контрактно устойчиво.
Причем, если Степан и может помешать Аксинье уйти к Григорию, то никто не
мешает объединиться Григорию и Наталье, которые оба этого хотят.
Коалиции {ГА}, {ГН} и {А} сильно блокируют разбиение, поэтому оно не принадле9
жит слабому ядру.
6)При разбиении {С}{А}{ГН} только Степан имеет причины для одиночного отклонения. Он хочет присоединиться к Аксинье, а она этому препятствует, поэтому
разбиение индивидуально устойчиво. Коалиция {С} одноточечная, поэтому разбиение не контрактно устойчиво.
Нет сильно блокирующих коалиций, но есть слабо блокирующая – {ГН}, значит разбиение принадлежит слабому ядру .
7)В разбиении {Г}{А}{С}{Н} все игроки состоят в одноточечных коалициях и хотят
отклониться, поэтому оно не устойчиво по Нэшу и не контрактно-устойчиво.
И Аксинья, и Наталья хотели бы соединиться с Григорием, который не будет этому препятствовать, поэтому разбиение не индивидуально-устойчиво. Есть две
сильно блокирующие коалиции – {ГА} и {ГН}, поэтому разбиение не лежит в слабом ядре.
10
2.
Задача «об устойчивом браке»
Задачей «об устойчивом браке» называется обобщение задачи о разбиении игроков на
пары.
Пусть множество игроков делится на два непересекающихся подмножества – M = {m1 , ...mk }
и N = {n1 , ..., nl }. Требуется разбить игроков по парам, в которых один из игроков принадлежит первому подмножеству, а другой – второму. У игроков есть предпочтения
среди тех, кто будет с ними в паре. Может быть так, что некоторым парам игрок предпочитает одиночество. Каждый игрок может находиться одновременно в ограниченном
количестве пар.
Таким образом, отношение предпочтения u для игрока mi ∈ M задаётся на некотором
множестве Ni ⊆ N , а для игрока nj ∈ N – на множестве Mj ⊆ M .
Каждый игрок k ∈ M ∪ N может принадлежать не более qk парам.
Теорема Гейла-Шепли (1962)[8]
Для задачи «об устойчивом браке» со строгими предпочтениями игроков существует
решение из ядра.
Для доказательства этой теоремы был предложен алгоритм, который и получил
название «алгоритм Гейла—Шепли». Он представлен ниже.
Алгоритм 1. 1 шаг. Каждый игрок mi из множества M делает предложения qmi
наиболее предпочтительным для него игрокам из множества N . Если игроку mi не
нравится никто из N , то он выходит из игры. Каждый игрок nj из множества N
рассматривает предложения игроков из M и говорит «может быть» не более qnj
раз тем, предложение которых ему кажутся наиболее привлекательными. Если все
сделанные ему предложения, для него менее предпочтительны чем одиночество, то
он остается один.
2 шаг. Игроки множества M , не набравшие квоту, делают предложения наиболее
предпочтительным для них игрокам из множества N , не набравшим квоту. Если
для какого-то игрока mi из M ни один игрок из N не предпочтительнее одиночества,
то он не делает предложение никому. Игроки из множества N сравнивают новые
предложения со старыми и говорят «может быть» наиболее предпочтительным игрокам, количество которых не превышает их квоту. Предложения, менее предпочтительные чем одиночество, игроки не рассматривают.
3 шаг. Шаг 2 повторяется до тех пор, пока остаются игроки из M , которые не набрали квоту и не предпочитают одиночество всем не набравшим квоту игрокам из N , и
11
игроки из N со свободными местами, не предпочитающие одиночество всем игрокам
из M , не набравшим квоту.
4 шаг. Все «помолвленные» пары сходятся, а все остальные остаются одинокими.
Пример 2.1. Игру примера 1.2 можно переформулировать в виде задачи «об устойчивом браке».
M = {Г, С}, N = {А, Н}.
NГ = {A, H} А ≐Г Н
NC = {A} NA = {Г} NН = {Г}
q Г = qС = qА = qН = 1
1 шаг. Григорий и Степан делают предложение Аксинье. Аксинья говорит Григорию
«может быть», и они становятся помолвлены.
2 шаг. Единственный непомолвленный мужчина – Степан. Для него одиночество
предпочтительнее брака с Натальей и он выходит из игры.
3 шаг. Не осталось мужчин, которые хотели бы сделать предложение. Переходим к
следующему шагу.
4 шаг. Григорий и Аксинья сходятся, Степан и Наталья остаются одни.
Таким образом, в результате алгоритма Гейла-Шепли мы получили разбиение {ГА}{С}{Н}.
Нетрудно заметить, что оно действительно лежит в ядре.
Пример 2.2. С помощью алгоритма Гейла-Шепли можно решить задачу распределения шестерых студентов некоторой кафедры по четырем научным руководителям.
Фамилии педагогов – Сорокин, Дроздов, Грачев и Чижова.
Фамилии студентов – Петров, Федоров, Васильев, Назаров, Борисов и Алексеева.
Обозначим M = {П, Ф, В, Н, Б, А} и N = {С, Д, Г, Ч}, как множество студентов и преподавателей кафедры.
Будем считать, что студент может быть прикреплен к одному научному руководителю, поэтому qП = qФ = qВ = qН = qБ = qА = 1.
Пусть, научный руководитель может иметь не более двух студентов. qС = qД = qГ =
qЧ = 2.
Индивидуальные предпочтения игроков выглядят следующим образом:
NП = NФ = NВ = NН = NБ = NА = {С, Д, Г, Ч}
С ≻ П Д ≻П Г ≻П Ч
С ≻ Ф Д ≻Ф Ч ≻Ф Г
С ≻ В Ч ≻ В Г ≻В Д
12
Д ≻ Н С ≻Н Ч ≻ Н Г
Г ≻ Б Д ≻ Б С ≻Б Ч
Д ≻ А Г ≻А Ч ≻ А С
MС = {П, Ф, В, Б, А}
П ≻ С Н ≻С В ≻С А ≻ С Ф ≻С Б ≻С C
MД = {Ф, Б, П, В, Н}
Ф ≻Д Б ≻Д П ≻ Д В ≻ Д Н
MГ = {П, Ф, В}
MЧ = {Ф, П, Н, В, Б, А}
П ≻Г Ф ≻Г В
Ф ≻Ч П ≻ Ч Н ≻Ч В ≻Ч Б ≻Ч А ≻ Ч Ч
Реализуем алгоритм:
1 шаг. Петров, Федоров и Васильев делают предложение Сорокину, Назаров и Алексеева – Дроздову, Борисов – Грачеву. Сорокин говорит «может быть» Петрову и
Васильеву и отказывает Федорову. Дроздов говорит «может быть» Назарову. Грачев отказывает Борисову, а Дроздов – Алексеевой.
2 шаг. Федоров и Борисов делают предложение Дроздову, Алексеева – Грачеву. Дроздов
говорит «может быть» Федорову и Борисову и отказывает Назарову. Грачев отказывает Алексеевой.
3 шаг. Назаров делает предложение Сорокину, Алексеева – Чижеву и те говорят «может быть», Сорокин отказывает Васильеву.
4 шаг. Васильев делает предложение Чижеву и тот соглашается.
Студенты распределяются по научным руководителям следующим образом:
{НС}, {АЧ}, {ФД}, {БД}, {ПС}, {ВЧ}.
13
3.
Аддитивно-сепарабельные гедонистические игры
Определение 3.1. Аддитивно-сепарабельной гедонистической игрой (АСГИ)
называется игра, в которой каждый игрок i оценивает то, насколько ему важно состоять в одной коалиции с игроком j ∈ N с помощью веса игрока vi (j), и то, насколько он хочет состоять в коалиции S ∈ Ni с помощью веса коалиции vi (S) =
∑j∈S∖{i} vi (j), vi ({i}) = 0, S ≿i T ⇔ ∑j∈S∖{i} vi (j) ≥ ∑j∈T ∖{i} vi (j). [2]
Нетрудно заметить, что АСГИ могут быть представлены в виде взвешенного ориентированного графа, в котором игроки представлены вершинами, а вес дуги (i, j) равен
vi (j).
Определение 3.2. Аддитивно-сепарабельные предпочтения называются симметричными, если vi (j) = vj (i) = vij для всех i, j ∈ N .
АСГИ, все предпочтения которой симметричны, называется симметричной АСГИ .
Утверждение 3.1. Если для некоторой симметричной АСГИ разбиение π является
решением задачи
vij → max, то это разбиение устойчиво по Нэшу. [4]
∑
ij∶∃S∈π,ij∈S
Доказательство. (От противного)
Пусть, для некоторой симметричной АСГИ (N, ≿), разбиение π является решением задачи
vij → max и не устойчиво по Нэшу.
∑
ij∶∃S∈π,ij∈S
Т.е. ∃k ∈ N, ∃T ∈ π ∪ ∅ ∶
T ∪ {k} ≻k π(k).
По определению АСГИ это означает, что
vij >
∑
ij∶∈T ∪{k}
∑
vij = ∑ vij + ∑ vik + ∑ vkj >
ij∶∈T
ij∶∈T ∪{k}
i∈T
j∶∈T
∑ vij =
ij∶∈π(k)
∑ vij .
ij∶∈π(k)
vij + ∑ vkj + ∑ vik
∑
ij∈π(k),i≠k
j∈π(k)
i∈π(k)
vij =
∑
ij∶∃S∈π,ij∈S
∑
vij + ∑ vij + ∑ vij =
ij∶∃S∈π,S≠π(k),S≠T,ij∈S
∑
ij∶∃S∈π,S≠π(k),S≠T,ij∈S
∑
vij + ∑ vkj + ∑ vik + ∑ vij <
∑
ij∈π(k)∖{k}
vij +
ij∶∃S∈π,S≠π(k),S≠T,ij∈S
∑
ij∈T
ij∈π(k)
vij +
j∈π(k)
j∈T
ij∈π(k)∖{k}
vij +
ij∶∃S∈π,S≠π(k),S≠T,ij∈S
vij +
∑
ij∈π(k)∖{k}
Получается, что на π сумма
ij∈T
i∈π(k)
vij + ∑ vkj + ∑ vik + ∑ vij =
∑
i∈T
∑
ij∈T
vij
ij∈T ∪{k}
∑
vij не достигает максимума и это противоречит
ij∶∃S∈π,ij∈S
начальному условию.
Значит наше предположение было неверно и разбиение π устойчиво по Нэшу.
Замечание 3.1. Для симметричной АСГИ всегда существует разбиение, устойчивое
по Нэшу.
14
Пример 3.1. Рассмотрим симметричную АСГИ четырех игроков, порожденную следующим графом.
Решением задачи
∑
vij → max является разбиение π = {1, 2, 4}{3}.
ij∶∃S∈π,ij∈S
Коалиционная структура π устойчива по Нэшу.
Пример 3.2. Известно, что усвояемость пищи зависит от сочетания входящих в
нее компонентов, поэтому далеко не все продукты питания полезно употреблять
вместе. Допустим, в магазине был куплен следующий набор продуктов: яйца, сыр,
кабачки, хлеб, рис и банка варенья. Согласно исследованиям, яйца, сыр и варенье нельзя сочетать с хлебом и рисом. Кабачки плохо перевариваются с вареньем. Чтобы
понять, в каких сочетаниях следует употреблять купленные продукты, составим
симметричную АСГИ, в которой продукты будем считать игроками. Веса дуг, соединяющих «сочетаемые» продукты, назначим равными 1, а веса дуг соединяющих
«несочетаемые» продукты будут -1.
N = {яйца, сыр, кабачок, хлеб, рис, варенье}
(Продукты будем обозначать по первым буквам названия.)
vяс = 1, vяк = 1, vях = −1, vяр = −1, vяв = 1,
vск = 1, vсх = −1, vср = −1, vсв = 1,
vкх = 1, vкр = 1, vкв = −1,
vхр = 1, vхв = −1, vрв = −1.
Чтобы составить правильные сочетания продуктов, нужно решить задачу
∑
vij → max.
ij∶∃S∈π,ij∈S
Получается, что разбиение π = {яйцо, сыр, варенье}{кабачок, хлеб, рис} устойчиво по
15
Нэшу. Такое разбиение продуктов наиболее полезно.
16
4.
Игры с общим порядком предпочтений
Определение 4.1. Говорят, что гедонистическая игра (N, ≿) имеет общий порядок
предпочтений, если существует функция w ∶ 2N ∖ {∅} → R, такая, что для любого
игрока i и всех содержащих его коалиций C и D верно следующее: C ≿i D ⇔ w(C) ≥
w(D). [14]
Для игры с общим порядком предпочтений, был найден алгоритм нахождения устойчивой по Нэшу коалиционной структуры из ядра [14].
Алгоритм 2. (В π будем записывать коалиции. Множество игроков, коалиции которых еще не найдены, обозначим как R.)
1. π ∶= ∅, R ∶= N .
2. Пока R ≠ ∅ выполняем следующие операции.
-Выбираем подкоалицию T ⊆ R с наибольшим значением w(T ). Если таких коалиций
несколько, то выбираем ту, в которой больше игроков. Среди коалиций одинакового
размера можно выбирать любую.
-Добавляем T в π.
-R ∶= R ∖ T .
Утверждение 4.1. Алгоритм 2 находит для гедонистической игры с общим порядком
предпочтений индивидуально-устойчивую коалиционную структуру из ядра.
Доказательство. В начале докажем, что полученное разбиение содержится в ядре.
(От противного)
Предположим, что разбиение π, полученное в результате работы алгоритма, не содержится в ядре.
Тогда существует коалиция S, такая что S ≻i π(i) для всех игроков i ∈ S. Это означает,
что w(S) > w(π(i)) для всех игроков i ∈ S.
Рассмотрим игрока i′ ∈ S такого, что w(π(i′ )) > w(π(i))∀i ∈ S. Значит, коалиция π(i′ )
была выбрана раньше остальных коалиций π(i), содержащих игроков из S, а значит
π(i′ ) – то подмножество ∪i∈S π(i), на котором функция w принимает наибольшее значение. w(S) не может быть больше w(π(i)).
Значит, наше предположение было неверно, и разбиение π содержится в ядре.
Теперь докажем, что π индивидуально-устойчиво.
(От противного)
Допустим, что π не индивидуально-устойчиво.
17
Тогда, существует игрок i и коалиция S ∈ π : S ∪ {i} ≻i π(i).
Т.е. w(S ∪ {i}) > w(π(i)). Получается, что коалиция S была выбрана раньше чем π(i)
и w(S) > w(S ∪ {i}) > w(π(i)). Таким образом, игрокам из S не выгодно отклонение i и
разбиение π индивидуально-устойчиво.
Предположение было неверно.
Пример 4.1. Пусть в гедонистической игре (N, ≿) с общим порядком предпочтений
N = {1, 2, 3} и функция w задана следующим образом:
w({1}) = 3, w({2}) = 4, w({3}) = 2, w({12}) = 4, w({13}) = 4, w({23}) = 1,
w({123}) = 3.
Тогда общий порядок предпочтений игроков среди коалиций выглядит следующим образом: {2} ∼ {12} ∼ {13} ≻ {1} ∼ {123} ≻ {3} ≻ {23}.
Реализуем алгоритм.
Начальные данные:
1 шаг. T ∶= {12}
S=N
π=∅
S ∶= S ∖ T = {3} π ∶= {12}
2 шаг. T ∶= {3}
S ∶= S ∖ T = ∅ π ∶= {12}{3}
Нетрудно проверить, что коалиционная структура {12}{3}, полученная в результате реализации алгоритма, индивидуально-устойчива и находится в ядре.
18
5.
B,W и T OP–игры
5.1.
Определение B и W–игр
Опишем игры, в которых предпочтения каждого игрока i среди коалиций S ∈ Ni однозначно определяется через список всех игроков N , упорядоченный по предпочтению
для этого игрока i. В этом случае мы говорим, что на множестве игроков N задано
отношение предпочтения u.
Если для каждого игрока i ∈ N и каждой коалиции S ∈ Ni задать множество наиболее
(maxui (S)) или наименее (minui (S)) предпочтительных игроков из коалиции S для игрока i, то для каждого i ∈ N можно упорядочить по предпочтительности множество
коалиций Ni .
Определение 5.1. Игра называется B–игрой, или игрой с B-предпочтениями, если
S ui T т.и т.т. когда выполнено одно из следующих условий:
1)∀s ∈ maxui (S ∖ {i}), ∀t ∈ maxui (T ∖ {i}), s ⋗i t
2)∀s ∈ maxui (S ∖ {i}), ∀t ∈ maxui (T ∖ {i}), s ≐i t, ∣S∣ < ∣T ∣
Определение 5.2. Игра называется W–игрой, или игрой с W-предпочтениями, если
S ≻i T т.и т.т. когда выполнено одно из следующих условий:
1)∀s ∈ minui (S ∖ {i}), ∀t ∈ minui (T ∖ {i}), s ⋗i t
2)∀s ∈ minui (S ∖ {i}), ∀t ∈ minui (T ∖ {i}), s ≐i t, ∣S∣ < ∣T ∣
[2]
Считаем, что maxui ({i}) = minui ({i}) = i.
Замечание 5.1. В B и W–играх S ∼i T т. и т.т. когда
∀s ∈ minui (S ∖ {i}), ∀t ∈ minui (T ∖ {i}), s ≐i t, ∣S∣ = ∣T ∣
Пример 5.1. Рассмотрим игру пяти лиц N = {Н, Л, Ф, З, Т}, для которых задан следующий список предпочтений:
для Н ∶ Л ⋗Н Ф ⋗Н Н ⋗Н Т ⋗Н З
для Л ∶ Ф ⋗Л З ⋗Л Н ⋗Л Л ⋗Л Т
для Ф ∶ Л ⋗Ф Н ⋗Ф З ⋗Ф Ф ⋗Ф Т
для З ∶ Т ⋗З Л ⋗З Ф ⋗З З ⋗З Н
для Т ∶ З ⋗Т Л ⋗Т Н ⋗Т Ф ⋗Т Т
19
Если по нему построить B–игру, то список предпочтений среди коалиций будет выглядеть следующим образом:
для Н
{ЛН} ≻Н {ЛФН} ∼Н {ЛЗН} ∼Н {ЛТН} ≻Н {ЛФЗН} ∼Н {ЛФТН} ∼Н {ЛЗТН} ≻Н
{ЛФЗТН} ≻Н {ФН} ≻Н {ФЗН} ∼Н {ФТН} ≻Н {ФЗТН} ≻H {H} ≻Н {ТН} ≻Н {ЗТН} ≻Н
{ЗН}
для Л
{ФЛ} ≻Л {ФЛН} ∼Л {ФЛЗ} ∼Л {ФЛТ} ≻Л {ФЛНЗ} ∼Л {ФЛНТ} ∼Л
{ФЛЗТ} ≻Л {ФЛНЗТ} ≻Л {ЗЛ} ≻Л {НЛЗ} ≻Л {ЗЛТ} ≻Л {ЗЛТН} ≻Л {НЛ} ≻Л {НЛТ} ≻Л
{Л} ≻Л {ЛТ}
для Ф
{ЛФ} ≻Ф {ЛФН} ∼Ф {ЛФЗ} ∼Ф {ЛФТ} ≻Ф {ЛФНЗ} ∼Ф {ЛФНТ} ∼Ф
{ЛФЗТ} ≻Ф {ЛФНЗТ} ≻Ф {НФ} ≻Ф {НФЗ} ≻Ф {НФТ} ≻Ф {НФЗТ} ≻Ф {ЗФ} ≻Ф {ЗФТ} ≻Ф
{Ф} ≻Ф {ТФ}
для З
{ЗТ} ≻З {ТЗЛ} ∼З {ТЗН} ∼З {ТЗФ} ≻З {ТЗЛН} ∼З {ТЗЛФ} ∼З {ТЗНФ} ≻З
{ТЗНФЛ} ≻З {ЛЗ} ≻З {ЛЗН} ∼З {ЛЗФ} ≻З {ЛЗФН} ≻З {ФЗ} ≻З {ФЗН} ≻З {З} ≻З {ЗН}
для Т
{ЗТ} ≻т {ЗТЛ} ∼т {ЗТН} ∼т {ЗТФ} ≻т {ЗТЛФ} ∼т {ЗТЛН} ∼т {ЗТНФ} ≻т
{ЗТНФЛ} ≻т {ЛТ} ≻т {ЛТФ} ∼т {ЛТН} ≻т {ЛТНФ} ≻т {НТ} ≻т {НТФ} ≻т {ФТ} ≻Т {Т}
Пример 5.2. Если взять тот же список предпочтений среди игроков, что и в примере 5.1, но игру считать W–игрой, то предпочтения игроков среди коалиций будут
выглядеть следующим образом:
для Н
{ЛН} ≻Н {ФН} ≻Н {ФНЛ} ≻H {H} ≻Н {ТН} ∼Н {ФТН} ∼Н {ЛТН} ≻Н {ЛФТН} ≻Н
{ЗН} ≻Н {ЗНФ} ∼Н {ЗНЛ} ∼Н {ЗТН} ≻Н {ЗНФТ} ∼Н {ЗНЛТ} ∼Н {ЗНЛФ} ≻Н {ЗНЛФТ}
для Л
{ФЛ} ≻Л {ЗЛ} ≻Л {ЗЛФ} ≻Л {НЛ} ≻Л {НЛФ} ∼Л {ЗЛН} ≻Л {ЗЛНФ} ≻Л
{Л} ≻Л {ТЛ} ≻Л {ТЛЗ} ∼Л {ТЛФ} ∼Л {ТЛН} ≻Л {ТЛНЗ} ∼Л {ТЛФЗ} ∼Л {ТЛФН} ≻Л
{ТЛФНЗ}
для Ф
{ЛФ} ≻Ф {НФ} ≻Ф {НФЛ} ≻Ф {ЗФ} ≻Ф {ЗФН} ∼Ф {ЗФЛ} ≻Ф {ЗФЛН} ≻Ф
{Ф} ≻Ф {ТФ} ≻Ф {ТФЗ} ∼Ф {ТФЛ} ∼Ф {ТФН} ≻Ф {ТФЛЗ} ∼Ф {ТФНЗ} ∼Ф {ТФНЛ} ≻Ф
{ТФНЛЗ}
20
для З
{ТЗ} ≻з {ЛЗ} ≻з {ЛЗТ} ≻з {ФЗ} ≻з {ФЗТ} ∼з {ФЗЛ} ≻з {ФЗЛТ} ≻з {З} ≻
з{НЗ} ≻з {НЗЛ} ∼з {НЗФ} ∼з {НЗТ} ≻з {НЗТФ} ∼з {НЗЛТ} ∼з {НЗЛФ} ≻з {НЗЛФТ}
для Т
{ЗТ} ≻т {ЛТ} ≻т {ЛТЗ} ≻т {НТ} ≻т {НТЗ} ∼т {НТЛ} ≻т {НТЛЗ} ≻
т{ФТ} ≻т {ФТН} ∼т {ФТЗ} ∼т {ФТЛ} ≻т {ФТНЗ} ∼т {ФТЛН} ∼т {ФТЛЗ} ≻т {ФТЛЗН} ≻т
{Т}
5.2.
T OP–игры
Обозначим как Ch(i, S), ту подкоалицию коалиции S, которую игрок i предпочитает
больше других.
Для обозначения наиболее предпочтительных подкоалиций коалиции S для игрока i в
введем обозначение Ch(i, S):
Ch(i, S) ∶= {S ′ ⊆ S ∶ (i ∈ S ′ ) ∧ (S ′ ≿i S ′′ ∀S ′′ ⊆ S)}
Если ∣Ch(i, S)∣ = 1, то мы обозначаем единственное подмножество S, которое наиболее
предпочтительно для i, как ch(i, S).
Определение 5.3. Игра (N, ≿) называется T OP–игрой, если каждая коалиция имеет одну наиболее предпочтительную подкоалицию и для любого игрока i и любых двух
коалиций S и T , его содержащих, верно, что:
1)S ≻i T , если ch(i, S) ≻i ch(i, T )
2)S ≻i T , если ch(i, S) = ch(i, T ), S ⊂ T [2]
Таким образом, считается, что чем меньше множество, содержащее «кумира», тем
оно лучше.
Если (N, ≿) – T OP–игра, то ∀S, T ⊆ N, i ∈ (S ∩ T ) верны следующие утверждения.
Утверждение 5.1. Если S ≻i T , то ch(i, S) ≿i ch(i, T ).
Доказательство. (От противного) Пусть ch(i, T ) ≻i ch(i, S). Тогда по определению
T OP–игры T ≻i S, что противоречит исходным данным. Таким образом, наше предположение было не верно.
Утверждение 5.2. Если T ⊆ N , то ch(i, S) ≿i ch(i, T )∀i
Утверждение 5.3. Если T ⊂ S, T ≿i S то ch(i, S) = ch(i, T ).
21
Доказательство. (От противного) Пусть ch(i, S) ≻i ch(i, T ). Тогда S ≻i T , что противоречит исходным данным. Значит наше предположение было неверно и ch(i, S) ∼i
ch(i, T ), то есть ch(i, S) = ch(i, T ).
Утверждение 5.4. Если T ⊆ S, S ≿i T, ch(i, S) = ch(i, T ),то S = T .
Доказательство. (От противного) Пусть T ⊂ S, тогда по определению T OP–игры T ≿i
S, что противоречит начальным условиям. Значит наше предположение было неверно
и S = T.
Замечание 5.2. Если B или W–игра является T OP–игрой, то для каждого игрока
существует только один наиболее предпочтительный игрок.
Доказательство. Допустим, что у игрока i ∈ N существует два наиболее предпочтительных игрока j и k.
Ch(i, {i, j, k}) = {{i, j}, {i, k}}, значит ∣Ch(i, {i, j, k})∣ ≠ 2 и игра и не является T OPигрой, что противоречит нашему изначальному предположению.
Таким образом, если B или W–игра является T OP–игрой, то у каждого игрока существует только один наиболее предпочтительный игрок.
Замечание 5.3. Обратное утверждение не верно.
B или W–игра, в которой каждый игрок имеет одного наиболее предпочтительного
игрока, не всегда является T OP–игрой.
Пример 5.3. Рассмотрим B - игру со следующими упорядоченными по предпочтению
списками игроков:
2 ⋗1 3 ≐1 4 ⋗1 1
3 ⋗2 4 ≐2 1 ⋗2 2
1 ⋗3 2 ≐3 4 ⋗3 3
3 ⋗4 2 ≐4 1 ⋗4 4
В этом случае, предпочтения игроков среди коалиций выглядят следующим образом:
{12} ≻1 {123} ∼1 {124} ≻1 {1234} ≻1 {13} ∼1 {14} ≻1 {134} ≻1 {1}
{23} ≻2 {123} ∼2 {234} ≻2 {1234} ≻2 {24} ∼2 {12} ≻2 {124} ≻2 {2}
{13} ≻3 {123} ∼3 {134} ≻3 {1234} ≻3 {23} ∼3 {34} ≻3 {234} ≻3 {3}
{34} ≻4 {234} ∼4 {134} ≻4 {1234} ≻4 {24} ∼4 {14} ≻4 {124} ≻4 {4}
∣Ch(1, {134})∣ = ∣{13}{14}∣ = 2 и игра не является T OP–игрой.
22
Утверждение 5.5. Если в B или W–игре каждый игрок имеет строгий порядок предпочтений среди игроков, то ∣Ch(i, S)∣ = 1 для любого игрока i и содержащей его коалиции S.
Доказательство. (От противного)
Пусть в некоторой B–игре каждый игрок имеет строгий порядок предпочтений среди
игроков, но для некоторого игрока i найдется коалиция S такая, что ∣Ch(i, S)∣ > 1.
Это означает, что в S найдется хотя бы два подмножества S1 и S2 такие что S1 , S2 ∈
Ch(i, S).
Так как S1 , S2 ∈ Ch(i, S), значит S1 ∼i S2 .
Из замечания мы знаем, что в игре две коалиции S1 и S2 могут быть одинаково предпочтительны для игрока i, только если
∀s1 ∈ maxui (S1 ∖ {i}), ∀s2 ∈ maxui (S2 ∖ {i}), s1 ∼i s2 , ∣S1 ∣ = ∣S2 ∣.
В нашей игре для i задан строгий порядок предпочтений среди игроков, значит
∣maxui (S1 ∖ {i})∣ = ∣maxui (S2 ∖ {i})∣ = 1 и maxui (S1 ∖ {i}) = maxui (S2 ∖ {i}) = {smax }
Обозначим множество {smax , i} как Sm
Покажем, что S1 = Sm .
Допустим, что это не так и Sm ⊂ S1 , а ∣Sm ∣ < ∣S1 ∣.
Мы знаем, что maxui (S1 ∖ {i}) = {smax } = maxui (Sm ∖ {i}).
По определению B–игры получается, что Sm ≻i S1 , но этого быть не может, так как
Sm ⊂ S1 ⊆ S, а S1 ∈ Ch(i, S).
Значит наше предположение было неверно и S1 = Sm .
Аналогично доказывается, что S2 = Sm .
Таким образом, получается, что S1 = Sm = S2 и предположение о том, что найдутся
такие i и S, что ∣Ch(i, S)∣ > 1 было неверно.
Доказательство для W–игры полностью аналогично.
Утверждение 5.6. Если в B–игре каждый игрок имеет строгий порядок предпочтений среди игроков, то для любого игрока i и содержащей его коалиции S множества
maxui (S ∖ {i}) и maxui (ch(i, S) ∖ {i}) равны.
Доказательство. Мы знаем, что ch(i, S) ≿i S.
Тогда по определению B–игры выполняется одна из двух альтернатив:
1)∀cs ∈ maxui (ch(i, S) ∖ {i}), ∀s ∈ maxui (S ∖ {i}) ∶ cs ⋗i s,
2)∀cs ∈ maxui (ch(i, S) ∖ {i})∀s ∈ maxui (S ∖ {i}) ∶ s ≐i cs, ∣Ch(i, S)∣ < ∣S∣.
Первая альтернатива не может быть выполнена, так как maxui (ch(i, S)∖{i}) ⊆ ch(i, S) ⊆
23
S, значит всегда выполняется вторая.
Игрок i имеет строгий порядок предпочтений среди игроков, поэтому множества maxui (S∖
{i}) и maxui (ch(i, S) ∖ {i}) одноточечные, а значит maxui (S ∖ {i}) = maxui (ch(i, S) ∖
{i}).
Утверждение 5.7. Если в W–игре каждый игрок имеет строгий порядок предпочтений среди игроков, то для любого игрока i и содержащей его коалиции S множества
minui (S ∖ {i}) и minui (ch(i, S) ∖ {i}) равны.
Доказательство. Доказывается аналогично предыдущему утверждению.
Утверждение 5.8. Если в B или W–игре каждый игрок имеет строгий порядок предпочтений среди других игроков, то для любого игрока i и любых двух коалиций, которым он принадлежит, из того что ch(i, S) ≻i ch(i, T ) следует, что S ≻i T .
Доказательство. Возьмем i, S, T такие, что ch(i, S) ≻i ch(i, T ).
По определению B–игры получается, что выполняется одна из двух альтернатив:
1)∀s ∈ maxui (ch(i, S) ∖ {i}), ∀t ∈ maxui (ch(i, T ) ∖ {i}) ∶ s ⋗i t
2)∀s ∈ maxui (ch(i, S) ∖ {i})∀s ∈ maxui (ch(i, T ) ∖ {i}) ∶ s ≐i t, ∣Ch(i, S)∣ < ∣Ch(i, T )∣.
Из предыдущего замечания мы знаем, что maxui (S ∖ {i}) = maxui (ch(i, S) ∖ {i}) и
maxui (T ∖ {i}) = maxui (ch(i, T ) ∖ {i}). Выполним замену множеств в 1),2) и получим,
что выполнена одна из альтернатив
1′ )∀s ∈ maxui (S ∖ {i}), ∀t ∈ maxui (T ∖ {i}) ∶ s ⋗i t
2′ )∀s ∈ maxui (S ∖ {i})∀s ∈ maxui (T ∖ {i}) ∶ s ≐i t, ∣S∣ < ∣T ∣.
Это равносильно тому, что S ≻i T .
Доказательство для W–игры аналогично.
Утверждение 5.9. Если в B или W–игре каждый игрок имеет строгий порядок предпочтений среди других игроков, то для любого игрока i и любых двух коалиций S и
T , которым он принадлежит, из того что ch(i, S) ∼i ch(i, T ) и S ⊆ T следует, что
S ≻i T .
Доказательство. Рассмотрим i, S, T такие, что ch(i, S) ∼i ch(i, T ) и S ⊂ T .
Так как S ⊂ T , значит ∣S∣ < ∣T ∣.
Из Замечания 5.1 мы знаем, что ch(i, S) ∼i ch(i, T ) равносильно тому, что
∀s ∈ maxui (ch(i, S) ∖ {i}), ∀t ∈ maxui (ch(i, T ) ∖ {i}), s ⋗i t, ∣ch(i, S)∣ = ∣ch(i, T )∣
Из Утверждения 6.6 мы знаем, что maxui (S∖{i}) = maxui (ch(i, S)∖{i}) и maxui (T ∖{i}) =
24
maxui (ch(i, T ) ∖ {i})
Получается, что
∀s ∈ maxui (S ∖ {i}), ∀t ∈ maxui (T ∖ {i}), s ≐i t, ∣S∣ < ∣T ∣,
Значит, S ≻i T .
Следствие 5.1. B или W–игра, в которой каждый игрок имеет строгий порядок предпочтений среди игроков является T OP–игрой.
5.3.
Алгоритм «Top covering»
Опишем алгоритм нахождения разбиения из сильного ядра, для T OP–игры.
Для каждого X ⊆ N , определим отношение достижимости ↷X , как бинарное отношение
на X × X, где i ↷X j т. и т.т., когда j ∈ ch(i, X). В этом случае j называется соседом i в
X. Коалицию CC(i, X), достижимую игроком i в X, определим следующим образом:
CC(i, X) = {k ∈ X ∶ ∃j1 , ..., jl ∈ X ∶ i = j1 ↷X ... ↷X jl = k}
Алгоритм 3. «Top covering»[2]
(В π будем записывать коалиции. Множество игроков, коалиции которых еще не найдены, обозначим как R.)
1. π ∶= ∅, R ∶= N
2. Пока R ≠ ∅ выполняем следующие операции:
- Из множества R находим игрока i: CC(i, R) ≤ CC(j, R)∀j ∈ R.
- Добавляем в π найденное множество CC(i, R).
- R ∶= R ∖ CC(i, R).
Утверждение 5.10. Алгоритм «Top covering», примененный к T OP-игре, дает разбиение из ядра.[5]
Доказательство. Применим алгоритм к T OP–игре. Множество π, полученное на выходе, является разбиением, так как состоит из непересекающихся множеств, объединение
которых образует N .
Докажем, что разбиение π лежит в ядре.
(От противного)
Очевидно, что алгоритм циклический.
Множество тех игроков, среди которых ведется поиск k-ого элемента разбиения(во время k-го прохождения цикла) обозначим как Rk .
25
Будем обозначать как k(j) порядковый номер того цикла, на котором была найдена
коалиция игрока j .
Пусть для разбиения π, полученного с помощью алгоритма, найдется блокирующая
коалиция S, т.е.
S ≻j π(j)∀j ∈ S
(1)
Множество коалиций из разбиения π, которые содержат игроков из S обозначим как
πS .
Пусть коалиция π(j ′ ) игрока j ′ ∈ S, была найдена раньше остальных коалиций из πS .
k(j ′ ) будем обозначать как k ′ .
′
Тогда для любого j ∈ S, коалиция CC(j, Rk(j) ) содержится в Rk .
′
CC(j, Rk(j) ) ⊆ Rk ∀j ∈ S
(2)
Так как для любого j коалиция π(j), была выделена из множества Rk(j) , то
CC(j, Rk(j) ) = π(j)∀j ∈ S
(3)
Из 3 следует, что для всех игроков j из S верно, что ch(j, π(j)) = ch(CC(j, Rk(j) )) =
ch(i, Rk(j) )
ch(i, π(j)) = ch(i, Rk(j) )∀j ∈ S
(4)
Коалиция S–блокирующая, поэтому S ≻j π(j)∀j ∈ S.
По Утверждению 6.1 получается, что
ch(j, S) ≿j ch(j, π(j)) = ch(j, Rk(j) )∀j ∈ S
(5)
ch(j, S) ≿j ch(j, Rk(j) )∀j ∈ S
(6)
′
Все игроки из S содержатся в Rk , поэтому по Утверждению 6.1
′
ch(j ′ , Rk ) ≿j ′ ch(j ′ , S)
(7)
′
Из (7),(6) получаем, что ch(j ′ , Rk ) ∼j ′ ch(j ′ , S). У нас T OP-игра, поэтому
′
ch(j, Rk ) = ch(j, S)∀j ∈ S
(8)
′
В частности, ch(j ′ , Rk ) = ch(j ′ , S).
Докажем, что π(j ′ ) ⊆ S
Пусть t ∈ N. Для каждого игрока i и коалиции X, его содержащей, определим функцию
C t ∶ N ∗ 2N → 2N следующим образом :
26
C 1 (i, X) = ch(i, X)
C t+1 (i, X) = ∪i∈C t (i,X) ch(i, X)
′
Докажем по индукции, что C t (j ′ , Rk ) ⊆ S ∀t ∈ N
База
′
′
C 1 (j ′ , Rk ) = ch(j ′ , Rk ) = ch(j ′ , S) ⊆ S
Переход
′
′
(Покажем, что если C t (j ′ , Rk ) ⊆ S, то и C t+1 (j ′ , Rk ) ⊆ S)
′
′
Очевидно, что C t (j ′ , Rk ) ⊆ CC(j ′ , Rk )∀t ∈ N
′
′
Поэтому для любого j из C t (j ′ , Rk ) верно, что π(j) = π(j ′ ) = CC(j ′ , Rk ).
′
′
′
Очевидно, что для любого игрока j из C t (j ′ , Rk ) верно, что CC(j, Rk ) ⊆ CC(j ′ , Rk ).
′
′
′
′
ch(j, Rk ) ⊆ CC(j, Rk ) ⊆ CC(j ′ , Rk ) = π(j)∀j ∈ C t (j ′ , Rk )
Получается, что
′
′
ch(j, Rk ) = ch(j, π(j))∀j ∈ C t (j ′ , Rk )
′
(9)
′
Из (8),(9) получается, что ch(i, π(i)) = ch(i, S) = ch(j, Rk )∀i ∈ C t (j ′ , Rk )
′
′
Тогда C t+1 (j ′ , Rk ) = ∪i∈C t (j ′ ,Rk′ ) ch(i, Rk ) ⊆ S
′
′
′
CC(j ′ , X k ) = ∪t∈N C t (j ′ , Rk ) => π(j ′ ) = CC(j ′ , X k ) ⊆ S
Очевидно, что S = π(j ′ )
Замечание 5.4. Из предыдущего утверждения вытекает, что для игр обладающих
высокой восприимчивостью существует разбиение из ядра.
Пример 5.4. (Пример реализации алгоритма для B-игры, в которой каждый из игроков имеет одного наиболее предпочтительного игрока)
Рассмотрим гедонистическую игру в которой N = {1, 2, 3, 4} и для каждого игрока
существуют следующие предпочтения среди игроков:
2 ⋗1 3 ⋗1 4 ⋗1 1
3 ⋗2 4 ⋗2 1 ⋗2 2
1 ⋗3 2 ⋗3 4 ⋗3 3
3 ⋗4 2 ⋗4 1 ⋗4 4
Тогда предпочтения игроков на множестве коалиций выглядят следующим образом:
27
{12} ≻1 {123} ∼1 {124} ≻1 {1234} ≻1 {13} ≻1 {134} ≻1 {14} ≻1 {1}
{23} ≻2 {123} ∼2 {234} ≻2 {1234} ≻2 {24} ≻2 {124} ≻2 {12} ≻2 {2}
{13} ≻3 {123} ∼3 {134} ≻3 {1234} ≻3 {23} ≻3 {234} ≻3 {34} ≻3 {3}
{34} ≻4 {234} ∼4 {134} ≻4 {1234} ≻4 {24} ≻4 {124} ≻4 {14} ≻4 {4}
Данная игра является T OP-игрой. Реализуем алгоритм «Top covering».
Начальные данные: R = {1234}, π = ∅
1 шаг.
– 4 ↷{1234} 3 ↷{1234} 1 ↷{1234} 2 ↷{1234} 3
– S ∶= {123}
– π ∶= {123}
– R ∶= {1234} ∖ {123} = {4}
2 шаг.
– CC(4, {4}) = 4
– S ∶= {4}
–π ∶ {123}{4}
–R ∶= {4} ∖ {4} = ∅
В итоге: π = {123}{4} – разбиение из ядра.
Замечание 5.5. Из Замечания 5.1 очевидно, что данный алгоритм нельзя применить
к B–игре, в которой хотя бы один из игроков имеет более одного наиболее предпочтительного игрока.
Пример 5.5. Рассмотрим игру (N, ≿), где N = {1, 2, 3, 4} со следующим списком предпочтений среди игроков:
2 ≐1 3 ⋗1 4 ⋗1 1
3 ⋗2 4 ⋗2 1 ⋗2 2
1 ⋗3 2 ⋗3 4 ⋗3 3
3 ⋗4 2 ⋗4 1 ⋗4 4
Очевидно, что Ch(1, N ) = {12}{13}, Ch(2, N ) = {23}, Ch(3, N ) = {13}, Ch(4, N ) = {34}
и разбиение {13}{24} лежит в ядре, но данный алгоритм не применим к этой игре и
найти его не может.
28
Пример 5.6. Продемонстрируем работу алгоритма «Top covering» для игры
примера 5.1.
для Н ∶ Л ⋗Н Ф ⋗Н Н ⋗Н Т ⋗Н З
для Л ∶ Ф ⋗Л З ⋗Л Н ⋗Л Л ⋗Л Т
для Ф ∶ Л ⋗Ф Н ⋗Ф З ⋗Ф Ф ⋗Ф Т
для З ∶ Т ⋗З Л ⋗З Ф ⋗З З ⋗З Н
для Т ∶ З ⋗Т Л ⋗Т Н ⋗Т Ф ⋗Т Т
Начальные данные: π = ∅ R = N
1 шаг.
–Н ↷{НЛФЗТ} Л ↷{НЛФЗТ} Ф ↷{НЛФЗТ} Л
З ↷{НЛФЗТ} Т ↷{НДФЗТ} З
–S ∶= {ТЗ}
–π ∶= {ТЗ}
–R ∶= R ∖ {ТЗ} = {НЛФ}
2 шаг.
–Н ↷{НЛФ} Л ↷{НЛФ} Ф ↷{НЛФ} Л
–S ∶= {ЛФ}
–π ∶= {ТЗ}{ЛФ}
–R ∶= R ∖ {ТЗ} = {Н}
3 шаг.
–S ∶= {Н}
–π ∶= {ТЗ}{ЛФ}{Н}
–R ∶= R ∖ {Н} = ∅
Итог: разбиение π = {ТЗ}{ЛФ}{Н} находится в ядре.
29
Заключение
В работе были изучены принципы устойчивости для коалиционных структур в гедонистических играх, предъявлены и продемонстрированы с помощью примеров некоторые
модели игр, для которых есть алгоритм нахождения устойчивого решения.
Изучив уже опубликованные исследования в области теории гедонистических игр,
приходится сделать вывод, что она разработана не достаточно широко. Обзорная статья, послужившая основой для данной работы, ссылается на более чем пятьдесят источников, но большинство из них являются пересказом друг друга. Известно очень
мало моделей игр, для которых существует разбиение, обладающее достаточно сильной устойчивостью. Хочется верить, что новые исследования в этой области принесут
практически-важные результаты.
30
Литература
[1] Alcalde, J., and Revilla, P., Researching with whom? Stability and manipulation.
Journal of Mathematical Economics, 40(8), 869-887, 2004.
[2] Aziz, H. and Savani, R., Hedinic Games. In: F. Brandt, V. Conitzer, U. Endriss, J. Lang,
and A. D. Procaccia (eds.), Handbook of Computational Social Choice. Cambridge
University Press, 2015.
[3] Banerjee, S., H. Konishi, and T. Sönmez, Core in a simple coalition formation game,
Social Choice and Welfare 18, 135-153, 2001.
[4] Bogomolnaia, A. and Jackson, M. O., The Stability of Hedonic Coalition Structures.,
Games and Economic Behavior, 38(2), 201-230, 2002.
[5] Dimitrov, D. and Sung, S. C., Top responsiveness and Nash stability in coalition
formation games., Kybernetika, 2006.
[6] Dimitrov, D. and Sung, S. C., Top responsiveness and stable partitions in coalition
formation games., Universität Bielefeld, 2005.
[7] Dréze, J.H. and Greenberg, J., Hedonic coalitions: optimality and stability,
Econometrica, 48(4), 987-1003, 1980.
[8] Gale, D., and Shapley, L.S., College Admissions and the Stability of Marriage., The
American Mathematical Monthly, 1962.
[9] Hajduková, J., Coalition formation games: A survey. International Game Theory
Review, 8(4), 613-641, 2006.
[10] Roth, A.E., The Economics of Matching: Stability and Incentives, Mathematics of
Operations Research 7, 617-628, 1982.
31
[11] Roth, A.E., Sotomayor, M., Two-sided Matching: A Study in Game-Theoretic Modeling
and Analysis. New York: Cambridge University Press, 1990.
[12] Roth, A.E., The Economist as Engineer: Game Theory, Experimentation, and
Computation as Tools for Design Economics, Econometrica., 70(4), 1341—1378, 2003.
[13] Roth, A.E., Sotomayor, M.A.O., Two-sided Matching: A Study in Game-theoretic
Modeling and Analysis, Cambridge, N. Y.: Cambridge University Press, 1992.
[14] Suksompong, W., Individual and Group Stability in Neutral Restrictions of Hedonic
Games., Department of Computer Science, Stanford University.
[15] Sung, S.C., and Dimitrov, D. 2007a. On core membership testing for hedonic coalition
formation games. Operations Research Letters, 35(2), 155-158.
[16] Sung, S. C., and Dimitrov, D. 2010. Computational Complexity in Additive Hedonic
Games. European Journal of Operational Research, 203(3), 635-639.
[17] Sung, S. C., and Dimitrov, Dinko. 2007b. On Myopic Stability Concepts for Hedonic
Games. Theory and Decision, 62(1), 31-45.
[18] Алескеров Ф.Т., Кисельгоф С.Г., Лауреаты Нобелевской премии – 2012: Ллойд
Шепли и Элвин Рот., Экономический журнал ВШЭ., 4, 2012.
[19] Железова E., Измалков C., Сонин К., Хованская И., Теория и практика двусторонних рынков., Вопросы экономики., 1, 2013.
[20] Коджаспирова Г. М., Коджаспиров А. Ю., Педагогический словарь: Для студентов
высших и средних педагогических учебных заведений., Издат.центр: «Академия»,
2001.
32
Приложение
В данном приложении содержится текст программы, реализующей алгоритм «Top covering»
для B–игры на языке C#. Программа состоит из основного класса Program, и двух вспомогательных классов NewGame и ForList.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using ConsoleApplication1;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Здравствуйте!");
Console.WriteLine("Данная программа реализует алгоритм Top Covering,");
Console.WriteLine("который генерирует разбиение из ядра для B-игры со строгим списком предпочтений.");
Console.WriteLine("Для создания игры Вам будет нужно указать ");
Console.WriteLine("
количество игроков-участников");
Console.WriteLine("
предпочтения всех игроков");
Console.WriteLine();
Boolean start = true;
while (start)
{
string yes;
Console.WriteLine("Хотите создать игру?");
Console.WriteLine("1-создать игру на консоле, 2-игра из файла, 0-выйти");
yes = Console.ReadLine();
switch (yes)
{
case "0":
start = false;
Console.WriteLine("Press any key to exit.");
Console.ReadKey();
break;
case "1":
NewGame.NGame();
break;
case "2":
NewGame.NGame2();
break;
default:
Console.WriteLine("Вы неправильно ввели данные");
break;
}
Console.ReadLine();
33
}
}
}
}
namespace ConsoleApplication1
{
public static class NewGame
{
//класс для считывания количества игроков при введении игры из консоли
public static void haveN(out int N)
{
N = 0;
Boolean hN = false;
while (hN == false)
{
N = 0;
Console.WriteLine("Введите количество игроков");
string sn= Console.ReadLine();
int i = 0;
while (i < sn.Length)
{
if (sn[i] >= 48 && sn[i] < 58)
{
N = N * 10 + sn[i] - 48; hN = true;
}
else
{
hN = false;
Console.WriteLine("Вы не правильно ввели число");
break;
}
i++;
}
}
}
//считывание игры из текстового файла
public static void NGame2()
{
Console.WriteLine("Введите название текстового файла.");
Console.WriteLine("Каждая строка файла -- ПОЛНЫЙ СТРОГИЙ список предпочтения игрока.");
Console.WriteLine("Игроки списка должны быть разделены пробелом.");
string namefile=Console.ReadLine();
string[] lines = System.IO.File.ReadAllLines(@namefile);
int N=lines.Length;
Boolean[] incoal = new Boolean[N];
int[] Coal = new int[N];
for (int i = 0; i < N; i++)
Coal[i] = 0;
34
List<int>[] P = new List<int>[N];
string S;
for (int i = 0; i < N; i++)
{
Boolean d = true;
do
{
S = lines[i];
P[i] = null;
ForList.StringToList(N, S, out P[i], out d);
} while (d == false);
}
int nk = 0;
int inCoal = 0;
while (N-inCoal > 0)
{
int[,] C = new int[N, N];
ForList.GenCC(N, P, Coal, out C);
int min, imin;
ForList.MinCC(N, C, Coal, out min, out imin);
nk++;
for (int i = 0; i < N; i++)
if (C[imin - 1, i] == 1)
{
Coal[i] = nk;
for (int j1 = 0; j1 < N; j1++)
P[j1].Remove(i + 1);
}
inCoal = inCoal + min;
}
Console.Write("Разбиение ");
for (int j = 1; j <= nk; j++)
{
Console.Write("{");
for (int i = 0; i < N; i++)
if (Coal[i] == j)
Console.Write(i+1);
Console.Write("}");
}
Console.WriteLine(" находится в ядре");
}
//считывание игры с консоли
public static void NGame()
{
int N;
haveN(out N);
Boolean[] incoal = new Boolean[N];
int[] Coal = new int[N];
35
for (int i = 0; i < N; i++)
Coal[i] = 0;
List<int>[] P = new List<int>[N];
string S;
Console.WriteLine("Вводите список игроков ЧЕРЕЗ ПРОБЕЛ в порядке УБЫВАНИЯ предпочтительности");
Console.WriteLine();
for (int i = 0; i < N; i++)
{
Boolean d = true;
do
{
Console.WriteLine("
для игрока {0}", i + 1);
S = Console.ReadLine();
P[i] = null;
ForList.StringToList(N, S, out P[i], out d);
} while (d == false);
}
int nk = 0;
int inCoal = 0;
while (N - inCoal > 0)
{
int[,] C = new int[N, N];
ForList.GenCC(N, P, Coal, out C);
int min, imin;
ForList.MinCC(N, C, Coal, out min, out imin);
nk++;
for (int i = 0; i < N; i++)
if (C[imin - 1, i] == 1)
{
Coal[i] = nk;
for (int j1 = 0; j1 < N; j1++)
P[j1].Remove(i + 1);
}
inCoal = inCoal + min;
}
Console.Write("Разбиение ");
for (int j = 1; j <= nk; j++)
{
Console.Write("{");
for (int i = 0; i < N; i++)
if (Coal[i] == j)
Console.Write(i + 1);
Console.Write("}");
}
Console.WriteLine(" находится в ядре");
}
}
}
namespace ConsoleApplication1
36
{
public class ForList
{
public static void GenCoalList(int N, List<int>[] P,out List<int[]>[] Coal )
{
Coal = new List<int[]>[N];
Boolean[] notfull = new Boolean[N];
for (int i = 0; i < N; i++)
notfull[i] = true;
for (int i = 0; i < N; i++)
{
for (int j = 1; j <= N; j++)
{
Coal[i][j] = new int[N];
}
}
}
//преобразование введенных данных в списки предпочтений игроков
public static void StringToList(int N, string ss,out List<int> list,out Boolean d)
{
string s = ss;
while (s[0] == ’ ’)
s = s.Substring(1);
list = new List<int>(N);
d = true;
string els = "";
Boolean[] P = new Boolean[N];
for (int i = 0; i < N; i++)
{
P[i] = false;
}
Boolean elYes = true;
for (int i = 0; i < s.Length; i++)
{
if ((s[i] < 48 || s[i] > 57) && s[i] != ’ ’)
{
Console.WriteLine("Данные введены не правильно");
elYes = false;
break;
}
else
{
if (s[i] != ’ ’)
{
els += s[i];
if (Convert.ToInt32(els) > N)
{
Console.WriteLine("Данные введены не правильно");
elYes = false;
37
}
}
else
{
int el = Convert.ToInt32(els);
if (P[el-1])
{
d = false;
}
else
{
P[el-1] = true;
list.Add(el);
}
els = "";
}
}
if (elYes==false)
{
break;
}
}
if (elYes)
{
if (els != "")
{
int el = Convert.ToInt32(els);
if (P[el-1])
{
d = false;
}
else
{
P[el-1] = true;
list.Add(el);
}
}
for (int i = 0; i < N; i++)
{
if (P[i] == false)
{
d = false;
}
}
}
else d = false;
}
38
//генерация СС
public static void GenCC(int N,List <int>[] P,int[] coal, out int[,] C )
{
int j;
C = new int[N, N];
int i;
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
{
C[i, j] = 0;
}
}
for (i = 0; i < coal.Length; i++)
{
C[i, i] = 1;
j = P[i][0] - 1;
while (C[i, j] == 0)
{
C[i, j] = 1;
j = P[j][0] - 1;
}
}
}
//нахождение минимальной CC
public static void MinCC(int N,int[,] C,int[] coal,out int min,out int imin)
{
min = N; imin = 0;
int m = 0;
for (int i = 0; i < N; i++)
{
if (coal[i] == 0)
{
for (int j = 0; j < N; j++)
{
m += C[i, j];
}
if (m < min)
{
imin = i; min = m;
}
m = 0;
}
}
imin++;
}
}
}
39
Отзывы:
Авторизуйтесь, чтобы оставить отзыв