Лекция 24. Механизмы группового выбора

Понятие механизма. Поговорим о механизмах - объектах, очень близких к играм. Предположим, что группа участников (агентов) N должна выбрать один из элементов из некоторого (фиксированного, заданного) множества альтернатив Л. Выбор будет зависеть от предпочтений участников относи­тельно Л, но также и от процедуры, правила выбора. Вот это последнее и называется механизмом (группового выбора); употребим также термин game form. Формально, механизм (при данных Д* и Л) - это отображение

/ : x/f.vS/ —> А.

Множества Si называются множествами сообщений или стратегий участни­ка i, а само отображение / - функцией исхода. Участники посылают какие-то сообщения si £ Si; механизм выдает отобранную альтернативу f(sN) = f(sh ...,sn) £ А.

Как мы видим, эта структура очень похожа на игру; недостает только предпочтений или полезностей. Если задан профиль предпочтений Яд = (Ri, г £ N) на Л, или профиль полезностей un = (щ), мы получаем игру в нормальной форме, которая обозначается G(f, идг) или G(f, Rn)- Можно сказать, что механизм - это материальная часть игры (или правила игры), тогда как предпочтения (и веры) - это идеальная, надстроечная часть. Надо сказать, что многие игры задаются как механизмы. Даже если в них указаны денежные выигрыши и все стремятся максимизировать этот выигрыш, нуж­но уточнить по крайней мере две вещи: как агенты относятся к выигрышам других (зависть или альтруизм) и как агенты относятся к лотереям. Другой пример механизмов - аукционы. Наконец, процедуры голосования (выборов должностных лиц или общественных проектов) также доставляют примеры механизмов.

Из пройденного материала механизмы более всего напоминают Байесовы игры с сообщениями. Как и там, наиболее естественным сообщением было бы сообщение участника о своих предпочтениях. Такие механизмы, где страте­гические множества Si состоят из всех (допустимых данной задачей) пред­почтений участника г, называются прямыми. Однако часто применяются и непрямые механизмы. Даже при голосовании вас обычно просят не упорядо-чить всех кандидатов, а оставить в списке одного (реже - нескольких) наибо­лее достойного кандидата.

Каждый участник стремится послать такое сообщение, которое дало бы наиболее предпочтительный исход. Тут мы прямо попадаем на зыбкую поч­ву концепции решения. Как мы видели, в теории игр нет одного, пригодного во всех случаях понятия решения игры. Все зависит от привходящих обсто­ятельств, которые часто не оговариваются и должны уточняться отдельно. Например, могут ли участники сообщаться и координировать свои действия (стратегии)? Далее мы в основном будем придерживаться некооперативной точки зрения, хотя бы потому, что координация действий предполагает на­личие отдельного механизма координации.

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

Доминантно-стратегические механизмы. Вопрос о предсказуемости работы механизма - один из важнейших. Дело в том, что часто приходит­ся конструировать механизмы с заданными свойствами (mechanism design); например, желательно, чтобы механизм выдавал всегда Парето-оптимальные исходы. Но для этого нужно знать, каков будет исход; только после этого име­ет смысл обсуждать достоинства этого исхода. Поясним эту мысль на одном примере.

Пусть два участника выбирают из четырех альтернатив ж, у. z7 t. и пред­почтения их имеют вид

X

У

У

X

Z

Z

t

t

1

2

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

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

х У г У I У у.

В этом случае у набирает только 3 очка (как и л), и побеждает х. Но анало­гично может поступить участник 2 и объявить своим ранжированием

у У г У t У х.

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

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

Определение. Механизм / называется доминантно-стратегическим, ес­ли для любых предпочтений участников Яд в игре 0(/. Яд-) существует рав­новесие в доминирующих стратегиях.

