Поиск эксцессоподобных решений с помощью метода минимизации лексикографической разницы | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 15 августа, печатный экземпляр отправим 2 сентября.

Опубликовать статью в журнале

Библиографическое описание:

Поиск эксцессоподобных решений с помощью метода минимизации лексикографической разницы / А. А. Тарасов, О. А. Кащеева, Д. Л. Павлов [и др.]. — Текст : непосредственный // Молодой ученый. — 2020. — № 26 (316). — С. 9-12. — URL: https://moluch.ru/archive/316/72154/ (дата обращения: 07.08.2020).



В теории кооперативных игр с трансферабельными полезностями особое место занимают решения, основанные на эксцессах коалиций. Для нахождения решений подобных N-ядру, требуются нахождение лексикографически минимального вектора среди всех векторов эксцессов, упорядоченных по неубыванию [1]. Это создает множество проблем, поскольку поиск такого вектора является крайне нетривиальной задачей, и часто такие решения находят вручную. В данной статье представлен программный метод нахождения эксцессоподобных решений, основанный на функции лексикографической разницы.

Ключевые слова: кооперативные игры, эксцессоподобные решения, N-ядро, эксцесс коалиции, лексикографическая разница, метод поиска решений.

Существует множество способов программного поиска эксцессоподобных решений — метод перебора, решение задачи линейного программирования [2] и другие. Но семейство кооперативных игр огромно, и во многих случаях известные методы решений могут оказаться слишком трудозатратными или же попросту неподходящими для конкретного вида кооперативной игры.

Поиск эксцессоподобных решений достаточно важная задача в силу особенности таких решений. Данные решения интересны тем, что минимизируют неудовлетворенности коалиций, что позволяет в некоторых случаях найти более справедливые выигрыши для игроков.

В данной работе будет рассматриваться поиск решений, которые дают лексикографически минимальный вектор эксцессов коалиций кооперативной игры. Данный метод подойдет для поиска N-ядра, SM-ядра [3], интервального N-ядра [4] и других подобных решений.

Эксцессом коалиции кооперативной игры будем называть

где , — выигрыш коалиции.

Метод минимизации лексикографической разницы

Идея данного метода заключается в минимизации функции лексикографической разницы вектора эксцессов коалиций предыдущего решения с вектором эксцессов текущего. Под лексикографической разницей в данной работе понимается следующая функция:

где , — компоненты векторов и соответственно.

Рассмотрим задачу подробнее:

— вектор эксцессов коалиций кооперативной игры, упорядоченный по невозрастанию, от решения .

В данном случае — решение игры, принадлежащее некоторому множеству . Это может быть множество допустимых решений, множество дележей или какое-либо другое множество, характеризующее искомое решение.

— компоненты вектора .

— лексикографически минимальный вектор эксцессов, упорядоченный по невозрастанию, на -ом шаге.

Перейдем к самому алгоритму. На 0 шаге:

На 1 шаге:

На -ом шаге:

Критерий останова:

Алгоритм следует закончить на -ом шаге при , где — заданная точность, или же после достижения определенного количества шагов. Решением будет вектор .

Неплохим методом для решения такой задачи показался метод последовательного программирования наименьших квадратов, поскольку он последовательно решает задачи квадратичного программирования, аппроксимирующие основную задачу оптимизации [5].

Пример

Рассмотрим интервальную кооперативную игру, представленную в таблице 1.

Таблица 1

Пример интервальной кооперативной игры

1

0

0

4

6

2

0

0

4

6

3

0

0

4

6

4

0

0

6

8

1,2

2

2

8

10

1,3

0

0

8

10

1,4

2

2

8

10

2,3

2

2

8

10

2,4

2

2

10

12

3,4

2

2

8

10

1,2,3

4

4

10

12

1,2,4

6

6

10

12

1,3,4

6

6

10

12

2,3,4

6

6

10

12

10

12

10

12

N-ядро для нижней граничной игры:

N-ядро для верхней граничной игры:

Интервальное N-ядро:

SM-ядро для нижней граничной игры:

SM-ядро для верхней граничной игры:

Интервальное SM-ядро:

Результаты работы алгоритма:

N-ядро для нижней граничной игры: .

N-ядро для верхней граничной игры: .

Интервальное N-ядро:

SM-ядро для нижней граничной игры: .

SM-ядро для верхней граничной игры: .

Интервальное SM-ядро:

Литература:

  1. Печерский С. Л., Яновская Е. Б. Кооперативные игры: решения и аксиомы. М.: Европейский университет в Санкт-Петербурге, 2004.
  2. Сергей В. Бритвин, Светлана И. Тарашнина, Алгоритмы нахождения пред-N-ядра и SM-ядра в кооперативных ТП-играх, МТИП, 2013, том 5, выпуск 4, 14–32
  3. Tarashnina S. I., The simplified modified nucleolus of a cooperative TU-game //Top, 2011, T.19, C. 150–166.
  4. Elena B. Yanovskaya, The Nucleolus and the $\tau$-value of Interval Games // Contributions to Game Theory and Management, 2010, Volume 3, P.421–430.
  5. Sequential quadratic programming, https://en.wikipedia.org/wiki/Sequential_quadratic_programming
Основные термины (генерируются автоматически): кооперативная игра, лексикографическая разница, нижняя граничная игра, решение, верхняя граничная игра, интервальная кооперативная игра, интервальное N-ядро, интервальное SM-ядро, вектор эксцессов, эксцесс коалиции.


Ключевые слова

кооперативные игры, эксцессоподобные решения, N-ядро, эксцесс коалиции, лексикографическая разница, метод поиска решений

Похожие статьи

Аппарат теории кооперативных игр в моделировании...

