Концепции решений в задаче коллективного выбора тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Субочев, Андрей Николаевич

• Субочев, Андрей Николаевич
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Субочев, Андрей Николаевич

Аннотация

Введение

Глава 1. Постановка задачи коллективного выбора. Обзор концепций ее решений

1.1 Отношение мажоритарного доминирования и связанные с ним понятия

1.2 Доминирующее, недоминируемое и незапертое множества

1.3 Непокрытое и незахваченное множества

1.4 Слабоустойчивое множество

Глава 2. Сравнительный анализ основных решений, строящихся с помощью отношения мажоритарного доминирования

Глава 3. Концепции классов k-устойчивых альтернатив и к-устойчивых множеств

3.1 к-устойчивые альтернативы

3.2 к-устойчивые множества

Глава 4. Матрично-векторное представление решений и его компьютерная реализация

4.1 Матрично-векторное представление множеств и отношений: основные определения

4.2 Отношения ц, т и и. Победитель Кондорсе и ядро

4.3 Непокрытое множество

4.4 Незахваченное множество

4.5 Минимальное доминирующее, минимальное недоминируемое и незапертое множества

4.6 Минимальное слабоустойчивое множество

4.7 Новые версии непокрытого и слабоустойчивого множеств

4.8 Классы k-устойчивых альтернатив и к-устойчивых множеств

4.9 Оценка сложности вычислений решений с помощью формул их матрично-векторного представления

4.10 Компьютерная реализация вычислений решений с помощью формул их матрично-векторного представления

Введение диссертации (часть автореферата) на тему «Концепции решений в задаче коллективного выбора»

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

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

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

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

1. устанавливаются взаимные соотношения между этими множествами;

2. обобщаются концепции минимального доминирующего множества, непокрытого множества, минимального слабоустойчивого множества;

3. устанавливается соотношение этих обобщений с другими решениями;

4. строится матрично-векторное представление всех рассмотренных множеств-решений, определяющее алгоритм их вычисления.

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

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

Научная новизна. В ходе решения поставленных задач получены следующие новые результаты.

1. Сформулирован критерий, с помощью которого проверяется принадлежность любой альтернативы минимальному слабоустойчивому множеству. С его помощью установлено, что непокрытое множество является подмножеством объединения минимальных слабоустойчивых множеств;

2. Построены обобщения минимального доминирующего множества, и с их помощью выяснено, как устроена система доминирующих множеств.

3. Установлены новые соотношения между множествами-решениями.

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

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

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

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

Теоретическая и практическая значимость. Теоретическая ценность работы состоит в том, что выполнен исчерпывающий анализ и дано последовательное и единообразное описание известных множеств-решений. При этом описать удалось практически все известные решения, строящиеся с помощью отношения мажоритарного доминирования, (кроме двух). Используемое описание также позволило предложить новые версии концепций решений, ранее в литературе не рассматривавшиеся. Результаты работы использовались при обновлении программы учебной дисциплины "Методы анализа политических процессов", читаемой студентам 2 курса бакалавриата факультета прикладной политологии Государственного университета - Высшей школы экономики, и учебной дисциплины "Теория коллективного выбора", читаемой студентам 4 курса бакалавриата отделения прикладной математики и информатики факультета бизнес-информатики Государственного университета - Высшей школы экономики.

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

Полнота изложения материалов диссертации в публикациях.

Результаты диссертации были изложены в следующих публикациях:

Работы, опубликованные в* ведущих рецензируемых научных журналах и журналах, рекомендованных ВАК Министерства образования и науки России:

1. Алескеров Ф.Т., Субочев А.Н. Об устойчивых решениях в ординальной задаче выбора // Доклады Академии Наук. 2009. Т. 426. №3. С. 318-320. 0,35 п.л. (вклад автора 0,28 п.л.)

2. Субочев А.Н. Доминирующие, слабоустойчивые и непокрытые множества: свойства и обобщения // Автоматика и Телемеханика. 2010. №1. 1,00 п.л.

Другие работы, опубликованные по теме диссертации:

