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

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

Обозначения

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

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

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

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

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

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

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

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

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

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

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

{\text{Outcome}}(v_{i},v_{-i})\in W_{i}

и

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

затем:

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

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

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

\Pr[{\text{Outcome}}(v_{i},v_{-i})\in W_{i}]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\mathbb {E} [{\text{Payment}}_{i}(v_{i},v_{-i})]

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

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

\mathbb {E} [{\text{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

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

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

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

См. также

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

Ссылки

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

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

[ 1 ]