Гомоморфизмы и конгруэнции игр с отношениями предпочтения

1. В классической теории принятия решений и в теории игр основным способом формализации целевой структуры является задание целевой функции (функции выигрыша). При этом цель отождествляется с максимизацией или минимизацией этой функции в зависимости от ее содержания с точки зрения лица, принимающего решение. В прикладных задачах физического или технического содержания целевая функция иногда получается внешним образом или из теоретических соображений. Однако при построении целевой функции в реальных моделях принятия решений возникает ряд сложностей как принципиального, так и технического характера.

Как. известно, на практике объекты (состояния, ситуации) обычно оцениваются по нескольким показателям (критериям) качества. В литературе по принятию решений для оценки объекта используется «дерево критериев», что отражает иерархическую структуру подчиненности критериев. При таком подходе набор критериев должен обладать следующими свойствами (см. Мендель [22]),.

Полнота. Набор критериев должен содержать критерии, позволяющие охарактеризовать все основные аспекты оценки объекта.

Действенность (операционность). Критерии должны быть однозначно понимаемыми и способствовать выработке и принятию эффективных решений.

Разложимость. Возможность разбиения критериев на более мелкие группы.

Неизбыточность. Исключение возможности дублирования критериев.

Минимальная размерность. В набор критериев для оценки объекта должны быть включены только те, без которых адекватная оценка невозможна.

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

Целевая функция представляет собой единый (интегральный) показатель эффективности, поэтому для ее задания необходимо «свернуть» все имеющиеся критерии в один. На практике эта задача решается разными способами. Например, каждому показателю приписывают некоторый «вес», выражающий значимость этого показателя, и рассматривают в качестве оценки объекта взвешенную сумму. Однако в практических ситуациях выбор «весов» осуществить достаточно сложно. «Вес» должен быть постоянным для каждого показателя, но, как правило, невозможно заранее указать, во сколько раз один показатель важнее другого. В настоящее время проблема «свертывания» векторного критерия в скалярный превратилась в самостоятельное направление, по которому имеется обширная литература (см. например, [20, 27, 37]). Один из способов решения данной задачи — лексикографическое упорядочение. Критерии (показатели) в этом способе должны быть упорядочены по относительной важности (например, см. [34]). В работе [40] выяснена возможность построения единого (обобщенного) критерия на базе некоторой дополнительной информации об относительной важности этих критериев для лица, принимающего решение. В качестве такой информации выступает задание в рассматриваемой области карты безразличий или равносильная информация — задание локального коэффициента замещения.

В связи с указанными сложностями при построении целевых функций возник альтернативный подход, состоящий в том, что объекты оцениваются не с помощью числовой функции, а по отношению предпочтения. В этом случае при построении модели принятия решения надо задать отношение предпочтения (или структуру «доминирование-безразличие») на множестве объектов, а именно указать совокупность всех пар объектов, в которых один объект предпочтительнее другого для принимающего решение.

На «практике используются следующие основные способы выявления предпочтений на множестве объектов.

Метод попарных сравнений.

В некоторых случаях этот метод реализуется на базе субъективных представлений индивидуума об исследуемых объектах. А именно, для каждой пары объектов индивидуум должен указать более предпочтительный в этой паре. Если для какой-нибудь пары он затрудняется это сделать, индивидуум вправе считать сравниваемые объекты равноценными либо несравнимыми. На многочисленных опытах показано, что субъективное предпочтение обычно бывает нелинейным (т.е. некоторые объекты несравнимы друг с другом) и нетранзитивным [16], а иногда содержит циклы (контура). Результатом такого сравнения будет матрица предпочтений или граф предпочтений.

Разновидностью этого подхода является метод, в котором объекты сравниваются по инструментальному или опытному признаку (например, взвешивание или проведение турнира, выявляющего победителя).

Основной метод сравнения объектов базируется на таблице значений их признаков (показателей). В этом случае объект рассматривается как набор соответствующих ему значений признаков, а не как единое целое, что имеет место при методе попарных сравнений.

Для математических моделей, изучаемых в настоящей работе, этот метод может быть описан следующим образом. Каждый критерий (признак) измеряется в порядковой шкале (т.е. пункты шкалы — элементы некоторого линейно упорядоченного множества), а измерение состоит в сопоставлении объекту некоторого пункта шкалы и определено с точностью до монотонно возрастающей функции.