3. Subochev A. Dominant, Weakly Stable, Uncovered Sets: Properties and Extensions. Working paper WP7/2008/03. Moscow: State University -Higher School of Economics. 2008. 1,90 п.л.

4. Субочев А.Н. Доминирующие, слабоустойчивые и непокрытые множества: свойства и обобщения // Труды IV Международной конференции по проблемам управления. М.: ИЛУ РАН, 2009. 0,65 п.л

5. Aleskerov F., Subochev A. Matrix-vector representation of various solution concepts. Working paper WP7/2009/03. Moscow: State University -Higher School of Economics, 2009. 2,09 п.л. (вклад автора 1,67 п.л.)

Апробация работы. Основные положения и полученные результаты диссертационной работы прошли апробацию на следующих научных конференциях и семинарах:

1. IX Международная научная конференция "Модернизация экономики и глобализация", ГУ-ВШЭ, Москва, 1-3 апреля 2008 г., доклад "Концепции стабильных множеств альтернатив - равновесных решений игр, связанных с голосованием";

2. Общемосковский научный семинар "Математические методы анализа решений в экономике, бизнесе и политике" (научные руководители д.т.н. Ф.Т. Алескеров, д.т.н. В.В. Подиновский), Москва, 16 апреля 2008 г., доклад "Концепции стабильных множеств альтернатив -равновесных решений игр, связанных с голосованием";

3. Общемосковский научный семинар "Экспертные оценки и анализ данных" (научный руководитель д.т.н. Ф.Т. Алескеров), Институт проблем управления им. Трапезникова РАН, Москва, 23 апреля 2008 г., доклад "Концепции решений и их свойства";

4. Научный семинар "Математическая экономика" (научный руководитель академик РАН В.М. Полтерович), Центральный экономико-математический институт РАН, Москва, 28 октября 2008г., доклад "Множества-решения задачи коллективного выбора: сравнительный анализ";

5. Научный семинар "Теория управления организационными системами" (научный руководитель член-корреспондент РАН д.т.н. Д. А Новиков), Институт проблем управления им. Трапезникова РАН, Москва, 13 ноября 2008 г., доклад "Доминирующее, слабоустойчивое и непокрытое множества: свойства и обобщения";

6. Научный семинар отдела "Математическое моделирование экономических систем" Вычислительного центра РАН (научный руководитель академик РАН А.А. Петров), Москва, 19 ноября 2008 г., доклад "Доминирующее, слабоустойчивое и непокрытое множества: свойства и обобщения";

7. IV Международная конференция по проблемам управления, Институт проблем управления им. Трапезникова РАН, Москва, 26-30 января 2009 г., доклад "Доминирующее, слабоустойчивое и непокрытое множества: свойства и обобщения";

8. Научный семинар лаборатории теории игр и принятия решений Санкт-петербургского экономико-математического института РАН (научный руководитель д.ф.-м.н. Е.Б. Яновская, Санкт-Петербург), 27 мая 2009 г., доклад "Концепции решений задачи коллективного выбора";

9. Научный межфакультетский семинар по экономико-математическим методам Санкт-Петербургского государственного университета (научные руководители д.ф.-м.н. В.Д. Ногин и д.ф.-м.н. А.В. Прасолов), Петергоф, 28 мая 2009 г., доклад "Концепции решений в задаче коллективного выбора. Доминирующее, слабоустойчивое и непокрытое множества"; •

10. Международная конференция ADRES (Association pour le Developpement de la Recherche en Economie et Statistiques) в честь Мориса Салля, университет г. Кан (University of Caen), Кан, Франция, 11 июня 2009 г., доклад "Stable Solutions on Majority Relation", соавтор - Ф.Т. Алескеров;

11. Международная конференция Association of Southern European Economic Theorists (ASSET) Annual Meeting 2009, Босфорский Университет, Стамбул, Турция, 31 октября 2009 г., доклад "Stable Solutions to the Social Choice Problem: Dominant, Weakly Stable, Uncovered Sets and their Extensions", соавтор - Ф.Т. Алескеров;

12. Публичная лекция в университете Bilgi, Стамбул, Турция, 5 ноября 2009г. Тема лекции "Solutions on Majority Preference Relation";

