Аукцион Викри

Аукцион Викри или аукцион второй цены с закрытыми предложениями ( SBSPA ) — это тип аукциона с закрытыми предложениями . Участники торгов подают письменные заявки, не зная ставок других участников аукциона. Выигрывает тот, кто предложит самую высокую цену, но уплаченная цена будет второй по величине ставкой. Этот тип аукциона стратегически подобен английскому аукциону и дает участникам аукциона стимул предлагать свою истинную цену . Аукцион был впервые академически описан Колумбийского университета профессором Уильямом Викри в 1961 году. ^[1] использовали его хотя коллекционеры марок с 1893 года. ^[2] В 1797 году Иоганн Вольфганг фон Гете продал рукопись на аукционе второй цены с закрытыми торгами. ^[3]

В оригинальной статье Викри в основном рассматривались аукционы, на которых продается только один неделимый товар. Термины «аукцион Викри» и «аукцион с закрытыми предложениями второй цены» только в этом случае эквивалентны и используются как взаимозаменяемые. В случае наличия нескольких идентичных товаров участники торгов представляют обратные кривые спроса и оплачивают альтернативные издержки . ^[4]

Аукционы Викри широко изучаются в экономической литературе, но на практике встречаются редко. Существуют обобщенные варианты аукциона Викри для многоквартирных аукционов , такие как обобщенный аукцион второй цены, используемый в программах онлайн-рекламы Google и Yahoo! ^[5]^[6] ( несовместимо со стимулами ) и аукцион Викри-Кларка-Гроувса (совместимо со стимулами).

Характеристики

Совместимость самораскрытия и стимулов

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

Фактическая эффективность

Аукцион Викри является эффективным решением (победителем становится участник торгов с самой высокой оценкой) при самых общих обстоятельствах; ^{[ нужна ссылка ]} таким образом, он обеспечивает базовую модель, на основе которой можно определить свойства эффективности других типов аукционов. Это эффективно только постфактум (сумма трансферов равна нулю), если продавец включен в качестве «нулевого игрока», чей трансфер равен отрицательной сумме трансферов других игроков (т.е. ставок).

Слабые стороны

Он не позволяет определять цену , то есть определять рыночную цену, если покупатели не уверены в своих оценках, без последовательных аукционов.
Продавцы могут использовать коммерческие предложения для увеличения прибыли. ^{[ нужна ссылка ]}

Доказательство доминирования правдивых торгов

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

