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

Single-parameter utility

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

Обозначение

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

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

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

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

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

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

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

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

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

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

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

и
тогда:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Рекомендации

  1. ^ а б c d е Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.