Может показаться, что такое редко бывает. Чтобы доминирующая стра­тегия была у всех игроков? да еще при любых предпочтениях? Тут нужно сделать два пояснения. Во первых, взятый наугад механизм конечно не бу­дет доминантно-стратегическим; как и вообще все хорошее, он встречается крайне редко. Но в этом и состоит задача изобретателя (дизайнера) меха­низма. Во вторых, как мы увидим, ситуация сильно зависит от той области предпочтений, в которой должен действовать наш механизм. Если механизм должен хорошо работать в любой обстановке (иметь доминирующие страте­гии при любых мыслимых профилях предпочтений), то выбор крайне огра­ничен. Напротив, если обстановка достаточно узкая, ДС-механизмов может быть довольно много. Дальнейшее можно рассматривать как иллюстрацию этого общего замечания.

В случае прямых механизмов можно уточнить доминантную стратегич-ность. А именно, прямой механизм называется неманипулируемым (употре­бимы термины straightforward или strategy-proof), если для любых предпочте­ний R; правдивая стратегия Я; является доминирующей. В этой связи мож­но снова вспомнить принцип выявления. Это довольно простое утверждение, что если есть доминантно-стратегический механизм /. то существует и пря­мой неманипулируемый механизм, эквивалентный в некотором смысле исход­ному. По этой причине в дальнейшем мы ограничим свое внимание только прямыми неманипулируемыми механизмами.

Случай одного участника. При одном участнике существует доволь­но много неманипулируемых механизмов, и более того, можно дать полное их описание. А именно, зафиксируем некоторое подмножество Z в множе­стве А, и определим механизм / формулой (здесь R - предпочтение нашего единственного участника)

/ = Argmaxi2|Z.

Т.е. механизм отбирает наилучшую альтернативу в подмножестве Z (мы игнорируем вопросы существования и неединственности максимальных эле­ментов). Довольно явно, что это неманипулируемый механизм, и что так вы­глядит любой такой. При этом Z - это образ /.

Вообще, если механизм / зависит только от сообщений одного из участ­ников (и игнорирует сообщения остальных), то говорят, что он однобокий (унилатеральный), или диктаторский.

Случай двух альтернатив. Если альтернатив всего две, тоже суще­ствует масса неманипулируемых механизмов. Простейший из них - правило простого большинства. Каждый из участников отмечает одну из альтернатив (наилучшую для себя). Побеждает та (из двух) альтернатив, которая наберет больше голосов (случаи равенства мы сейчас игнорируем). Довольно ясно, что отметив не свою лучшую альтернативу, вы не улучшите исход, так что это неманипулируемый механизм. Можно разнообразить это правило, например, придавая разным участникам разный вес.

Теорема Гиббэрда. Ну а можно ли придумать механизм, который был бы неманипулируемым при трех и более альтернативах? Конкретно, речь шла о неманипулируемых системах голосования. Довольно давно было замечено, что все известные системы голосования (простого большинства, правило Бор-да, многокруговые выборы и т.п.) оставляли возможности для манипулирова­ния. В 1973 г. Гиббэрд (а позже - и Саттерсвейт) превратил это наблюдение в строгий результат. А именно, он доказал следующее утверждение. Пусть дляпростоты А - конечное множество, а V - множество всех слабых (или ли­нейных) порядков на А. Если f : Vм —У А - неманипулируемый механизм, то либо / однобокий, либо образ / состоит из двух элементов.

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

Отметим сразу, что этот результат аналогичен знаменитой теореме Эрроу, которая утверждает, что только диктаторское правило группового выбора удовлетворяет некоторым естественным требованиям (аксиомам). Как уже говорилось, один из выходов из пессимистического тупика Гиббэрда состоит в отказе от универсальности механизма, точнее, в ограничении области его применимости. Об одной такой области, наиболее экономически осмысленной, мы и расскажем.