Позволять $v_{i}$ быть участником торгов, цена которого указана за товар. Позволять $b_{i}$ быть участником торгов $i{\text{'s}}$ ставка за товар. Выплата для участника торгов $i$ является

{\begin{cases}v_{i}-\max _{j\neq i}b_{j}&{\text{if }}b_{i}>\max _{j\neq i}b_{j},\\0&{\text{otherwise.}}\end{cases}}

В стратегии завышения ставок преобладает честное предложение ставок (т.е. $v_{i}$ ). Предположим, что участник торгов $i$ ставки $b_{i}>v_{i}$ .

Если $\max _{j\neq i}b_{j}<v_{i}$ тогда участник торгов выиграет лот как с правдивой ставкой, так и с завышенной ставкой. Сумма ставки не меняет выигрыш, поэтому в этом случае обе стратегии имеют равные выигрыши.

Если $\max _{j\neq i}b_{j}>b_{i}$ тогда участник торгов в любом случае потеряет товар, поэтому в этом случае стратегии будут иметь равные выигрыши.

Если $v_{i}<\max _{j\neq i}b_{j}<b_{i}$ тогда только стратегия завышения ставок позволит выиграть аукцион. Выигрыш будет отрицательным для стратегии завышения цены, поскольку они заплатили больше, чем их стоимость товара, в то время как выигрыш для правдивой ставки будет равен нулю. Таким образом, стратегия предложения ставок выше реальной оценки доминирует над стратегией правдивых ставок.

В стратегии занижения ставок преобладает честное предложение ставок. Предположим, что участник торгов $i$ ставки $b_{i}<v_{i}$ .

Если $\max _{j\neq i}b_{j}>v_{i}$ тогда участник торгов потеряет товар как с правдивой ставкой, так и с заниженной ставкой, поэтому в этом случае стратегии имеют равные выигрыши.

Если $\max _{j\neq i}b_{j}<b_{i}$ тогда участник торгов выиграет лот в любом случае, поэтому в этом случае стратегии будут иметь равные выигрыши.

Если $b_{i}<\max _{j\neq i}b_{j}<v_{i}$ тогда только стратегия честных торгов позволит выиграть аукцион. Выплата за правдивую стратегию будет положительной, поскольку они заплатят меньше, чем их стоимость товара, в то время как выигрыш за заниженную ставку будет равен нулю. Таким образом, стратегия занижения цен доминирует над стратегией правдивых торгов.

Правдивые ставки доминируют над другими возможными стратегиями (занижение и завышение ставок), поэтому это оптимальная стратегия.

Эквивалент выручки аукциона Викри и закрытого аукциона первой цены

Двумя наиболее распространенными аукционами являются закрытые аукционы по первой цене (или с высокой ставкой) и аукцион по открытой возрастающей цене (или по-английски). В первом случае каждый покупатель подает запечатанную заявку. Участник, предложивший самую высокую цену, получает лот и платит свою ставку. В последнем случае аукционист последовательно объявляет более высокие запрашиваемые цены и продолжает это делать до тех пор, пока никто не захочет принять более высокую цену. Предположим, что оценка покупателя равна $v$ и текущая запрашиваемая цена $b$ . Если $v<b$ , то покупатель проигрывает, подняв руку. Если $v>b$ и покупатель не является текущим участником, предложившим самую высокую цену, выгоднее сделать ставку, чем позволить кому-то другому стать победителем. Таким образом, доминирующей стратегией покупателя является отказ от участия в торгах, когда запрашиваемая цена достигает его или ее оценки. Таким образом, как и на закрытом аукционе второй цены Викри, цена, уплаченная покупателем с самой высокой оценкой, равна второй по величине стоимости.

Рассмотрим затем ожидаемый платеж на закрытом аукционе второй цены. Викри рассмотрел случай двух покупателей и предположил, что стоимость каждого покупателя является независимым результатом равномерного распределения с поддержкой $[0,1]$ . Поскольку покупатели делают ставки в соответствии со своими доминирующими стратегиями, покупатель с оценкой $v$ выигрывает, если ценность его противника $x<v$ . Предположим, что $v$ это высокая ценность. Тогда выигрышная выплата равномерно распределяется на интервале $[0,v]$ и поэтому ожидаемый платеж победителя равен

e(v)={\tfrac {1}{2}}v.

Теперь мы утверждаем, что на закрытом аукционе по первой цене равновесная ставка покупателя с оценкой $v$ является

B(v)=e(v)={\tfrac {1}{2}}v.

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

Доказательство эквивалентности доходов

Предположим, что покупатель 2 делает ставку по стратегии $B(v)=v/2$ , где $B(v)$ это предложение покупателя на оценку $v$ . Нам нужно показать, что лучший ответ покупателя 1 — использовать ту же стратегию.

Прежде всего обратите внимание, что если покупатель 2 использует стратегию $B(v)=v/2$ , то максимальная ставка покупателя 2 равна $B(1)=1/2$ и поэтому покупатель 1 выигрывает с вероятностью 1 при любой ставке 1/2 или более. Тогда рассмотрим ставку $b$ на интервале $[0,1/2]$ . Пусть стоимость покупателя 2 равна $x$ . Тогда покупатель 1 выигрывает, если $B(x)=x/2<b$ , то есть, если $x<2b$ . Согласно предположению Викри о равномерном распределении значений, вероятность победы равна $w(b)=2b$ . Таким образом, ожидаемый выигрыш покупателя 1 составит

U(b)=w(b)(v-b)=2b(v-b)={\tfrac {1}{2}}[v^{2}-(v-2b)^{2}]

Обратите внимание, что $U(b)$ принимает максимум при $b=v/2=B(v)$ .

Использование в сетевой маршрутизации

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

В случае сетевых потоков, одноадресных или многоадресных , поток минимальной стоимости (MCF) в графе G рассчитывается на основе заявленных затрат d _k каждого из каналов, а оплата рассчитывается следующим образом:

Каждая ссылка (или узел) $e_{k}$ в МКФ выплачивается

p_{k}=d_{k}+\operatorname {MCF} (G-e_{k})-\operatorname {MCF} (G),

где MCF( G ) указывает стоимость потока с минимальной стоимостью в графе G , а G − e _k указывает на граф G без связи e _k . Ссылки, не входящие в MCF, не оплачиваются. Эта проблема маршрутизации является одним из случаев, когда VCG является стратегически устойчивым и минимальным.

В 2004 году было показано, что ожидаемая переплата VCG случайного графа Эрдеша – Реньи с n узлами и вероятностью ребра p , $\scriptstyle G\in G(n,p)$ подходы

{\frac {p}{2-p}}

как n , приближается $\scriptstyle \infty$ , для $np=\omega ({\sqrt {n\log n}})$ . До этого результата было известно, что Переплата ВКГ в G ( n , p ) равна

\Omega \left({\frac {1}{np}}\right)

и

O(1)\,

с высокой вероятностью, учитывая

np=\omega (\log n).\,

Обобщения

Наиболее очевидным обобщением для нескольких или делимых товаров является требование, чтобы все выигравшие участники торгов заплатили сумму самой высокой проигрышной ставки. Это известно как аукцион с единой ценой . Однако аукцион по единой цене не приводит к тому, что участники торгов предлагают свои истинные цены, как это происходит на аукционе второй цены, если только каждый участник торгов не предъявляет спрос только на одну единицу товара. Обобщенный вариант аукциона Викри, который сохраняет стимул делать правдивые ставки, известен как механизм Викри-Кларка-Гроувса (VCG). Идея VCG заключается в том, что элементы назначаются так, чтобы максимизировать сумму полезностей; затем каждый участник торгов платит «альтернативную стоимость», которую его присутствие представляет для всех остальных игроков. Эти альтернативные издержки для участника торгов определяются как общие ставки всех остальных участников торгов, которые выиграли бы, если бы первый участник торгов не сделал ставки, за вычетом общих ставок всех остальных фактически выигравших участников торгов.

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

В конструкции механизма принцип раскрытия можно рассматривать как обобщение аукциона Викри.

См. также

Ссылки

Виджай Кришна, Теория аукционов , Academic Press, 2002.
Питер Крэмтон, Йоав Шохам, Ричард Стейнберг (редакторы), Комбинаторные аукционы , MIT Press, 2006, Глава 1. ISBN 0-262-03342-9 .
Пол Милгром, Применение теории аукционов на практике , издательство Кембриджского университета, 2004.
Тек Хо, «Потребление и производство», Калифорнийский университет в Беркли, выпуск Haas, 2010 г.

Примечания

^ Викри, Уильям (1961). «Контрспекуляции, аукционы и закрытые тендеры». Журнал финансов . 16 (1): 8–37. дои : 10.1111/j.1540-6261.1961.tb02789.x .
^ Лакинг-Рейли, Дэвид (2000). «Аукционы Викри на практике: от филателии девятнадцатого века к электронной коммерции двадцать первого века» . Журнал экономических перспектив . 14 (3): 183–192. дои : 10.1257/jep.14.3.183 .
^ Бенни Молдовану и Манфред Титцель (1998). «Аукцион второй цены Гете». Журнал политической экономии . 106 (4): 854–859. CiteSeerX 10.1.1.560.8278 . дои : 10.1086/250032 . JSTOR 2990730 . S2CID 53490333 .
^ Джонс, Дерек (2003). «Теория аукционов для новой экономики». Справочник по новой экономике . Эмеральд Паблишинг Лтд. ISBN 978-0123891723 .
^ Бенджамин Эдельман, Майкл Островский и Майкл Шварц: «Интернет-реклама и обобщенный аукцион второй цены: продажа ключевых слов на миллиарды долларов». American Economic Review 97 (1), 2007, стр. 242–259.
^ Хэл Р. Вариан: «Аукционы позиций». Международный журнал промышленной организации, 2006 г., дои : 10.1016/j.ijindorg.2006.10.002 .
^ фон Ан, Луис (30 сентября 2008 г.). «Аукционы» (PDF) . 15–396: Примечания к веб-курсу «Наука» . Университет Карнеги-Меллон. Архивировано из оригинала (PDF) 8 октября 2008 года . Проверено 6 ноября 2008 г.

[1] Викри, Уильям (1961). «Контрспекуляции, аукционы и закрытые тендеры». Журнал финансов . 16 (1): 8–37. дои : 10.1111/j.1540-6261.1961.tb02789.x .

[2] Лакинг-Рейли, Дэвид (2000). «Аукционы Викри на практике: от филателии девятнадцатого века к электронной коммерции двадцать первого века» . Журнал экономических перспектив . 14 (3): 183–192. дои : 10.1257/jep.14.3.183 .

[3] Бенни Молдовану и Манфред Титцель (1998). «Аукцион второй цены Гете». Журнал политической экономии . 106 (4): 854–859. CiteSeerX 10.1.1.560.8278 . дои : 10.1086/250032 . JSTOR 2990730 . S2CID 53490333 .

[4] Джонс, Дерек (2003). «Теория аукционов для новой экономики». Справочник по новой экономике . Эмеральд Паблишинг Лтд. ISBN 978-0123891723 .

[5] Бенджамин Эдельман, Майкл Островский и Майкл Шварц: «Интернет-реклама и обобщенный аукцион второй цены: продажа ключевых слов на миллиарды долларов». American Economic Review 97 (1), 2007, стр. 242–259.

[6] Хэл Р. Вариан: «Аукционы позиций». Международный журнал промышленной организации, 2006 г., дои : 10.1016/j.ijindorg.2006.10.002 .

[7] фон Ан, Луис (30 сентября 2008 г.). «Аукционы» (PDF) . 15–396: Примечания к веб-курсу «Наука» . Университет Карнеги-Меллон. Архивировано из оригинала (PDF) 8 октября 2008 года . Проверено 6 ноября 2008 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]