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