13. Научный семинар кафедры алгебры механико-математического факультета Московского государственного университета, Москва, 17 ноября 2009 г., доклад "Устойчивые решения в задаче коллективного выбора и их матрично-векторное представление", соавтор - Ф.Т. Алескеров;

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, включающего 72 наименований. Основная часть работы изложена на 95 страницах, содержит 7 рисунков и 4 таблицы и 1 приложение.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Субочев, Андрей Николаевич

Заключение

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

Несколько таких решений были рассмотрены в сравнительной перспективе: Cr, UC1, UC11, UC111, UCIV, UCV, MWS1, MWS11, UCp, MU, UT и MD. В таблице 3 и таблице 4 для всех пар всех этих множеств-решений указано наличие или отсутствие отношения вложения, соответственно, в общем случае и для турниров. Символ "с=" в ячейке означает, что множество R, соответствующее строке данной ячейки, всегда является подмножеством множества С, соответствующего столбцу ячейки, RcC. Обозначение "п.п." указывает на отсутствие отношения вложения между множествами R и С. Знак ' говорит, что множества R и С совпадают.

Список литературы диссертационного исследования кандидат физико-математических наук Субочев, Андрей Николаевич, 2009 год

1. Айзерман М.А., Алескеров Ф.Т. Задача Эрроу в теории группового выбора (анализ проблемы) // Автоматика и телемеханика. 1983. № 9. С. 127-151.

2. Алескеров Ф.Т., Субочев А.Н. Об устойчивых решениях в ординальной задаче выбора // Доклады Академии Наук. 2009. Т. 426. №3. С. 318-320.

3. Субочев А.Н. Доминирующие, слабоустойчивые и непокрытые множества: свойства и обобщения // Автоматика и Телемеханика. 2010. №1. С. 130-143.

4. Субочев А.Н. Доминирующие, слабоустойчивые и непокрытые множества: свойства и обобщения // Труды IV Международной конференции по проблемам управления. М.: ИЛУ РАН, 2009.

5. Aizerman М., Aleskerov F. Voting operators in the space of choice functions // Mathematical Social Sciences. 1986. V. 11. № 3. P. 201-242.

6. Aleskerov F. Arrovian Aggregation Models. Dordercht: Kluwer Academic Publishers, 1999.

7. Aleskerov F. Voting models in Arrovian framework // Social Choice Theory reexamined / Eds. Arrow K., Sen A., Suzumura K. N.Y.: St. Martin Press, 1997. V. l.P. 47-67.

8. Aleskerov F., Kurbanov E. A Degree of Manipulability of Known Social Choice Procedures // Current Trends in Economics: Theory and Applications / Eds. Alkan A., Aliprantis Ch., Yannelis N. N.Y.: Springer-Verlag, 1999. P. 1327.

9. Aleskerov F., Subochev A. Matrix-vector representation of various solution concepts. Working paper WP7/2009/03. M.: State University Higher School of Economics, 2009.

10. Aleskerov F., Vol'skiy V. Choice of the Best Variants on Binary Relations and the Extrimizational Choice. Preprints of 10th World Congress on Automatic Control. Munich, 1987. V. 5. P. 234-239.

11. Arrow К. Social Choice and Individual Values. New Haven: Yale University Press, 1963. (1st ed. 1951).

12. Banks J. Sophisticated voting outcomes and agenda control // Social Choice and Welfare. 1985. V. 1. P. 295-306.

13. Banks J., Bordes G., Le Breton M. Covering relations, closest orderings and hamiltonian bypaths in tournaments // Social Choice and Welfare. 1991. V. 8. P. 355-363.

14. Bianco W., Jeliazkov I., Sened I. The uncovered set and the limits of legislative action // Political Analysis. 2004. V. 12(3). P. 256-276.

15. Bianco W., Lynch M., Miller G., Sened I. "A Theory Waiting to Be Discovered and Used": A Reanalysis of Canonical Experiments on Majority Rule Decision-Making // Journal of Politics. 2006. V. 68. Iss. 4. P. 838-851.

