Справедливый дележ

Карпов Александр Викторович

Как разделить предметы между участниками, чтобы никто не чувствовал себя обделенным? Александр Карпов, доцент факультета экономических наук, и его сингапурский коллега профессор Варут Суксомпонг искали математический ответ на этот вопрос. В интервью — о том, как строится модель рациональных предпочтений, почему нельзя полагаться на простую сумму ценностей и где пригодится алгоритм, задающий минимальное количество вопросов.

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

 

— Вы работали с профессором Варутом Суксомпонгом, который представляет Школу компьютерных наук Национального университета Сингапура. Как вы познакомились и как строилось ваше взаимодействие?

— Область научных интересов Варута Суксомпонга близка к моей. Мы исследуем вычислительные задачи теории коллективного выбора. Мы не были знакомы, но у нас есть общие соавторы, и я был знаком с некоторыми его работами. Как только был объявлен конкурс стажировок, я написал ему с предложением совместной работы, и он незамедлительно ответил согласием.

— Расскажите о своих исследованиях. Какую задачу вы решали с сингапурским коллегой?

— Я занимаюсь разработкой математических моделей коллективных предпочтений. В качестве иллюстрации можно обратиться к моделям голосования: в них формируется единая шкала политического спектра (например, правые — левые), а предпочтения избирателя определяются удаленностью кандидатов от его собственной позиции. Аналогичным образом в других задачах возникают иные структурированные системы предпочтений.

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

Задача справедливого дележа формулируется следующим образом: имеется множество неделимых предметов, которые необходимо распределить между участниками. Цель — разработать алгоритм распределения, обеспечивающий «справедливый» дележ при любых возможных предпочтениях участников. Однако из-за огромного разнообразия возможных предпочтений не существует алгоритма, который удовлетворял бы одновременно всем желаемым свойствам.

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

• Монотонность. Если набор A содержит все предметы набора B и еще какие-то дополнительные, то A предпочтительнее B.

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

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

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

— Национальный университет Сингапура — это место, где встречаются исследователи со всего мира, а Азия сегодня становится мощным центром математической экономики. Чувствуется ли в работах профессора Суксомпонга, который учился на Западе, но работает в Азии, какой-то особый, азиатский подход к этим задачам, или наука о принятии решений уже полностью глобальна и едина?

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

— Расскажите о вашем опыте стажировок. Отличается ли сингапурская академическая культура от европейской?

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

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

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

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

— Планируется ли публикация по итогам стажировки?

— Да, планируется подать работу на Международную конференцию по автономным агентам и мультиагентным системам (AAMAS). В области компьютерных наук публикация материалов конференций так же престижна, как и публикация в журнале.

23 апреля