Jump to content

Однопараметрическая утилита

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

Обозначения

[ редактировать ]

Есть набор возможных результатов.

Есть агенты, которые имеют разные оценки для каждого результата.

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

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

У каждого агента есть номер который представляет собой «выигрышную ценность» . Оценка агентом результатов в может принимать одно из двух значений: [ 1 ] : 228 

  • для каждого результата в ;
  • 0 за каждый результат в .

Вектор выигрышных значений всех агентов обозначается через .

Для каждого агента вектор всех выигрышных значений других агентов обозначается через . Так .

Функция социального выбора — это функция, которая принимает в качестве входных данных вектор ценностей. и возвращает результат . Это обозначается или .

Монотонность

[ редактировать ]

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

и
затем:

Т.е., если агент выигрывает, объявив определенное значение, то он также может выиграть, объявив более высокое значение (когда объявления других агентов одинаковы).

Свойство монотонности можно обобщить на случайные механизмы, которые возвращают распределение вероятностей в пространстве. . [ 1 ] : 334  Свойство WMON подразумевает, что для каждого агента и каждый , функция:

является слабовозрастающей функцией .

Критическое значение

[ редактировать ]

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

Например, на аукционе второй цены критическое значение для агента это самая высокая ставка среди других агентов.

В однопараметрических средах детерминированные правдивые механизмы имеют очень специфический формат. [ 1 ] : 334  Любой детерминированный правдивый механизм полностью определяется набором функций c. Агент выигрывает тогда и только тогда, когда его ставка не менее , и в этом случае он платит ровно .

Детерминированная реализация

[ редактировать ]

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

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

Механизм должен работать следующим образом: [ 1 ] : 229 

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

Этот механизм правдив, потому что чистая полезность каждого агента равна:

  • если он выиграет;
  • 0, если он проиграет.

Следовательно, агент предпочитает выиграть, если и проиграть, если , именно это и происходит, когда он говорит правду.

Рандомизированная реализация

[ редактировать ]

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

В рандомизированном механизме каждый агент имеет вероятность выигрыша, определяемую как:

и ожидаемый платеж, определяемый как:

В однопараметрической области рандомизированный механизм является правдивым в ожидании тогда и только тогда, когда: [ 1 ] : 232 

  • Вероятность выигрыша, , является слабо возрастающей функцией ;
  • Ожидаемый гонорар агента составляет:

Обратите внимание, что в детерминированном механизме равно 0 или 1, первое условие сводится к слабомонотонности функции Результат, а второе условие сводится к начислению каждому агенту его критического значения.

Однопараметрические и многопараметрические домены

[ редактировать ]

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

См. также

[ редактировать ]
  1. ^ Jump up to: а б с д и Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  0-521-87282-0 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: a97cbb3db49f1310ba3dda11f498d1db__1664736900
URL1:https://arc.ask3.ru/arc/aa/a9/db/a97cbb3db49f1310ba3dda11f498d1db.html
Заголовок, (Title) документа по адресу, URL1:
Single-parameter utility - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)