16. Black D. The theory of committees and elections. Cambridge: Cambridge University Press, 1958.

17. Brandt F., Fischer F., Harrenstein P., Mair M. A computational analysis of the tournament equilibrium set // Social Choice and Welfare. 2009. (on-line publication).

18. Coughlan P., Le Breton M. A social choice function implementable via backward induction with values in the ultimate uncovered set // Review of Economic Design. 1999. V. 4. P. 153-160.

19. Cox G. The Uncovered Set and the Core // American Journal of Political Science. 1987. V. 31(2). P. 408-422.

20. Deb R. On Schwart's Rule // Journal of Economic Theory. 1977. V. 16. P. 103110.

21. De Donder Ph. Majority voting solution concepts and redistributive taxation // Social Choice and Welfare. 2000. V. 17. P. 601-627.

22. Duggan J. A systematic approach to the construction of non-empty choice sets // Social Choice and Welfare. 2007. V. 28. P. 491-506.

23. Duggan J. Uncovered sets. Mimeo. 2006.

24. Dutta В. Covering sets and a New Condorcet Choice Correspondence // Journal of Economic Theory. 1988. V. 44. P. 63-80.

25. Dutta B. On the Tournament Equilibrium Set // Social Choice and Welfare. 1990. V. 7. P. 381-383.

26. Dutta В., Jackson M., Le Breton M. The Banks Set and the Uncovered Set in Budget Allocation Problems // Social Choice and Strategic Decisions. Essays in Honor of Jeffrey S. Banks. Studies in Choice and Welfare. Berlin-Heidelberg: Springer-Verlag, 2005.

27. Dutta В., Laslier J.-F. Comparison functions and choice correspondences // Social Choice and Welfare. 1999. V. 16. P. 513-532.

28. Epstein D. Uncovering some subtleties of the uncovered set: social choice theory and distributive politics // Social Choice and Welfare. 1997. V. 15. P. 81-93.

29. Farquharson R. The theory of social choice. Princeton: Princeton University Press, 1973.

30. Feld S., Grofman В., Hartley R., Kilgour M., Miller N. The Uncovered Set in Spatial Voting Games // Theory and Decision. 1987. V. 23(2). P. 129-155.

31. Feld S., Grofman В., Miller N. The Geometry of Majority Rule // Journal of Theoretical Politics. 1989. V. 1(4). P. 379-406.

32. Ferejohn J. Spatial Theory of Elections // Political Science in History: research programs and political traditions / Eds. Farr J., Dryzek J., Leonard S. N.Y.: Cambridge University Press, 1995. P. 253-275.

33. Fishburn P. Condorcet social choice functions // SIAM Journal of Applied Mathematics. 1977. V. 33. P. 469-489.

34. Hartley R., Kilgour M. The geometry of the uncovered set // Mathematical Social Sciences. 1987. V. 14. P. 175-183.

35. Goff B, Grier K. On the (mis)measurement of legislator ideology and shirking // Public Choice. 1993. V. 76. P. 5-20.

36. Good I. A note on Condorcet sets // Public Choice. 1971. V. 10. P. 97-101.

37. Kadane J. Some equivalence classes in paired comparisons // Annals of Mathematical statistics. 1966. V. 37. P. 488-494.

38. Laffond G., Laine J. Condorcet choice and the Ostrogorski paradox // Social Choice and Welfare. 2009. V. 32. P. 317-333.

39. Laffond G., Laine J. Weak covering relations // Theory and Decision. 1994. V. 37(3). P. 245-65.

40. Laffond G., Laine J, Laslier J.-F. Composition-consistent tournament solutions and social choice functions // Social Choice and Welfare. 1996. V. 13. P. 7593.

41. Laffond G., Laslier J.-F. Slater's Winner of a Tournament may not be the Banks Set // Social Choice and Welfare. 1991. V. 8. P. 365-369.

42. Laffond G., Laslier J.-F, Le Breton M. Condorcet Choice Correspondences: A Set-Theoretical Comparison // Mathematical Social Sciences. 1995. V. 30 P. 25-35.

