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

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

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

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

Свойства [ править ]

Саморазоблачение / совместимость со стимулами [ править ]

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

Эффективность постфактум [ править ]

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

Слабые стороны [ править ]

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

Механизм Викри-Кларка-Гровса (ВКГ) имеет дополнительные недостатки:

• Это уязвимо для сговора участников торгов . Если все участники аукциона Викри раскрывают друг другу свои оценки, они могут снизить некоторые или все свои оценки, сохранив при этом победителя аукциона. ^[7]
• Он уязвим для варианта торгов за шиллы, в котором покупатель использует несколько идентификаторов на аукционе, чтобы максимизировать свою прибыль. ^[8]
• Это не обязательно максимизирует доходы продавца; на аукционах VCG доходы продавца могут быть нулевыми. Если целью проведения аукциона является максимизация прибыли для продавца, а не просто распределение ресурсов между покупателями, то VCG может быть плохим выбором.
• Выручка продавца немонотонна по отношению к совокупности участников торгов и предложений.

Немонотонность доходов продавца по отношению к заявкам (без введения механизма альтернативных издержек VCG, описанного в конце этой статьи) можно показать на следующем примере. Рассмотрим трех участников аукциона A, B и C, а также двух однородных товаров Y и Z.

• A хочет оба товара и предлагает 2 доллара за пакет Y и Z.
• B и C предлагают по 2 доллара каждый за один предмет (ставят 2 доллара за Y или Z), поскольку им действительно нужен один предмет, но им все равно, есть ли у них второй.

Теперь Y и Z распределены между B и C, но цена составляет 0 долларов, что можно найти, удалив B или C соответственно. Если C предложит 0 долларов вместо 2 долларов, то продавец получит 2 доллара вместо 0 долларов. Поскольку выручка продавца может увеличиваться при увеличении или уменьшении ставок, доходы продавца немонотонны по отношению к ставкам.

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

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

Пусть будет стоимость товара i участником аукциона. Пусть будет заявка участника аукциона i за товар. B Выплата для участника торгов i составляет${\ displaystyle v_ {i}}$${\ displaystyle b_ {i}}$${\ displaystyle {\ begin {cases} v_ {i} - \ max _ {j \ neq i} b_ {j} & {\ text {if}} b_ {i}> \ max _ {j \ neq i} b_ {j} \\ 0 & {\ text {иначе}} \ end {case}}}$

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

Если тогда участник торгов выиграет лот как с правдивой, так и с перекупленной ставкой. Сумма ставки не влияет на выплату, поэтому в этом случае обе стратегии имеют равные выплаты.${\ Displaystyle \ макс _ {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}}$

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

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

Если тогда участник торгов выиграет товар в любом случае, то в этом случае стратегии будут иметь равные выплаты.${\ Displaystyle \ макс _ {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 х <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 в сетевой маршрутизации состоит в том, чтобы заплатить владельцу каждого канала или узла (в зависимости от сетевой модели), который является частью решения, его заявленную стоимость плюс добавленную стоимость. Во многих задачах маршрутизации этот механизм не только защищен от стратегии , но и является минимальным среди всех механизмов защиты от стратегии.

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

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

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

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

В 2004 г. было показано , что ожидаемый ВКГ переплата из случайного графа Эрдеша-Рение с п узлами и вероятностью края р , подходы${\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.
• Питер Крэмтон, Йоав Шохам, Ричард Стейнберг (редакторы), Combinatorial Auctions , MIT Press, 2006, глава 1. ISBN  0-262-03342-9 .
• Пол Милгром, Применение теории аукционов на практике , Cambridge University Press, 2004.
• Тек Хо, «Потребление и производство» Калифорнийского университета в Беркли, класс Haas, 2010 г.

Заметки [ править ]