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

Аукцион, цена которого установлена ​​на основе второй по величине закрытой ставки

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

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

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

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

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

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

Эффективность ex-post

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

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

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

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

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

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

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

Стратегия перекупки доминирует при честной ставке (т.е. ставке ). Предположим, что участник торгов делает ставку . ${\displaystyle v_{i}}$ ${\displaystyle i}$ ${\displaystyle b_{i}>v_{i}}$

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

Таким образом, стратегия предложения цены выше своей истинной оценки доминируется стратегией честного предложения цены. Стратегия предложения цены ниже цены также доминируется стратегией честного предложения цены. Предположим, что претендент делает ставку . ${\displaystyle i}$ ${\displaystyle b_{i}<v_{i}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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 приближается к ${\displaystyle \scriptstyle G\in G(n,p)}$

${\displaystyle {\frac {p}{2-p}}}$

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

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

и

${\displaystyle O(1)\,}$

с высокой вероятностью

${\displaystyle np=\omega (\log n).\,}$

Обобщения

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

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

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

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

• Теория аукциона
• Аукцион с закрытыми ставками первой цены
• Аукцион VCG

Ссылки

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

Примечания

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