Механизмы Кларка-Гроувса. Допустим, что мы находимся в ситуации трансферабельной полезности. Т.е. имеются деньги которые линейно вхо­дят в функцию полезности (так что она имеет вид и[а,£) = у (а) + где а -неденежная часть исхода) и которые можно передавать друг другу. В такой ситуации сообщениями участников естественно считать функции у : А —у К. - денежные оценки ими исходов из множества А. Прямой механизм перера­батывает профиль оценок Ум = {у^ в исход (а; ^1,1п), где а - общественная альтернатива, а ^ - денежные платежи участнику /.

Мы уже сталкивались с примером неманипулируемого механизма в такой ситуации - с аукционом Викри (или второй цены). Там речь шла об одном предмете, каждый назначал какую-то оценку v; £ К, побеждал тот, кто на­зовет наибольшую цену, но платил он вторую цену. Чтобы обобщить этот пример, нужно правильно понять принцип, который обеспечивает немини-пул ируемость. Он состоит в том, что денежные трансферы должны компен­сировать тот ущерб, который участник наносит остальным своим участием. Эта идея формализуется так.

Пусть v; - сообщение участники /. и пусть а*{ум) - та альтернатива, на которых достигает максимума суммарная полезность Х^елт : • ^ —^ И^-Тогда наш механизм отбирает альтернативу а* {ум) и назначает участнику /денежный трансфер

U = U(vN) = J~]vj(a*(vN))-

Зфг

Иначе говоря, денежные выплаты участнику / равны "выигрышу" всех осталь­ных от принятия проекта а*. Вместе с "натуральной" частью полезности Vi(a*) игрок г получает денежную часть в размере

зфг 3

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

Какие достоинства предложенного механизма? Первое и главное - он нема­нипулируем (и значит, предсказуем). Второе - он отбирает исходы а*, которые максимизируют суммарную оценку группы. Однако сразу бросается в глаза и главный недостаток механизма - его финансовая несбалансированность. Где же взять такую прорву денег, чтобы выплачивать каждому Х^угуз(а*У- Хо­телось бы, чтобы суммарные выплаты (трансферы) равнялись нулю. Они же равны

1>Ы = ЕЕ^*) = (п- l)V(a%

i i j^i

где V = Yli ri" суммарная оценка альтернатив всеми участниками группы. И это число в общем случае отлично от нуля. Кто же будет возмещать расходы по функционированию этого механизма?

Однако возможности по конструированию механизма еще не исчерпаны до конца. Это видно хотя бы из того, что сами оценки Vi определены с точностью до константы. И вообще, к денежным выплатам без ущерба для неманипули­руемости можно прибавлять выражения вида hi(vN^i)7 которые не зависят от сообщений участника г (и тем самым не влияют на выбор им своего сооб­щения vi). Таким образом, более общий вид денежных трансферов такой:

U(vn) = ^2vj(a*(vN)) + hi(vN-i),

Зфг

где, напомню, (i*{v\) максимизирует суммарную оценку V = ^ v-,. Механизм такого вида называют механизмом Гроувса (Groves). Можно показать, чтолюбой неманипулируемый механизм является механизмом Гроувса. Подби­рая те или иные корректирующие добавки hi, можно пытаться строить нема­нипулируемый механизм с теми или иными дополнительными свойствами.

Интересный способ корректировки денежных трансферов предложил Кларк. Идея его в том, что участник, безразличный к общественным альтернативам (т.е. у которого оценочная функция Vi является константой), не получает и не платит денег. В общем случае он платит за тот ущерб для остальных, который он наносит своим воздействием. Таким образом, t; всегда неположительны при механизме Кларка. "Налогом" облагаются лишь те участники, которые активно влияют на выбор, т.н. ключевые (pivot) участники. Нужно отметить, что этот излишек денег не должен распределяться между остальными участ­никами (это нарушило бы неманипулируемость), а должен выбрасываться на ветер, сжигаться (или оставляться у организатора аукциона). Так что ме­ханизм Кларка также финансово несбалансирован, хотя и в минимальной степени.