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

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

Обозначение

Есть набор возможных исходов. ${\ displaystyle X}$

Есть агенты, которые по-разному оценивают каждый результат. ${\ displaystyle n}$

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

В особом случае однопараметрической полезности каждый агент имеет общеизвестное собственное подмножество исходов, которые являются «выигрышными результатами» для агента (например, в аукционе с одним предметом, содержащий результат, в котором агент выигрывает предмет). ${\ displaystyle i}$ ${\ displaystyle W_ {i} \ subset X}$ ${\ displaystyle i}$ ${\ displaystyle W_ {i}}$ ${\ displaystyle i}$

Для каждого агента есть число, которое представляет «выигрышную ценность» . Оценка агентом результатов может принимать одно из двух значений: ^[1]^{: 228} ${\ displaystyle v_ {i}}$ ${\ displaystyle i}$ ${\ displaystyle X}$

${\ displaystyle v_ {i}}$ для каждого исхода в ; ${\ displaystyle W_ {i}}$
0 для каждого результата в . ${\ Displaystyle X \ setminus W_ {i}}$

Вектор выигрышных значений всех агентов обозначен как . ${\ displaystyle v}$

Для каждого агента вектор всех выигрышных значений других агентов обозначается . Итак . ${\ displaystyle i}$ ${\ displaystyle v _ {- i}}$ ${\ Displaystyle v \ эквив (v_ {я}, v _ {- я})}$

Функция общественного выбора - это функция, которая принимает на вход вектор-значение и возвращает результат . Обозначается он или . ${\ displaystyle v}$ ${\ displaystyle x \ in X}$ ${\ Displaystyle Результат (v)}$ ${\ displaystyle Outcome (v_ {i}, v _ {- i})}$

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

Слабая монотонность свойство имеет специальную форму в однопараметрических доменах. Функция общественного выбора является слабо-монотонной, если для каждого агента и каждого , если: ${\ displaystyle i}$ ${\ displaystyle v_ {i}, v_ {i} ', v _ {- i}}$

{\ displaystyle Outcome (v_ {i}, v _ {- i}) \ in W_ {i}}

а также

{\ displaystyle v '_ {i} \ geq v_ {i}> 0}

тогда:

{\ displaystyle Outcome (v '_ {i}, v _ {- i}) \ in W_ {i}}

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

Свойство монотонности можно обобщить на рандомизированные механизмы, которые возвращают распределение вероятностей в пространстве . ^[1]^{: 334} Свойство WMON подразумевает, что для каждого агента и каждого функция: ${\ displaystyle X}$ ${\ displaystyle i}$ ${\ displaystyle v_ {i}, v_ {i} ', v _ {- i}}$

{\ displaystyle Prob [Результат (v_ {i}, v _ {- i}) \ in W_ {i}]}

является слабо возрастающей функцией . ${\ displaystyle v_ {i}}$

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

Для каждой слабо монотонной функции общественного выбора, для каждого агента и для каждого вектора существует критическое значение , такое, что агент выигрывает тогда и только тогда, когда его ставка не меньше . ${\ displaystyle i}$ ${\ displaystyle v _ {- i}}$ ${\ displaystyle c_ {i} (v _ {- i})}$ ${\ displaystyle i}$ ${\ displaystyle c_ {i} (v _ {- i})}$

Например, на аукционе второй цены критической ценностью для агента является самая высокая ставка среди других агентов. ${\ displaystyle i}$

В однопараметрических средах детерминированные правдивые механизмы имеют очень специфический формат. ^[1]^{: 334} Любой детерминированный истинный механизм полностью определяется набором функций c. Агент выигрывает тогда и только тогда, когда его ставка не меньше , и в этом случае он платит точно . ${\ displaystyle i}$ ${\ displaystyle c_ {i} (v _ {- i})}$ ${\ displaystyle c_ {i} (v _ {- i})}$

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

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

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

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

Попросите агентов раскрыть свои оценки . ${\ displaystyle v}$
Выберите результат , основанный на функции социального выбора: . ${\ displaystyle x = Результат [v]}$
Каждый выигрыш агент (каждый агент таким образом, что ) платит цену , равную критическое значение: . ${\ displaystyle i}$ ${\ displaystyle x \ in W_ {i}}$ ${\ displaystyle Price_ {i} (x, v _ {- i}) = - c_ {i} (v _ {- i})}$
Каждый проигрышной агент (каждый агент таким образом, что ) ничего не платит: . ${\ displaystyle i}$ ${\ displaystyle x \ notin W_ {i}}$ ${\ displaystyle Price_ {i} (x, v _ {- i}) = 0}$

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

${\ displaystyle v_ {i} -c_ {i} (v _ {- i})}$ если он выиграет;
0 если он проиграет.

Следовательно, агент предпочитает выигрывать, если и проигрывать, если , что именно и происходит, когда он говорит правду. $v_{i}>c_{-i}$ $v_{i}<c_{-i}$

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

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

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

w_{i}(v_{i},v_{-i}):=\Pr[Outcome(v_{i},v_{-i})\in W_{i}]

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

E[Payment_{i}(v_{i},v_{-i})]

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

Вероятность выигрыша, является слабо возрастающей функцией от ; $w_{i}(v_{i},v_{-i})$ $v_{i}$
Ожидаемый платеж агента:

E[Payment_{i}(v_{i},v_{-i})]=v_{i}\cdot w_{i}(v_{i},v_{-i})-\int _{0}^{v_{i}}w_{i}(t,v_{-i})dt

Обратите внимание, что в детерминированном механизме, это либо 0, либо 1, первое условие сводится к слабомонотонности функции Outcome, а второе условие сводится к начислению каждому агенту его критического значения. $w_{i}(v_{i},v_{-i})$

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

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

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

Однопиковые предпочтения

использованная литература

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

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

[1]