43. Laslier J.-F. Tournament Solutions and Majority Voting. Berlin/Heidelberg: Springer-Verlag, 1997.

44. Lombardi M. Minimal covering set solutions // Social Choice and Welfare. 2009. V. 32(4).

45. Lombardi M. Uncovered set choice rules // Social Choice and Welfare. 2008. V.31.P. 271-279.

46. McGarvey D. A theorem on the construction of voting paradoxes // Econometrica. 1953. V. 21. P. 608-610.

47. McKelvey R. Covering, dominance and institution-free properties of social choice // American Journal of Political Science. 1986. V. 30. P. 283-314.

48. Miller N. A new solution set for tournaments and majority voting: Further graph-theoretical approaches to the theory of voting // American Journal of Political Science. 1980. V. 24. P. 68-96.

49. Miller N. Graph-theoretical approaches to the theory of voting // American Journal of Political Science. 1977. V. 21. P. 769-803.

50. Miller N. Pluralism and Social Choice // American Political Science Review. 1983. V. 77. P. 734-747.

51. Miller N., Grofman В., Feld S. The structure of the Banks set // Public Choice. 1990. V. 66. P. 243-251.

52. Moulin H. Choosing from a Tournament // Social Choice and Welfare. 1986. V. 3(4). P. 271-291.53. von Neumann J., Morgenstern O. Theory of Games and Economic Behavior. Princeton: Princeton University Press, 1944.

53. Nurmi H. On the difficulty of making social choices // Theory and Decision. 1995. V. 38. No. 1.

54. Ordeshook P. Constitutional stability // Constitutional Political Economy. 1992. V. 3. No. 2.

55. Ordeshook P., Schwartz T. Agendas and The Control of Political Outcomes // The American Political Science Review. 1987. V. 81. No. 1. P. 179-199.

56. Ozkal-Sanver I., Sanver R. A new monotonicity condition for tournament solutions // Theory and Decision. 2009. (on-line publication).

57. Penn E. Alternate definitions of the uncovered set and their implications // Social Choice and Welfare. 2006. V. 27. P. 83-87.

58. Penn E. The Banks set in infinite spaces // Social Choice and Welfare. 2006. V. 27. P. 531-543.

59. Peris J., Subiza B. Condorcet choice correspondences for weak tournaments // Social Choice and Welfare. 1999. V. 16(2). P. 217-231.

60. Plott C. A Notion of Equilibrium and its Possibility under Majority Rule // American Economic Review. 1967. V. 67. Iss. 4. P. 787-806.

61. Shepsle K., Weingast B. Uncovered sets and Sophisticated Voting Outcomes with Implications for Agenda Institutions // American Journal of Political Science. 1984. V. 28(1). P. 49-74.

62. Smith J. Aggregation of Preferences with Variable Electorates // Econometrica. 1973. V. 41. Iss. 6. P. 1027-1041.

63. Schwartz Т. Collective choice, separation of issues and vote trading // The American Political Science Review. 1977. V. 71. No. 3. P. 999-1010.

64. Schwartz T. Cyclic Tournaments and Cooperative Majority Voting: A Solution // Social Choice and Welfare. 1990. V. 7. P. 19-29.

65. Schwartz T. On the Possibility of Rational Policy Evaluation // Theory and Decision. 1970. V. 1. P. 89-106.

66. Schwartz T. Parliamentary procedure: principal forms and political effects // Public Choice. 2008. V. 136. P. 353-377.

67. Schwartz T. Rationality and the Myth of the Maximum // Nous. 1972. V. 6. P. 97-117.

68. Schwartz T. The Logic of Collective Choice. N.Y.: Columbia University Press, 1986.

69. Subiza В., Peris J. Condorcet choice functions and maximal elements // Social Choice and Welfare. 2005. V. 24. P. 497-508.

70. Subochev A. Dominant, Weakly Stable, Uncovered Sets: Properties and Extensions. Working paper WP7/2008/03. Moscow: State University Higher School of Economics, 2008.

71. Ward B. Majority Rule and Allocation // Journal of Conflict Resolution. 1961. V. 5. P. 379-389.