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

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

Обозначение

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

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

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

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

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

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

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

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

А социальный выбор функция - это функция, которая принимает на вход вектор-значение ${\displaystyle v}$ и возвращает результат ${\displaystyle x\in X}$. Обозначается он ${\displaystyle Outcome(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}$ выигрывает, объявляя определенное значение, тогда он также может выиграть, объявив более высокое значение (когда декларации других агентов совпадают).

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

${\displaystyle Prob[Outcome(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=Outcome[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 если он проиграет.

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

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

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

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

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

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

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

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

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

${\displaystyle 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}$

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

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

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

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

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

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

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