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

редактировать
Аукцион со второй по величине запечатанной ставкой

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

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

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

Содержание

  • 1 Свойства
    • 1.1 Саморазоблачение / совместимость со стимулами
    • 1.2 Фактическая эффективность
    • 1.3 Слабые стороны
  • 2 Доказательство доминирования правдивых торгов
  • 3 Выручка, эквивалентная Аукцион Викри и запечатанный аукцион первой цены
  • 4 Использование в сетевой маршрутизации
  • 5 Обобщения
  • 6 См. Также
  • 7 Ссылки
  • 8 Примечания

Свойства

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

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

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

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

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

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

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

  • Он уязвим для участников аукциона сговор. Если все участники аукциона Викри раскрывают свои оценки друг другу, они могут снизить некоторые или все свои оценки, сохранив при этом, кто выиграет аукцион.
  • Это уязвимо для варианта торга в шиллах, в котором покупатель использует множественные идентичности на аукционе с целью максимизации его прибыли.
  • Это не обязательно максимизирует доходы продавца; на аукционах 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 долларов. Поскольку выручка продавца может увеличиваться при увеличении или уменьшении ставок, доходы продавца немонотонны по отношению к ставкам.

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

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

Пусть vi {\ displaystyle v_ {i}}v_{i}будет значением покупателя i для элемента. Пусть b i {\ displaystyle b_ {i}}b_{i}будет ставкой i покупателя за товар.

Выплата для участника торгов i составляет {vi - max j ≠ ibj, если bi>max j ≠ ibj 0, в противном случае {\ displaystyle {\ begin {cases} v_ {i} - \ max _ {j \ neq i} b_ {j} {\ text {if}} b_ {i}>\ max _ {j \ neq i} b_ {j} \\ 0 {\ text {else}} \ end {cases}} }{\begin{cases}v_{i}-\max _{{j\neq i}}b_{j}{\text{if }}b_{i}>\ max _ {{j \ neq i}} b_ {j} \\ 0 {\ text {иначе}} \ end {cases}}

В стратегии завышения ставок преобладает правдивое назначение ставок. bi>vi {\ displaystyle b_ {i}>v_ {i}}b_{i}>v_ {i} .

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

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

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

В стратегии снижения ставок преобладают делает ставку честно. Предположим, что участник аукциона i делает ставку bi < v i {\displaystyle b_{i}b_ {i} <v_ {i} .

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

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

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

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

Выручка, эквивалентная аукциону Викри и аукциону с запечатанной первой ценой

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

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

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

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

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

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

Подтверждение эквивалентности доходов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и

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

с высокой вероятностью, заданной

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

Обобщения

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

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

См. Также

Ссылки

  • Виджай Кришна, Auction Theory, Academic Press, 2002.
  • Питер Крэмтон, Йоав Шохам, Ричард Стейнберг (редакторы), Combinatorial Auctions, MIT Press, 2006, глава 1. ISBN 0-262-03342 -9.
  • Пол Милгром, Применение теории аукционов на практике, Cambridge University Press, 2004.
  • Тек Хо, «Потребление и производство» Калифорнийского университета в Беркли, класс Haas 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.
  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. ^"Vickrey Auction". maxi-pedia.com.
  8. ^Лоуренс М. Осубель и Пол Милгром. Аукцион милых, но одиноких Викри. Комбинаторные аукционы, MIT Press, 2006, глава 1, стр. 12,.
  9. ^фон Ан, Луис (30 сентября 2008 г.). «Аукционы» (PDF). 15–396: Заметки о веб-курсе. Университет Карнеги Меллон. Архивировано из оригинального (PDF) 8 октября 2008 г. Дата обращения 6 ноября 2008 г.
Последняя правка сделана 2021-06-18 12:27:30
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте