Цените соглашение

Консенсусная оценка — это метод проектирования правдивых механизмов в условиях проектирования механизмов без априорной обработки . Методику внедрили на аукционах цифровых товаров. ^{[ 1 ]} и позже расширен до более общих настроек. ^{[ 2 ]}

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

Попросите покупателей сообщить свою оценку.
Рассчитать $R_{max}$ - максимально возможная прибыль с учетом оценок.
Рассчитайте цену, которая гарантирует, что мы получим прибыль в размере $R_{max}$ .

Шаг 3 может быть достигнут с помощью механизма извлечения прибыли , который является правдивым механизмом . Однако в целом механизм не правдив, поскольку покупатели могут попытаться повлиять на ситуацию. $R_{max}$ стратегически делая ставки. Чтобы решить эту проблему, мы можем заменить точное $R_{max}$ с приближением - $R_{app}$ - на которые с большой вероятностью не может повлиять один агент. ^{[ 3 ]}^{: 349–350}

В качестве примера предположим, что мы знаем, что оценка каждого отдельного агента не превышает 0,1. В качестве первой попытки консенсусной оценки позвольте $R_{app}=\lfloor R_{max}\rfloor$ = значение $R_{max}$ округляется до ближайшего целого числа ниже него. Интуитивно понятно, что в «большинстве случаев» один агент не может повлиять на стоимость $R_{app}$ (например, если с достоверными отчетами $R_{max}=56.7$ , то один агент может изменить его только между $R_{max}=56.6$ и $R_{max}=56.8$ , но во всех случаях $R_{app}=56$ ).

Чтобы сделать понятие «большинство случаев» более точным, определим: $R_{app}=\lfloor R_{max}+U\rfloor$ , где $U$ это случайная величина, полученная равномерно из $[0,1]$ . Это делает $R_{app}$ тоже случайная величина. С вероятностью не менее 90%, $R_{app}$ не может находиться под влиянием какого-либо отдельного агента, поэтому механизм, использующий $R_{app}$ правдиво с высокой вероятностью.

Такая случайная величина $R_{app}$ называется консенсусной оценкой :

«Консенсус» означает, что с высокой вероятностью один агент не может повлиять на результат, поэтому существует согласие между результатами с агентом или без него.
«Оценка» означает, что случайная величина находится рядом с интересующей нас реальной величиной – переменной $R_{max}$ .

Недостатками использования консенсусной оценки являются:

Это не дает нам оптимальной прибыли, но дает нам приблизительно оптимальную прибыль.
Оно не совсем правдиво — оно лишь «правдиво с высокой вероятностью» (вероятность того, что агент сможет получить выгоду от отклонения, обращается в 0 при росте числа выигравших агентов). ^{[ 3 ]}^: 349

На практике вместо округления до ближайшего целого числа лучше использовать экспоненциальное округление – округление до ближайшей степени некоторой константы. ^{[ 3 ]}^: 350 В случае цифровых товаров использование этой консенсусной оценки позволяет нам достичь как минимум 1/3,39 оптимальной прибыли даже в худших сценариях.

См. также

Механизм случайной выборки — альтернативный подход к проектированию механизма без априорной выборки .

Ссылки

^ Эндрю В. Голдберг, Джейсон Д. Хартлайн (2003). «Конкурентоспособность через консенсус» . Материалы четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . СОДА 03 . Проверено 14 марта 2016 г.
^ Ха, Бах К.; Хартлайн, Джейсон Д. (2013). «Разработка механизма с помощью консенсусных оценок, перекрестной проверки и извлечения прибыли». Транзакции ACM по экономике и вычислениям . 1 (2): 1. arXiv : 1108.4744 . дои : 10.1145/2465769.2465773 .
^ Jump up to: ^а ^б ^с Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0 .

[gh03-1] Эндрю В. Голдберг, Джейсон Д. Хартлайн (2003). «Конкурентоспособность через консенсус» . Материалы четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . СОДА 03 . Проверено 14 марта 2016 г.

[2] Ха, Бах К.; Хартлайн, Джейсон Д. (2013). «Разработка механизма с помощью консенсусных оценок, перекрестной проверки и извлечения прибыли». Транзакции ACM по экономике и вычислениям . 1 (2): 1. arXiv : 1108.4744 . дои : 10.1145/2465769.2465773 .

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

[ 1 ]

[ 2 ]

[ 3 ]