Введение
Глава 1. Основные определения
Глава 2. Известные результаты
Глава 3. Лексикографически минимаксное решение . . . . 17
3.1. Условия пропорциональности
3.2. Условия слабой пропорциональности
Глава 4. Эквивалентность решений
Глава 5. Примеры
5.1. Минимальное покрытие
5.2. Системы коалиций для |�| = 4, 5
5.3. Системы коалиций для |�| = 6
Заключение
Список литературы
ДОПУСТИМЫЕ СИСТЕМЫ КОАЛИЦИЙ В ИГРАХ С ОГРАНИЧЕННОЙ КООПЕРАЦИЕЙ
|
Введение
Глава 1. Основные определения
Глава 2. Известные результаты
Глава 3. Лексикографически минимаксное решение . . . . 17
3.1. Условия пропорциональности
3.2. Условия слабой пропорциональности
Глава 4. Эквивалентность решений
Глава 5. Примеры
5.1. Минимальное покрытие
5.2. Системы коалиций для |�| = 4, 5
5.3. Системы коалиций для |�| = 6
Заключение
Список литературы
Задачи «справедливого» дележа в условиях кооперации были поставлены в 1944 г. в книге Джона фон Неймана и Оскара Моргенштерна [1].
В этой работе ставилась задача дележа между игроками из множества �
фиксированной суммы дохода �(�) при условии, что известна сумма дохода �(�), которую может получить подмножество � множества �, если
все его элементы будут действовать сообща. Любое подмножество � множества � называется коалицией. Таким образом, в этой постановке задачи коалицией является не реально действующее множество игроков, а гипотетическое. В рассматриваемой работе предполагалось, что сумма дохода �(�)
задана для любого подмножества � множества �. Однако во многих реальных задачах не все коалиции могут быть реализуемы, и в настоящее
время в теории кооперативных игр в основном рассматриваются задачи с
ограниченной кооперацией.
В связи с этим возникает надежда получать более «естественное» решение задач о «справедливом» дележе при небольшом наборе коалиций.
Кроме того, величины �(�) в ряде задач могут рассматриваться не как
величины, отражающие силу коалиций, а как величины, соответствующие
потребностям этих коалиций.
Наталья Наумова в [2] рассматривала вопрос возможности дележа
суммарного, бесконечно делимого фиксированного ресурса, удовлетворяющего условию пропорциональности как между всеми коалициями, так и
только между непересекающимися коалициями из фиксированного набора коалиций, называемых допустимыми. В случае, когда набор коалиций
является набором только всех одноточечных множеств, пропорциональное
распределение ресурса можно также получить и как решение задачи максимизации взвешенной энтропии, и как решение задач о лексикографически5
максиминном и лексикографически минимаксном векторах. Если набор коалиций не является разбиением множества �, то эти задачи не являются
эквивалентными. Оказывается, что пропорциональное распределение ресурса между всеми допустимыми коалициями при любых положительных �
возможно только если для каждой коалиции существует элемент, принадлежащий только этой коалиции (его можно назвать фанатиком этой коалиции). Аналогично случаю одноточечных допустимых коалиций, если набор всех рассматриваемых коалиций — разбиение множества �, то все эти методы дают одинаковый результат. Кроме того, обобщенное энтропийное
решение и лексикографически максиминное решение всегда содержатся в
пропорциональном только если набор допустимых коалиций — разбиение множества �.
Поэтому в работе [2] условие пропорциональности ослабляется и требуется только пропорциональность для непересекающихся допустимых коалиций. Такие распределения ресурса называются слабо пропорциональными. Там же было описано необходимое и достаточное условие на набор
допустимых коалиций для существования слабо пропорционального решения при любых положительных �. Поскольку обобщенное энтропийное и
лексикографически максиминное решения всегда существуют, возникает
вопрос о возможности их использования в качестве селекторов слабо пропорционального решения. В [3] были получены необходимое и достаточное
условие на набор допустимых коалиций для слабой пропорциональности
обобщенного энтропийного решения и необходимое и достаточное условие
на набор допустимых коалиций для слабой пропорциональности лексикографического максиминного решения. Необходимое и достаточное условие
на систему коалиций для совпадения обобщенного энтропийного решения и
обобщенного максиминного решения неизвестно. В [3] было описано только достаточное условие.
В данной работе для задач описанного выше типа рассматривается
лексикографически минимаксное решение. Получены условия его пропорциональности и слабой пропорциональности, которые не совсем аналогичны известным условиям для лексикографически максиминного решения.
Так, если для набора допустимых коалиций пропорциональное решение
всегда существует, то лексикографически минимаксное решение является
пропорциональным. Для включения лексикографически максиминного решения в слабо пропорциональное в [3] и [4] были получены эквивалентные
условия на набор допустимых коалиций. Однако аналоги этих условий для
минимаксного случая не эквивалентны, только один из аналогов из [4] является необходимым и достаточным условием слабой пропорциональности
лексикографически минимаксного решения.
В работе приводятся примеры, когда условия для слабой пропорциональности для минимаксного и максиминного решения не совпадают, описываются все наборы коалиций, удовлетворяющие полученному условию при |�| 6 6. Кроме того, получено достаточное условие совпадения обобщенного энтропийного решения, обобщенного минимаксного решения и их
слабой пропорциональности (это условие совпадает с достаточным условием для максиминного решения)
В этой работе ставилась задача дележа между игроками из множества �
фиксированной суммы дохода �(�) при условии, что известна сумма дохода �(�), которую может получить подмножество � множества �, если
все его элементы будут действовать сообща. Любое подмножество � множества � называется коалицией. Таким образом, в этой постановке задачи коалицией является не реально действующее множество игроков, а гипотетическое. В рассматриваемой работе предполагалось, что сумма дохода �(�)
задана для любого подмножества � множества �. Однако во многих реальных задачах не все коалиции могут быть реализуемы, и в настоящее
время в теории кооперативных игр в основном рассматриваются задачи с
ограниченной кооперацией.
В связи с этим возникает надежда получать более «естественное» решение задач о «справедливом» дележе при небольшом наборе коалиций.
Кроме того, величины �(�) в ряде задач могут рассматриваться не как
величины, отражающие силу коалиций, а как величины, соответствующие
потребностям этих коалиций.
Наталья Наумова в [2] рассматривала вопрос возможности дележа
суммарного, бесконечно делимого фиксированного ресурса, удовлетворяющего условию пропорциональности как между всеми коалициями, так и
только между непересекающимися коалициями из фиксированного набора коалиций, называемых допустимыми. В случае, когда набор коалиций
является набором только всех одноточечных множеств, пропорциональное
распределение ресурса можно также получить и как решение задачи максимизации взвешенной энтропии, и как решение задач о лексикографически5
максиминном и лексикографически минимаксном векторах. Если набор коалиций не является разбиением множества �, то эти задачи не являются
эквивалентными. Оказывается, что пропорциональное распределение ресурса между всеми допустимыми коалициями при любых положительных �
возможно только если для каждой коалиции существует элемент, принадлежащий только этой коалиции (его можно назвать фанатиком этой коалиции). Аналогично случаю одноточечных допустимых коалиций, если набор всех рассматриваемых коалиций — разбиение множества �, то все эти методы дают одинаковый результат. Кроме того, обобщенное энтропийное
решение и лексикографически максиминное решение всегда содержатся в
пропорциональном только если набор допустимых коалиций — разбиение множества �.
Поэтому в работе [2] условие пропорциональности ослабляется и требуется только пропорциональность для непересекающихся допустимых коалиций. Такие распределения ресурса называются слабо пропорциональными. Там же было описано необходимое и достаточное условие на набор
допустимых коалиций для существования слабо пропорционального решения при любых положительных �. Поскольку обобщенное энтропийное и
лексикографически максиминное решения всегда существуют, возникает
вопрос о возможности их использования в качестве селекторов слабо пропорционального решения. В [3] были получены необходимое и достаточное
условие на набор допустимых коалиций для слабой пропорциональности
обобщенного энтропийного решения и необходимое и достаточное условие
на набор допустимых коалиций для слабой пропорциональности лексикографического максиминного решения. Необходимое и достаточное условие
на систему коалиций для совпадения обобщенного энтропийного решения и
обобщенного максиминного решения неизвестно. В [3] было описано только достаточное условие.
В данной работе для задач описанного выше типа рассматривается
лексикографически минимаксное решение. Получены условия его пропорциональности и слабой пропорциональности, которые не совсем аналогичны известным условиям для лексикографически максиминного решения.
Так, если для набора допустимых коалиций пропорциональное решение
всегда существует, то лексикографически минимаксное решение является
пропорциональным. Для включения лексикографически максиминного решения в слабо пропорциональное в [3] и [4] были получены эквивалентные
условия на набор допустимых коалиций. Однако аналоги этих условий для
минимаксного случая не эквивалентны, только один из аналогов из [4] является необходимым и достаточным условием слабой пропорциональности
лексикографически минимаксного решения.
В работе приводятся примеры, когда условия для слабой пропорциональности для минимаксного и максиминного решения не совпадают, описываются все наборы коалиций, удовлетворяющие полученному условию при |�| 6 6. Кроме того, получено достаточное условие совпадения обобщенного энтропийного решения, обобщенного минимаксного решения и их
слабой пропорциональности (это условие совпадает с достаточным условием для максиминного решения)
В данной работе дан обзор результатов, касающихся селекторов пропорционального и слабо пропорционального решений, а именно: лексикографически максиминного, лексикографически минимаксного и �–решений.
Результаты, касающиеся лексикографически минимаксного решения,
являются новыми. Получены условия включения лексикографически минимаксного решения в пропорциональное и слабо пропорцинальное, а также
условия эквивалентности с другими рассматриваемыми решениями.
Несмотря на внешнее сходство лексикографически минимаксного и
лексикографически максиминного решений, условия их пропорциональности и слабой пропорциональности не аналогичны.
Кроме того, при |�| 6 6 рассмотрены все наборы коалиций, для которых слабо пропорциональное решение непусто. Для каждого набора указано, являются ли лексикографически минимаксные и лексикографически максиминные решения слабо пропорцинальными
Результаты, касающиеся лексикографически минимаксного решения,
являются новыми. Получены условия включения лексикографически минимаксного решения в пропорциональное и слабо пропорцинальное, а также
условия эквивалентности с другими рассматриваемыми решениями.
Несмотря на внешнее сходство лексикографически минимаксного и
лексикографически максиминного решений, условия их пропорциональности и слабой пропорциональности не аналогичны.
Кроме того, при |�| 6 6 рассмотрены все наборы коалиций, для которых слабо пропорциональное решение непусто. Для каждого набора указано, являются ли лексикографически минимаксные и лексикографически максиминные решения слабо пропорцинальными
Подобные работы
- ДОПУСТИМЫЕ СИСТЕМЫ КОАЛИЦИЙ в ИГРАХ С ОГРАНИЧЕННОЙ КООПЕРАЦИЕЙ
Дипломные работы, ВКР, информатика. Язык работы: Русский. Цена: 4300 р. Год сдачи: 2017 - ТЕОРЕТИКО-ИГРОВЫЕ МЕТОДЫ АНАЛИЗА УСТОЙЧИВОСТИ В ЗАДАЧАХ УПРАВЛЕНИЯ ЗАГРЯЗНЕНИЕМ ОКРУЖАЮЩЕЙ СРЕДЫ
Диссертация , информатика. Язык работы: Русский. Цена: 770 р. Год сдачи: 2024 - Теоретико-игровые модели процессов инвестирования в задачах размещения при неполноте информации и множественных интересов участвующих агентов
Магистерская диссертация, информатика. Язык работы: Русский. Цена: 5500 р. Год сдачи: 2020