Конструкция механизма
Эта статья включает список литературы , связанную литературу или внешние ссылки , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( Июль 2024 г. ) |
Часть серии о |
Экономика |
---|
Проектирование механизмов , иногда называемое теорией реализации или институтов проектированием , [1] — раздел экономики , социального выбора и теории игр , занимающийся разработкой игровых форм (или механизмов) для реализации заданной функции социального выбора . Поскольку она начинается с конца игры (оптимальный результат), а затем работает в обратном направлении, чтобы найти игру, которая его реализует, ее иногда называют обратной теорией игр . [2]
Проектирование механизмов имеет широкое применение, включая традиционные области экономики, такие как проектирование рынка , а также политологию (посредством теории голосования ) и даже сетевые системы (например, междоменная маршрутизация ). [2]
Проектирование механизмов изучает концепции решений для класса игр с конфиденциальной информацией. Леонид Гурвич объясняет, что «в задаче проектирования целевая функция является основной заданной, а механизм неизвестен. Таким образом, задача проектирования является обратной стороной традиционной экономической теории, которая обычно посвящена анализу эффективности заданный механизм». [3]
2007 года Нобелевская премия по экономике была присуждена Леониду Гурвичу , Эрику Маскину и Роджеру Майерсону «за заложение основ теории проектирования механизмов». [4] Связанные с этим работы Уильяма Викри , положившие начало этой области, принесли ему Нобелевскую премию 1996 года.
Описание
[ редактировать ]Один человек, называемый «принципалом», хотел бы обуславливать свое поведение информацией, известной лично игрокам игры . Например, директор хотел бы знать истинное качество подержанного автомобиля, который предлагает продавец. Он не может ничему научиться, просто спросив продавца, потому что в интересах продавца исказить правду. Однако при проектировании механизмов у директора есть одно преимущество: он может разработать игру, правила которой заставляют других действовать так, как ему хочется.
Без теории проектирования механизмов проблему директора было бы трудно решить. Ему придется рассмотреть все возможные игры и выбрать ту, которая лучше всего повлияет на тактику других игроков. Кроме того, доверителю придется делать выводы от агентов, которые могут ему лгать. Благодаря принципу раскрытия принципалу необходимо учитывать только те игры, в которых агенты правдиво сообщают свою личную информацию.
Фонды
[ редактировать ]Механизм
[ редактировать ]Игра в проектирование механизмов — это игра с частной информацией, в которой один из агентов, называемый принципалом, выбирает структуру выплат. Согласно Харсаньи ( 1967 ), агенты получают секретные «сообщения» от природы, содержащие информацию, необходимую для вознаграждения. Например, сообщение может содержать информацию об их предпочтениях или качестве продаваемого товара. Мы называем эту информацию «типом» агента (обычно обозначаемым и соответственно пространство типов ). Затем агенты сообщают о типе принципалу (обычно отмечается шляпой). ), это может быть стратегической ложью. После отчета принципал и агенты получают оплату в соответствии со структурой выплат, которую выбрал принципал.
Тайминг игры:
- Принципал обязуется использовать механизм что дает результат как функция сообщаемого типа
- Агенты сообщают, возможно, нечестно, о типовом профиле
- Механизм выполняется (агенты получают результат )
Чтобы понять, кто что получает, принято делить результат в распределение товаров и перевод денег, где означает распределение оказанных или полученных товаров в зависимости от типа, и означает денежный перевод как функцию типа.
В качестве ориентира проектировщик часто определяет, что должно произойти при наличии полной информации. Определить функцию социального выбора сопоставление (истинного) типового профиля непосредственно с распределением полученных или оказанных товаров,
Напротив, механизм сопоставляет сообщаемый профиль типа с результатом (опять же, как распределение товаров, так и и денежный перевод )
Принцип откровения
[ редактировать ]Предлагаемый механизм представляет собой байесовскую игру (игру с частной информацией), и если он ведет себя хорошо, игра имеет байесовское равновесие Нэша . В состоянии равновесия агенты стратегически выбирают свои отчеты в зависимости от типа
В таких условиях трудно найти байесовское равновесие, поскольку это включает в себя поиск стратегий наилучшего ответа агентов и наилучшего вывода из возможной стратегической лжи. Благодаря радикальному результату, называемому принципом откровения, независимо от того, какой механизм может использовать дизайнер, [5] ограничьте внимание состояниями равновесия, в которых агенты правдиво сообщают о типе. Принцип раскрытия гласит: «Каждому байесовскому равновесию Нэша соответствует байесовская игра с тем же равновесным результатом, но в которой игроки правдиво сообщают о типе».
Это чрезвычайно полезно. Этот принцип позволяет найти байесовское равновесие, предполагая, что все игроки правдиво сообщают о типе (с учетом ограничения совместимости стимулов ). Одним махом это устраняет необходимость учитывать либо стратегическое поведение, либо ложь.
Ее доказательство вполне прямое. Предположим, что это байесовская игра, в которой стратегия и выигрыш агента являются функциями его типа и действий других: . По определению агента i равновесная стратегия является ли Нэш ожидаемой полезностью:
Просто определите механизм, который побуждал бы агентов выбирать одно и то же равновесие. них равновесные стратегии агентов Самый простой для определения — это механизм, который обязуется играть за .
При таком механизме агенты, конечно, считают оптимальным раскрыть тип, поскольку механизм в любом случае использует те стратегии, которые они сочли оптимальными. Формально выбираем такой, что
Реализуемость
[ редактировать ]Разработчик механизма обычно надеется либо
- спроектировать механизм который «реализует» функцию социального выбора
- найти механизм который максимизирует некоторый критерий ценности (например, прибыль)
Реализовать функцию социального выбора это найти некоторую передаточную функцию что мотивирует агентов выбирать . Формально, если профиль равновесной стратегии в рамках этого механизма соответствует тому же распределению благ, что и функция социального выбора,
мы говорим, что механизм реализует функцию социального выбора.
Благодаря принципу откровения проектировщику обычно удается найти передаточную функцию. реализовать социальный выбор, решая связанную с ним игру по раскрытию правды. Если агенты считают оптимальным правдиво сообщить тип,
мы говорим, что такой механизм действительно реализуем . Задача состоит в том, чтобы найти правдиво реализуемую и приписать эту передаточную функцию исходной игре. Распределение истинно реализуемо, если существует передаточная функция такой, что
которое также называется ограничением совместимости стимулов (IC).
В приложениях состояние IC является ключом к описанию формы любым полезным способом. При определенных условиях он может даже аналитически выделить передаточную функцию. Кроме того, иногда добавляется ограничение участия ( индивидуальной рациональности ), если у агентов есть возможность не играть.
Необходимость
[ редактировать ]Рассмотрим ситуацию, в которой все агенты имеют функцию полезности, зависящую от типа. . Рассмотрим также распределение товаров это векторное значение и размер (что позволяет количества товаров) и предположим, что он кусочно непрерывен по своим аргументам.
Функция осуществимо только в том случае, если
в любое время и и x непрерывен в . Это необходимое условие, которое выводится из условий первого и второго порядка задачи оптимизации агента, предполагающего, что он говорит правду.
Его смысл можно понять в двух частях. агента В первой части говорится, что предельная норма замещения (MRS) увеличивается в зависимости от типа.
Короче говоря, агенты не скажут правду, если механизм не предложит более высоким типам агентов более выгодную сделку. В противном случае высшие типы, столкнувшиеся с любым механизмом, который наказывает высшие типы за сообщение, будут лгать и заявлять, что они являются низшими типами, нарушая ограничение совместимости стимулов и правдивости. Вторая часть — это условие монотонности, ожидающее своего исполнения. [ нужны разъяснения ]
что, если быть положительным, означает, что высшим типам следует давать больше благ.
Существует вероятность взаимодействия этих двух частей. Если для некоторого типового ряда в контракте предлагалось меньшее количество для более высоких типов , возможно, механизм мог бы компенсировать это, предоставляя более высоким типам скидку. Но для агентов низкого типа такой контракт уже существует, поэтому такое решение является патологией. Такое решение иногда встречается в процессе решения механизма. В этих случаях его необходимо « погладить ». В среде с несколькими товарами разработчик также может вознаградить агента большим количеством одного товара, чтобы заменить меньшее количество другого (например, масло вместо маргарина ). Многоцелевые механизмы — это область продолжающихся исследований в области проектирования механизмов.
Достаточность
[ редактировать ]В документах по проектированию механизмов обычно делаются два предположения для обеспечения реализуемости:
Это явление известно под несколькими названиями: условие однократного пересечения , условие сортировки и условие Спенса – Миррлиса. агента Это означает, что функция полезности имеет такую форму, что MRS имеет возрастающий тип. [ нужны разъяснения ]
Это техническое условие, ограничивающее скорость роста MRS.
Этих предположений достаточно, чтобы доказать, что любое монотонное реализуема (а существует тот, кто может это реализовать). Кроме того, в ситуации с одним товаром условие одиночного пересечения является достаточным, чтобы гарантировать, что только монотонный реализуема, поэтому дизайнер может ограничить свой поиск монотонным .
Выделенные результаты
[ редактировать ]Теорема об эквивалентности доходов
[ редактировать ]Викри ( 1961 ) приводит знаменитый результат: любой участник большого класса аукционов гарантирует продавцу одинаковый ожидаемый доход и что ожидаемый доход — это лучшее, что может сделать продавец. Это тот случай, если
- Покупатели имеют одинаковые функции оценки (которые могут быть функцией типа).
- Типы покупателей распределяются независимо
- Типы покупателей выбираются из непрерывного распределения.
- Распределение типов обладает свойством монотонной степени опасности.
- Механизм продает товар покупателю с наибольшей оценкой.
Последнее условие является решающим для теоремы. Подразумевается, что для получения более высокого дохода продавец должен рискнуть и передать товар агенту с более низкой оценкой. Обычно это означает, что он должен рискнуть вообще не продать товар.
Механизмы Викри – Кларка – Гроувса
[ редактировать ]Модель аукциона Викри (1961) позже была расширена Кларком ( 1971 ) и Гроувзом для решения проблемы общественного выбора, в которой стоимость государственного проекта несут все агенты, например, строить ли муниципальный мост. Получающийся в результате механизм «Викри-Кларка-Гроувса» может мотивировать агентов выбирать социально эффективное распределение общественного блага, даже если у агентов есть частные известные оценки. Другими словами, это может решить « трагедию общего достояния » — при определенных условиях, в частности, при квазилинейной полезности или если бюджетный баланс не требуется.
Рассмотрим ситуацию, в которой число агентов имеет квазилинейную полезность с частными оценками где валюта оценивается линейно. Разработчик VCG разрабатывает механизм, совместимый со стимулами (а значит, правдиво реализуемый), для получения истинного профиля типа, на основе которого он реализует социально оптимальное распределение.
Хитрость механизма VCG заключается в том, как он мотивирует правдивые откровения. Он устраняет стимулы к искажению информации, наказывая любого агента в размере стоимости вызванного им искажения. Среди отчетов, которые может сделать агент, механизм VCG допускает «нулевой» отчет, в котором говорится, что он безразличен к общественному благу и заботится только о денежном переводе. Это эффективно удаляет агента из игры. Если агент решает сообщить о типе, механизм VCG взимает с агента плату, если его отчет является ключевым , то есть если его отчет изменяет оптимальное распределение x так, чтобы нанести вред другим агентам. Оплата рассчитывается
который суммирует искажения в полезностях других агентов (а не его собственных), вызванные отчетностью одного агента.
Теорема Гиббарда – Саттертуэйта
[ редактировать ]Гиббард ( 1973 ) и Саттертуэйт ( 1975 ) дают результат о невозможности, аналогичный по духу теореме о невозможности Эрроу . Для очень общего класса игр могут быть реализованы только «диктаторские» функции социального выбора.
Функция социального выбора f () является диктаторской , если один агент всегда получает наиболее благоприятствуемое распределение благ.
Теорема утверждает, что при общих условиях любая истинно реализуемая функция общественного выбора должна быть диктаторской, если:
- X конечно и содержит не менее трех элементов
- Предпочтения рациональны
Теорема Майерсона – Саттертуэйта
[ редактировать ]Майерсон и Саттертуэйт ( 1983 ) показывают, что не существует эффективного способа для двух сторон торговать товаром, если каждая из них имеет тайные и вероятностно различающиеся оценки этого товара, без риска вынудить одну сторону торговать с убытком. Это один из самых замечательных негативных результатов в экономической науке — своего рода негативное зеркало фундаментальных теорем экономики благосостояния .
Значение Шепли
[ редактировать ]Филлипс и Марден (2018) доказали, что для игр с разделением затрат с вогнутыми функциями затрат оптимальное правило распределения затрат, которое сначала оптимизирует неэффективность игры в наихудшем случае (цену анархии ), а затем, во-вторых, оптимизирует лучший вариант. Результаты ( цена стабильности ) – это и есть правило разделения затрат по ценности Шепли. [6] Утверждение о симметрии аналогично справедливо и для игр с разделением полезностей с выпуклыми функциями полезности.
Ценовая дискриминация
[ редактировать ]Миррлис ( 1971 ) предлагает ситуацию, в которой передаточную функцию t () легко найти. Из-за своей актуальности и доступности это распространенная ситуация в литературе. Рассмотрим ситуацию с одним товаром и одним агентом, в которой агент имеет квазилинейную полезность с неизвестным параметром типа.
и в котором принципал имеет предшествующий CDF по типу агента . Принципал может производить товары с выпуклыми предельными издержками c ( x ) и хочет максимизировать ожидаемую прибыль от транзакции.
в зависимости от условий IC и IR
Главным здесь является монополист, пытающийся установить схему ценообразования, максимизирующую прибыль, в которой он не может идентифицировать тип клиента. Типичным примером является авиакомпания, устанавливающая тарифы для деловых путешественников, туристов и студентов. Из-за условий IR он должен предоставить каждому типу достаточно выгодную сделку, чтобы побудить к участию. Из-за условия IC он должен предоставить каждому типу достаточно выгодную сделку, чтобы этот тип предпочел свою сделку любой другой.
Уловка, предложенная Миррлисом (1971), состоит в том, чтобы использовать теорему о конверте , чтобы исключить передаточную функцию из ожидания максимизации:
Интеграция,
где это некоторый тип индекса. Замена стимул-совместимого в максимаде,
после интегрирования по частям. Эту функцию можно максимизировать поточечно.
Потому что совместим со стимулами, и разработчик может отказаться от ограничения IC. Если функция полезности удовлетворяет условию Спенса–Мирлиса, то монотонная функция существует. Ограничение IR можно проверить в равновесии и соответствующим образом повысить или понизить тарифный план. Кроме того, обратите внимание на наличие коэффициента опасности в выражении . Если распределение типов обладает свойством монотонного отношения рисков, FOC достаточно для решения t (). Если нет, то необходимо проверить, выполняется ли ограничение монотонности (см. достаточность выше) повсюду в графиках распределения и комиссий. Если нет, то дизайнер должен использовать глажку Майерсона.
Майерсон гладит
[ редактировать ]В некоторых приложениях разработчик может решить условия первого порядка для графиков цен и распределения, но обнаружить, что они не являются монотонными. Например, в квазилинейной ситуации это часто происходит, когда отношение рисков само по себе не является монотонным. По условию Спенса-Миррлиса оптимальные графики цен и распределения должны быть монотонными, поэтому разработчик должен исключить любой интервал, в течение которого график меняет направление, путем его выравнивания.
Интуитивно понятно, что дизайнер считает оптимальным объединить определенные типы вместе и дать им один и тот же контракт. Обычно дизайнер мотивирует более высокопоставленных людей выделиться, предлагая им более выгодную сделку. Если на границе недостаточно нескольких высших типов, проектировщик не считает целесообразным предоставлять более низким типам уступку (называемую их информационной рентой ), чтобы взимать с более высоких типов контракт, специфичный для конкретного типа.
Рассмотрим пример выше, когда принципал-монополист продает товары агентам с квазилинейной полезностью. Предположим, что график распределения удовлетворяющий условиям первого порядка, имеет единственный внутренний пик при и один внутренний корыто на , показано справа.
- Следуя Майерсону (1981), сгладьте его, выбрав удовлетворяющий где является обратной функцией отображения x в и является обратной функцией отображения x в . То есть, возвращает перед внутренним пиком и возвращает после внутреннего корыта.
- Если немонотонная область граничит с краем пространства типов, просто установите соответствующий функцию (или обе) к типу границы. Если имеется несколько регионов, см. учебник по итеративной процедуре; возможно, придется гладить несколько корыт вместе.
Доказательство
[ редактировать ]В доказательстве используется теория оптимального управления. Он рассматривает набор интервалов в немонотонной области из-за чего это могло бы сгладить график. Затем он записывает гамильтониан, чтобы получить необходимые условия для в интервалах
- это удовлетворяет монотонности
- для которого ограничение монотонности не является обязательным на границах интервала
Второе условие гарантирует, что удовлетворение задачи оптимального управления повторно подключается к расписанию исходной задачи на границах интервалов (без скачков). Любой Удовлетворение необходимым условиям должно быть плоским, поскольку оно должно быть монотонным и при этом пересоединяться на границах.
Как и прежде, максимизируйте ожидаемый выигрыш принципала, но на этот раз с учетом ограничения монотонности.
и для этого используйте гамильтониан с теневой ценой
где является переменной состояния и контроль. Как обычно при оптимальном управлении, уравнение эволюции стоимости должно удовлетворять
Воспользовавшись условием 2, обратите внимание, что ограничение монотонности не является обязательным на границах интервал,
это означает, что условие переменной стоимости может быть интегрировано и также равно 0
Среднее искажение профицита основной суммы долга должно быть равно 0. Чтобы сгладить график, найдите такой, что его прообраз отображается в интервал, удовлетворяющий приведенному выше условию.
См. также
[ редактировать ]- Алгоритмическое проектирование механизмов
- Элвин Э. Рот – Нобелевская премия в области дизайна рынка
- Проблема с назначением
- Теория контрактов
- Теория реализации
- Совместимость стимулов
- Принцип откровения
- Умный рынок
- Метаигра
Примечания
[ редактировать ]- ^ «Журнал проектирования механизмов и институтов» . www.mechanism-design.org . Проверено 1 июля 2024 г.
- ^ Jump up to: а б Пенна, Паоло; Вентре, Кармин (июль 2014 г.). «Оптимальные механизмы защиты от сговора с проверкой» . Игры и экономическое поведение . 86 : 491–509. дои : 10.1016/j.geb.2012.09.002 . ISSN 0899-8256 .
- ^ Л. Гурвич и С. Рейтер (2006), Разработка экономических механизмов , стр. 30
- ^ «Премия Риксбанка Швеции в области экономических наук памяти Альфреда Нобеля 2007» (пресс-релиз). Нобелевский фонд . 15 октября 2007 года . Проверено 15 августа 2008 г.
- ^ В необычных обстоятельствах некоторые игры, говорящие правду, имеют больше равновесий, чем байесовская игра, из которой они построены. См. Фуденбург-Тироль, гл. 7.2 для некоторых ссылок.
- ^ Филлипс, Мэтью; Марден, Джейсон Р. (июль 2018 г.). «Компромиссы в проектировании в вогнутых играх с разделением затрат». Транзакции IEEE при автоматическом управлении . 63 (7): 2242–2247. дои : 10.1109/tac.2017.2765299 . ISSN 0018-9286 . S2CID 45923961 .
Ссылки
[ редактировать ]- Кларк, Эдвард Х. (1971). «Многочастное ценообразование на общественные блага» (PDF) . Общественный выбор . 11 (1): 17–33. дои : 10.1007/BF01726210 . JSTOR 30022651 . S2CID 154860771 .
- Гиббард, Аллан (1973). «Манипулирование схемами голосования: общий итог» (PDF) . Эконометрика . 41 (4): 587–601. дои : 10.2307/1914083 . JSTOR 1914083 .
- Гроувс, Теодор (1973). «Стимулы в командах» (PDF) . Эконометрика . 41 (4): 617–631. дои : 10.2307/1914085 . JSTOR 1914085 .
- Харсаньи, Джон К. (1967). «Игры с неполной информацией, в которые играют «байесовские» игроки, I-III. Часть I. Базовая модель». Наука управления . 14 (3): 159–182. дои : 10.1287/mnsc.14.3.159 . JSTOR 2628393 .
- Миррлис, Дж. А. (1971). «Исследование теории оптимального подоходного налогообложения» (PDF) . Обзор экономических исследований . 38 (2): 175–208. дои : 10.2307/2296779 . JSTOR 2296779 . Архивировано из оригинала (PDF) 10 мая 2017 г. Проверено 12 августа 2016 г.
- Майерсон, Роджер Б.; Саттертуэйт, Марк А. (1983). «Эффективные механизмы двусторонней торговли» (PDF) . Журнал экономической теории . 29 (2): 265–281. дои : 10.1016/0022-0531(83)90048-0 . hdl : 10419/220829 .
- Саттертуэйт, Марк Аллен (1975). «Стратегическая устойчивость и условия Эрроу: теоремы существования и соответствия для процедур голосования и функций социального благосостояния». Журнал экономической теории . 10 (2): 187–217. CiteSeerX 10.1.1.471.9842 . дои : 10.1016/0022-0531(75)90050-2 .
- Викри, Уильям (1961). «Контрспекуляции, аукционы и закрытые конкурсные торги» (PDF) . Журнал финансов . 16 (1): 8–37. дои : 10.1111/j.1540-6261.1961.tb02789.x .
Дальнейшее чтение
[ редактировать ]- Глава 7 Фуденберг, Дрю; Тироль, Жан (1991), Теория игр , Бостон: MIT Press , ISBN 978-0-262-06141-4 . Стандартный учебник по теории игр для аспирантов.
- Глава 23 Мас-Колелл ; Уинстон; Грин (1995), Микроэкономическая теория , Оксфорд: Oxford University Press , ISBN 978-0-19-507340-9 . Стандартный текст для выпускников микроэкономики.
- Милгром, Пол (2004), Применение теории аукционов на практике , Нью-Йорк: Издательство Кембриджского университета , ISBN 978-0-521-55184-7 . Применение принципов проектирования механизмов в контексте аукционов.
- Ноам Нисан . о Технический доклад Google конструкции механизмов.
- Легро, Патрик; Кантильон, Эстель (2007). «Что такое конструкция механизма и почему это важно для разработки политики?» . Центр исследований экономической политики .
- Роджер Б. Майерсон (2008), «Проектирование механизмов», Новый экономический онлайн-словарь Пэлгрейва, Аннотация.
- Диамантарас, Димитриос (2009), Набор инструментов для экономического проектирования , Нью-Йорк: Пэлгрейв Макмиллан , ISBN 978-0-230-61060-6 . Текст для выпускников, специально посвященный проектированию механизмов.
Внешние ссылки
[ редактировать ]- Эрик Маскин « Лекция Нобелевской премии » прочитана 8 декабря 2007 года в Аула Магна Стокгольмского университета.