Наиболее часто используемыми решениями кооперативных игр являются С-ядро, N-ядро, вектор Шепли, переговорное множество, K-ядро. Понятия решений в кооперативных играх так или иначе связаны с идеей устойчивости дележей, т.е. отсутствием у игроков мотивов или...

Сравнение принципов оптимальности для кооперативных игр на...

Введение. В обыкновенной теории кооперативных игр принято, что игроки не ограничены в кооперации и могут образовывать коалиции с любыми игроками. Но в реальной жизни не всегда такое возможно. Чаще существуют какие-либо ограничения на кооперацию.

Построение многошаговой игры для би-кооперативной игры

Ключевые слова: многошаговая игра, би-кооперативные игры. Добыча и распределение ограниченных ресурсов является затратным процессом, поэтому привлечение нескольких игроков облегчает решение данной проблемы с одной стороны.

Применение методов теории кооперативных игр в генетике

Другое решение кооперативной игры — индекс Банзафа: MSC-вектор[5]— принцип оптимальности

Таким образом, можем сделать вывод, что кооперативная теория игр может применяться для микрочиповых игр, например вектор Шепли и индекс Банзафа.

Применение свойств матричных норм к реализуемости...

называют верхними граничными реализациями последовательности (1). 3. Методы решения.

Теорема о граничных реализациях. Если для нижней и верхней граничных реализаций одинаковой размерности и некоторой последовательности интервальных матриц...

Создание и использование программы для статистического...

Первое значение является нижней ценой игры и минимальным гарантированным выигрышем первого игрока, второе — верхней ценой игры и максимальным значением проигрыша второго игрока. Если нижняя и верхняя границы совпадают — это значение является седловой точкой...

Решение интервальной задачи дробно-линейного...

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного

Верхняя граничная задача задачи (3), (4) может быть получена при замене всех

Решение нижней граничной задачи дает максимальное значение ее целевой функции...

Решение общей марковской игры путем аппроксимации ее игрой...

Процесс игры определяется следующим образом. Пусть на очередном шаге разыгрывается игра-компонента Гi (игра находится в состоянии i). Игрок I и II независимо выбирают строку k

Верхнее и нижнее значения игры Γ определяются следующими N-мерными вектор столбцами

Применение методов теории кооперативных игр в генетике

Ключевые слова: коалиционная игра, значение Шепли, MSC-вектор, экспрессия гена, патогенез.

Таким образом, можем сделать вывод, что кооперативная теория игр может применяться для микрочиповых игр, например вектор Шепли и индекс Банзафа.

Теория игр: основные понятия, типы игр, примеры

Из двух типов игр, кооперативные описывают процесс игры в целом, в то время как бескоалиционные рассматривают ситуации в мельчайших подробностях

Например, игроки имеют право объединяться в коалиции, но сама игра будет вестись в бескоалиционном стиле.

Похожие статьи

Аппарат теории кооперативных игр в моделировании...

Наиболее часто используемыми решениями кооперативных игр являются С-ядро, N-ядро, вектор Шепли, переговорное множество, K-ядро. Понятия решений в кооперативных играх так или иначе связаны с идеей устойчивости дележей, т.е. отсутствием у игроков мотивов или...

Сравнение принципов оптимальности для кооперативных игр на...

Введение. В обыкновенной теории кооперативных игр принято, что игроки не ограничены в кооперации и могут образовывать коалиции с любыми игроками. Но в реальной жизни не всегда такое возможно. Чаще существуют какие-либо ограничения на кооперацию.

Построение многошаговой игры для би-кооперативной игры

Ключевые слова: многошаговая игра, би-кооперативные игры. Добыча и распределение ограниченных ресурсов является затратным процессом, поэтому привлечение нескольких игроков облегчает решение данной проблемы с одной стороны.

Применение методов теории кооперативных игр в генетике

Другое решение кооперативной игры — индекс Банзафа: MSC-вектор[5]— принцип оптимальности

Таким образом, можем сделать вывод, что кооперативная теория игр может применяться для микрочиповых игр, например вектор Шепли и индекс Банзафа.

Применение свойств матричных норм к реализуемости...

называют верхними граничными реализациями последовательности (1). 3. Методы решения.

Теорема о граничных реализациях. Если для нижней и верхней граничных реализаций одинаковой размерности и некоторой последовательности интервальных матриц...

Создание и использование программы для статистического...

Первое значение является нижней ценой игры и минимальным гарантированным выигрышем первого игрока, второе — верхней ценой игры и максимальным значением проигрыша второго игрока. Если нижняя и верхняя границы совпадают — это значение является седловой точкой...

Решение интервальной задачи дробно-линейного...

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного

Верхняя граничная задача задачи (3), (4) может быть получена при замене всех

Решение нижней граничной задачи дает максимальное значение ее целевой функции...

Решение общей марковской игры путем аппроксимации ее игрой...

Процесс игры определяется следующим образом. Пусть на очередном шаге разыгрывается игра-компонента Гi (игра находится в состоянии i). Игрок I и II независимо выбирают строку k

Верхнее и нижнее значения игры Γ определяются следующими N-мерными вектор столбцами

Применение методов теории кооперативных игр в генетике

Ключевые слова: коалиционная игра, значение Шепли, MSC-вектор, экспрессия гена, патогенез.

Таким образом, можем сделать вывод, что кооперативная теория игр может применяться для микрочиповых игр, например вектор Шепли и индекс Банзафа.

Теория игр: основные понятия, типы игр, примеры

Из двух типов игр, кооперативные описывают процесс игры в целом, в то время как бескоалиционные рассматривают ситуации в мельчайших подробностях

Например, игроки имеют право объединяться в коалиции, но сама игра будет вестись в бескоалиционном стиле.

Задать вопрос