Итак, задана таблица значений признаков, где а, 1,., ап — данные объектыр,., рп — введенные для них признаки (критерии) — Pj (щ) — значение критерия р^ для объекта а* {'] = 1,., гаг = 1,., п). Формально Pj (а) = с € где С) — линейно упорядоченное множество. объекты критерии VI Рз Ргп а>1 р М Рз М Рт.

Р (щ) Рз М Рт (а") ап Рг (ап) Рз К) Рт (ап).

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

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

Таким образом, отказываясь от числового описания объектов, мы заменяем его заданием отношения предпочтения, которое в общем случае является рефлексивным бинарным отношением и может не обладать привычными свойствами транзитивности и линейности.

2. Реакцией на сложности построения целевых функций явилось появление в теории игр на рубеже 50−60-х годов ряда работ, в которых целевая (оценочная) структура задачи принятия решений задается не с помощью целевой функции, а с помощью отношений предпочтения игроков. Начиная с фундаментальной монографии Неймана и Моргенштерна [26] в теории игр рассматриваются вопросы существования и нахождения С-ядра и решения (по Нейману-Моргенштерну) для произвольных бинарных отношений, а также для отношений, удовлетворяющих дополнительным условиям: транзитивность, ацикличность, частичный порядок и т. д. Это направление отражено в частности в работах Бержа [5,6], Араксляна [1−4] и др.

Промежуточным классом между классическими играми с функциями выигрыша и играми с отношениями предпочтения является класс игр с векторными выигрышами (здесь свойство транзитивности сохраняется, а свойство линейности не имеет места) [24,59,65].

Различные аспекты теории игр с отношениями предпочтения исследовались в работах как зарубежных авторов (Р. Фаркуарсон [57], Р. Ауман [55,56], Б. Пелег [61], П. Фишберн [58]), так и отечественных ученых (Э. Й. Вилкас [11−14], Б. Б. Яновская [53,54], О. Н. Бондарева [9], Т. Е. Кулаковская [19], Б. Г. Миркин [23], В. В. Подиповский [35,36],.

В. В. Розен [38,39,41−46]).

Можно выделить следующие направления, активно развивающиеся в последние десятилетия в теории игр с отношениями предпочтения: выработка принципов оптимальности для классов игр с отношениями предпочтениянахождение условий существования решений игр как в чистых, так и в смешанных стратегияхразработка кооперативной теории для игр с отношениями предпочтенияперенос важнейших понятий теории игр с функциями выигрыша игроков на игры с отношениями предпочтения (нижняя и верхняя цена игры, обобщение соотношения максимина, ситуации равновесия, характеристическая функция игры, построение смешанного расширения игры и другие). В. В. Подиновский [35] предлагает новые формулировки принципа максимина для антагонистической игры с частичными (нелинейными) отношениями предпочтения. О. В. Шимельфениг в работе [51] рассматривает игры на графах, в которых правило игры и предпочтения игроков заданы бинарными отношениями между элементами базисного множества. В этой работе получены необходимые и достаточные условия того, что гомоморфный образ игры определенного типа будет игрой того же типа. Достаточные условия существования индивидуально-рационального исхода и непустоты множества дележей в игре с квазиупорядоченными исходами найдены М. В. Пасечник в статье [28]. В работах В. В. Розепа [38,39,41−48,62−64] была построена теория игр с упорядоченными исходами, для которых важнейшим свойством предпочтения является его транзитивность. В то же время некоторые типы решающих правил приводят к предпочтениям, не обладающим свойством транзитивности.

3. В данной диссертационной работе основной изучаемой моделью является игра фиксированного множества игроков N = {1,., п} с отношениями предпочтения вида: 6? = ((Хг-)^еЛГ, Л, (/?г)г?ЛГ, .Р), где Хг — множество стратегий игрока г (г е ./V), А — множество исходов, Рг — рефлексивное бинарное отношение на А, выражающее предпочтения игрока г, Р — отображение множества ситуаций X = х. х Хп в множество исходов А, называемое функцией реализации.

Подсистема ((Хг)ге^Г, А, Р) представляет собой реализационную структуру, а подсистема (А, (Pi)ieN) — оценочную структуру игры G. Предполагается, что п ^ 2- Хг ^ 2 (i? N), А ^ 2. Никаких других ограничений на мощности множеств Хг и A a priori не накладывается.

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

Основным инструментом исследования в данной диссертации являются гомоморфизмы и конгруэнции игр. В работе введены различные типы гомоморфизмов игр: строгие, реверсивные, взаимные, точные. В главе 1 доказаны структурные теоремы о гомоморфизмах игр с отношениями предпочтенияв частности, охарактеризованы конгруэнции, факторизации по которым приводят к гомоморфизмам указанных видов. Указаны необходимые и достаточные условия вложимости игры с отношениями предпочтения в класс игр с функциями выигрыша. В главе 2 получено достаточное условие непустоты множества допустимых исходов игры с отношениями предпочтения. Для всех вышеперечисленных типов оптимальных решений найдены ковариантные и контравариантные гомоморфизмы. Для некоторых видов оптимальных решений построены полные семейства гомоморфизмов, что позволяет дать точное описание оптимальных решений игр одного класса через оптимальные решения игр другого класса. В главе 3 для коалиционных принципов оптимальности при фиксированном правиле согласования предпочтений игроков указаны типы гомоморфизмов, удовлетворяющие условию коили контравариантности.

1. Аракелян А. А. Решение для системы нерефлексивных, транзитивных отношений, заданных в метрическом пространстве. // Ученые записки. — Ереван: Изд-во Ереван, ун-та, 1973. № 1. С. 115−119.

2. Аракелян А. А. Гомоморфизмы и решения произведений релятивов. // Математические вопросы кибернетики и вычислительной техники. XI. Автоматизация проетирования и численные методы. — Ереван: Изд-во АН Армянской ССР, 1982. С. 108−115.

3. Аракелян А. А. Нерефлексивные отношения в компактом пространстве множеств. // Доклады АН Армянской ССР. Том 1ЛУ, № 1. С. 3−7.

4. Аракелян А. А. О представлении задач принятия решений. // Доклады АН Армянской ССР. Том ЬХ1Х, № 3, 1979. С. 135−139.

5. Берж К. Общая теория игр нескольких лиц. Пер. с франц. под ред. В. Ф. Колчина. — М.: ФМ, 1961.

6. Берж К. Теория графов и ее применения. Пер. с франц. под ред. И. А. Вайпштейна. — М.: ИЛ, 1962.

7. Биркгоф Г. Теория решеток. Пер. с англ. — М.: Наука, 1984. — 568 с.

8. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. — М., Наука. Физматлит, 1997. — 368 с.

9. Бондарева О. Н. Решение и ядро ациклического отношения на Компакте. // Успехи теории игр. — Вильнюс, 1973. С. 127−130.

10. Вагнер В. В. Теория отношений и алгебра частичных отобраэ/сений. // Теория полугрупп и ее приложения. — Саратов: Изд-во Сарат. ун-та, 1965. Вып. 1. С. 3−178.

11. Вилкас Э. Й. Многоцелевая оптимизация. // Матем. методы в социальных науках, вып. 7. — Вильнюс, изд. ин-та физики и математики АН Лит. ССР, 1976. С. 17−68.

12. Вилкас Э. Й. Оптимальность в играх и решениях. — М.: Наука. Гл. ред. физ.-мат. лит., 1990. — 256 с.

13. Вилкас Э. Й. Понятия оптимальности в теории игр. // Современные направления теории игр. — Вильнюс, МОКСЛАС, 1976. С. 25−43.

14. Вилкас Э. Й., Майминас Е. 3. Решения: теория, информация, моделирование. — М.: Радио и связь, 1981.

15. Воробьев Н. Н. Современное состояние теории игр. — УМН, т. XXV, вып. 2 (152), 1970. С. 81−140.

16. Гранберг А. А. Проблема транзитивности индивидуальных и коллективных предпочтений при построении целевых функций. В кн.: Количественные методы в социологии. — М.: Наука, 1966. С. 70−92.

17. Кирута А. Я., Рубинов А. М., Яновская Е. Б. Оптимальный выбор распределений в сложных социально-экономических задачах. — Л.: Наука ЛО, 1980.

18. Кукушкин Н. С., Морозов В. В. Теория неантагонистических игр.- М.: Изд-во МГУ, 1984. 104 с.

19. Кулаковская Т. Е. Классические принципы оптимальности для бесконечных кооперативных игр. // Современные направления теории игр. Вильнюс, МОКСЛАС, 1976. С. 94−108.

20. Лотов А. В.

Введение

в экономико-математическое моделирование.-М.: Наука, 1984. — 392 с.

21. Льюс Р., Райфа X. Игры и решения. Пер. с англ. под ред. Д. Б. Юдина. — М.: ИЛ, 1961.

22. Мендель А. В. Модели принятия решений: учеб. пособие для студентов вузов, обучающихся по направлениям «Экономика» и «Менеджмент» / А. В. Мендель. — М.: ЮНИТИ-ДАНА, 2010. — 463 с.

23. Миркин Б. Г. Проблема группового выбора. — М.: Наука, 1979.

24. Морозов В. В. Смешанные стратегии в игре с векторными выигрышами. // Вестн. МГУ, Вычисл. матем. и кибернетика, № 4, 1978. С. 44−49.

25. Мулен Э. Теория игр с примерами из математической экономики. Пер. с франц. — М.: Мир, 1985. — 200 с.

26. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. Пер. с англ. под ред. H. Н. Воробьева. — М.: Наука, 1970. — 708 с.

27. Ногин В. Д. Принятие решений в многокритериальной среде: количественный подход. — М.: Физматлит, 2002. — 176 с.

28. Пасечник М. В. Дележи в бескоалиционных играх с квазиупорядоченными исходами. // Сб. науч. тр. Механика. Математика, Саратов: Изд-во Сарат. ун-та, 2002. С. 114−117.

29. Пасечник М. В. Исходы, допустимые для семейства коалиций в игре с квазиупорядоченными исходами. // Сб. науч. тр. Механика. Математика, Саратов: Изд-во Сарат. ун-та, 2005. С. 93−95.

30. Петросян Л. А. Дифференциальные игры преследования. — Л.: Изд-во Ленингр. ун-та, 1977. — 224 с.

31. Петросян Л. А., Захаров В. В.

Введение

в математическую экологию. — Л.: Изд-во Ленингр. ун-та, 1986. — 224 с.

32. Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр. — М.: Книжный дом. Университет Высшая школа. — 1998. — 301 с.

33. Петросян Л. А., Томский Г. В. Дифференциальные игры с неполной информацией. — Иркутск: Изд-во Иркут. ун-та, 1984. — 188 с.

34. Подиновский В. В. Коэффициенты ваоюности критериев в задачах принятия решений. Порядковые, или ординальные, коэффициенты важности. // Автоматика и телемеханика. — М.: Академия Наук СССР, 10, 1978. С. 130−141.

35. Подиновский В. В. Принцип гарантированного результата для частичных отношений предпочтения. — Ж. вычисл. матем. и матем. физ., 1979, т. 19, № 6. С. 1436−1450.

36. Подиновский В. В. Общие антагонистические игры. — Ж. вычисл. матем. и матем. физ., 1981, т. 21, № 5. С. 1140−1153.

37. Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. — М.: Наука, 1982.

38. Розен В. В. Гомоморфизмы игр с упорядоченными исходами. // Матем. модели поведения. — Саратов, изд. СГУ, 1981. С. 90−104.

39. Розен В. В. Игры с упорядоченными исходами. — Изв. АН СССР, Технич. кибернетика, № 5, 1977. С. 31−37.

40. Розен В. В. Математические модели принятия решений в экономике. — М.: Книжный Дом Университет: Высш. шк., 2002.

41. Розен В. В. Нахождение оптимальных рещений методом построения ковариантпо полных семейств контравариантных гомоморфизмов. Фундаментальные проблемы математики и механики. Математика. — М.: Изд-во Моск. ун-та. 1994. 371 с. С. 349−350.

42. Розен В. В. Общие теоремы о достижимости и минимаксе в позиционных играх. // Матем. модели и методы в социально-экономических исследованиях. — Новосибирск: Изд. ИЗ и ОПП, вып.1, 1968. С. 64−70.

43. Розен В. В. Применение теории бинарных отношений к общей теории игр. // Матем. методы решения экономических задач. — Новосибирск: Наука СО. С. 127−152.

44. Розен В. В. Редуцируемостпъ оптимальных решений игр с упорядоченными исходами. // Теория полугрупп и ее приложения. Вопросы аксиоматизации. 1988. С. 50−60.

45. Розен В. В. Ситуации равновесия в играх с упорядоченными исходами. // Современные направления теории игр. — Вильнюс: МОКСЛАС, 1976. С. 115−118.

46. Розен В. В. Смешанные расширения игр с упорядоченными исходами. — Ж. вычисл. матсм. и матем. физ., 1976, № 6. С. 1436−1450.

47. Розен В. В. Структура отношений предпочтения. Учеб. пособие для слушателей факультета повыш. квалиф. ИДПО. — Саратов: Изд-во Сарат. ун-та, 2007. — 56 с.

48. Розен В. В. Цель оптимальность — решение. М.: Радио и связь, 1982. — 169 с.

49. Фишберн Питер С. Теория полезности для принятия решений. М.: Наука, 1978. — 352 с. с илл.

50. Харшаньи Д., Зельтен Р. Общая теория выбора равновесия в играх. Пер. с англ. под ред. Н. А. Зенкевича. СПб: Экономическая школа, 2001. 424 с.

51. Шимельфениг О. В. Применение алгебры полирелятивов к теории игр. // Сиб. мат. журн., т. XII, № 4, 1971. С. 855−879.

52. Шрейдер Ю. А. Равенство, сходство, порядок. — М.: Наука, Гл. ред. физ.-мат. лит., 1971. — 256 с. с илл.

53. Яновская Е. Б. Ситуации равновесия в играх с неархимедовыми полезностями. // Матем. модели в социальных науках. — Вильнюс, изд. ин-та физики и математики АН Лит. ССР. С. 98−118.

54. Яновская Е. Б. Ситуации равновесия в общих бескоалиционных играх и их смешанных расширениях. // Теоретико-игровые вопросы принятия решений. — Л.: Наука ЛО, 1978. С. 43−64.

55. Aumann R. J. Utility theory without the completeness axiom. — Economet-rica, 1962, v. 30, № 3. P. 445−462.

56. Aumann R. J. Utility theory without the completeness axiom: a correction. Econometrica, 1964, v. 32, № 1−2. P. 210−212.

57. Farquharson R. Sur une generalisation de la notion d! equilibrium. C.r. Acad. sci. Paris, 1955, 240, № 1. P. 46−48.

58. Fishburn Peter C. The Theory of Social Choice. — Princeton University Press. 1973. 264 p.

59. Jentzsch G. Some thoughts on the theory of cooperative games. — Advances in game theory. Ann. Math. Studies, 1964, 52. P. 407−442.

60. Nash J. Non-cooperative games. Ann. of Math.," 54, 1951. P. 286−295.

61. Peleg B. The independence of Game theory of utility theory. Bull, of the Amer. Math. Soc. Vol. 72, № 6, 1966. P. 995−999.

62. Rozen V. V. Cooperative games with ordered outcomes. // Game. Theory and Management. Collected abstracts of papers presented on the Third International Confcrcncc Game Theory and Management. SPb.: Graduate School of Management SPbU, 2009. P. 221−222.

63. Shapley L. S. Equilibrium points in games with vector payoffs. — Naval Res. Logist. Quart, 1959, v. 6, № 1. P. 57−61.Список трудов.

64. Савина Т. Ф. Ковариантпые и контравариантные гомоморфизмы игр с отношениями предпочтения. // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2009. Т. 9, вып. 3. С. 66−70.с.

65. Савина Т. Ф. Оптимальные решения в играх с отношениями предпочтения. // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2011. Т. 11, вып. 2. С. 32−36.

66. Савина Т. Ф. Гомоморфизмы и конгруэнтности игр с транзитивной структурой предпочтений. // Компьютерные науки и информационные технологии: материалы Междунар. науч. конф. Саратов, Россия, 1−4 июля 2009 г. — Саратов: Изд-во Сарат. ун-та, 2009. С. 157−160.

67. Савина Т. Ф. Гомоморфизмы и конгруэнтности игр с отношениями предпочтения. // Сб. науч. тр. Механика. Математика, Саратов: Изд-во Сарат. ун-та, 2009. С. 63−66.

68. Савина Т. Ф. Гомоморфизмы игр с отношениями предпочтения. // Дискретная математика и ее приложения: материалы X Международного семинара, Москва, МГУ, 1−6 февр. 2010. — М.: Изд-во мех.-мат. фак. Моск. ун-та, 2010. С. 426−428.

69. Савина Т. Ф. Равновесные и допустимые исходы для коалиций в игре с отношениями предпочтения. // Сб. науч. тр. Механика. Математика, Саратов: Изд-во Сарат. ун-та, 2010. С. 74−78.