Последовательный аукцион

Последовательный аукцион — это аукцион , на котором один за другим продаются несколько предметов одной и той же группе потенциальных покупателей. На последовательном аукционе первой цены (SAFP) каждый отдельный предмет продается с использованием аукциона первой цены , а на последовательном аукционе второй цены (SASP) каждый отдельный предмет продается с использованием аукциона второй цены .

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

Пример 1 . ^[1] На продажу выставлены два объекта и два потенциальных покупателя: Алиса и Боб, со следующими оценками:

Алиса оценивает каждый предмет как 5, а оба предмета — как 10 (т. е. ее оценка аддитивна ).
Боб оценивает каждый товар как 4, а оба товара — как 4 (т. е. его оценка равна спросу на единицу товара ).

В SASP каждый товар выставляется на аукцион второй цены. Обычно такой аукцион представляет собой правдивый механизм , поэтому, если каждый предмет продается отдельно, Алиса выигрывает оба предмета и платит 4 за каждый предмет, ее общий платеж равен 4+4=8, а ее чистая полезность равна 5 + 5 − 8 = 2. Но если Алиса знает оценки Боба, у нее есть лучшая стратегия: она может позволить Бобу выиграть первый предмет (например, предложив 0). Тогда Боб вообще не будет участвовать во втором аукционе, поэтому Алиса выиграет второй предмет и заплатит 0, а ее чистая полезность составит 5 − 0 = 5.

Аналогичный результат происходит и в SAFP. Если каждый предмет продается по отдельности, существует равновесие Нэша , при котором Алиса делает ставку немного выше 4 и выигрывает, а ее чистая полезность немного ниже 2. Но если Алиса знает оценки Боба, она может отклониться к стратегии, которая позволит Бобу выиграть. в первом раунде, чтобы во втором раунде она могла выиграть по цене чуть выше 0.

Пример 2 . ^[2] На аукционе выставляется несколько одинаковых объектов, и у агентов есть ограничения по бюджету. Участнику торгов может быть выгодно агрессивно предлагать цену за один объект с целью поднять цену, уплачиваемую его соперником, и истощить свой бюджет, чтобы затем второй объект можно было приобрести по более низкой цене. По сути, участник торгов может пожелать «повысить затраты конкурента» на одном рынке, чтобы получить преимущество на другом. Подобные соображения, похоже, сыграли значительную роль на аукционах по лицензиям на радиочастоты , проводимых Федеральной комиссией по связи . Оценка бюджетных ограничений конкурирующих участников торгов была основным компонентом предтендерной подготовки тендерной группы GTE .

Равновесие Нэша

Последовательный аукцион — это частный случай последовательной игры . Естественный вопрос, который следует задать в такой игре, заключается в том, существует ли идеальное равновесие подыгры в чистых стратегиях (SPEPS). Когда игроки обладают полной информацией (т. е. заранее знают последовательность аукционов) и в каждом раунде продается один предмет, SAFP всегда имеет SPEPS, независимо от оценок игроков. Доказательство проводится методом обратной индукции : ^[1]^{: 872–874}

В последнем раунде у нас есть простой аукцион первой цены . Он имеет чисто стратегическое равновесие Нэша, в котором агент с наивысшей стоимостью выигрывает, предлагая цену немного выше второй по величине стоимости.
В каждом предыдущем раунде ситуация представляет собой частный случай аукциона первой цены с внешними эффектами . На таком аукционе каждый агент может получить выгоду не только тогда, когда он выигрывает, но и когда выигрывают другие агенты. В целом оценка агента $i$ $я$ представлен вектором $v_{i}[1],\dots ,v_{i}[n]$ $v_{i}[1],\dots ,v_{i}[n]$ , где $v_{i}[j]$ $v_{i}[j]$ стоимость агента $i$ $я$ когда агент $j$ $j$ побеждает. В последовательном аукционе внешние эффекты определяются равновесными результатами будущих раундов. Во вводном примере есть два возможных результата:
- Если Алиса выиграет первый раунд, то равновесным результатом второго раунда будет то, что Алиса купит предмет стоимостью 5 долларов за 4 доллара. ^[3] поэтому ее чистая прибыль равна 1 доллару. Следовательно, ее общая стоимость победы в первом раунде равна $v_{\text{Alice}}[{\text{Alice}}]=5+1=6$ .
- Если Боб выиграет первый раунд, то равновесным результатом во втором раунде будет то, что Алиса купит товар стоимостью 5 долларов за 0 долларов, поэтому ее чистая прибыль составит 5 долларов. Следовательно, ее общая ценность за то, что она позволила Бобу выиграть, равна $v_{\text{Alice}}[{\text{Bob}}]=0+5=5$ .
Каждый аукцион первой цены с внешними эффектами имеет чисто стратегическое равновесие Нэша. ^[1] В приведенном выше примере равновесие в первом раунде таково, что Боб выигрывает и платит 1 доллар.
Таким образом, методом обратной индукции каждый SAFP имеет SPE с чистой стратегией.

Примечания:

Результат существования также справедлив для SASP. Фактически, любой равновесный результат аукциона первой цены с внешними эффектами является также равновесным результатом аукциона второй цены с теми же внешними эффектами.
Результат существования сохраняется независимо от оценок участников торгов – они могут иметь произвольные функции полезности для неделимых товаров . Напротив, если все аукционы проводятся одновременно , равновесие Нэша в чистой стратегии не всегда существует, даже если участники торгов имеют субаддитивные функции полезности. ^[4]

Социальное обеспечение

Как только мы узнаем, что идеальное равновесие подыгры существует, следующий естественный вопрос заключается в том, насколько оно эффективно : обеспечивает ли оно максимальное социальное благосостояние? Количественно это выражается ценой анархии (PoA) – отношением максимально достижимого социального благосостояния к социальному благосостоянию в наихудшем равновесии. Во вводном примере 1 максимально достижимое социальное благосостояние равно 10 (когда Алиса выигрывает оба предмета), но благосостояние в равновесии равно 9 (Боб выигрывает первый предмет, а Алиса выигрывает второй), поэтому PoA составляет 10/9. В целом, PoA последовательных аукционов зависит от функций полезности участников торгов.

Первые пять результатов применимы к агентам с полной информацией (все агенты знают оценки всех других агентов):

Случай 1: Идентичные предметы . ^[5]^[6] Есть несколько одинаковых предметов. Есть два претендента. По крайней мере один из них имеет вогнутую функцию оценки ( убывающую доходность ). PoA SASP не превышает $1/(1-e)\approx 1.58$ . Численные результаты показывают, что при наличии большого количества участников торгов с вогнутыми функциями оценки потери эффективности уменьшаются по мере увеличения числа пользователей.

Случай 2: Дополнительные участники торгов . ^[1]^: 885 Товары различны, и все участники торгов рассматривают все позиции как независимые товары , поэтому их оценки являются аддитивными функциями множества . PoA SASP не ограничен – благосостояние в SPEPS может быть сколь угодно небольшим.

Случай 3: Участники торгов с единичным спросом . ^[1] Все участники торгов рассматривают все товары как чистые товары-заменители , поэтому их оценки представляют собой спрос на единицу товара . PoA SAFP составляет не более 2 – благосостояние в SPEPS составляет не менее половины максимального (если разрешены смешанные стратегии, PoA составляет не более 4). Напротив, PoA в SASP снова неограничен.

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

Случай 4: субмодульные участники торгов . ^[1] Оценки участников торгов представляют собой произвольные субмодулярные функции множества (обратите внимание, что аддитивный и единичный спрос являются частными случаями субмодулярных функций). В этом случае PoA как SAFP, так и SASP не ограничено, даже если есть только четыре участника торгов. Интуиция подсказывает, что участник торгов с высокой стоимостью может предпочесть позволить выиграть участнику с низкой стоимостью, чтобы уменьшить конкуренцию, с которой он может столкнуться в будущих раундах.

Случай 5: добавка+UD . ^[7] Некоторые участники торгов имеют аддитивную оценку, в то время как другие имеют оценку единичного спроса. PoA SAFP может быть как минимум $\min(n,m)$ , где m — количество позиций, а n — количество участников торгов. Более того, неэффективное равновесие сохраняется даже при многократном устранении слабо доминируемых стратегий. Это подразумевает линейную неэффективность для многих природных условий, в том числе:

Участники торгов с оценкой валового заменителя ,
обоснованные оценки,
бюджетно-аддитивные оценки,
аддитивные оценки с жесткими бюджетными ограничениями на выплаты.

Случай 6: участники торгов с единичным спросом и неполной информацией . ^[8] Агенты не знают оценок других агентов, а знают только распределение вероятностей, из которого извлекаются их оценки. В этом случае последовательный аукцион представляет собой байесовскую игру , и ее PoA может быть выше. Когда все участники торгов имеют оценки спроса на единицу продукции , PoA байесовского равновесия Нэша в SAFP не превышает 3.

Максимизация дохода

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

1. Что лучше использовать: последовательный аукцион или одновременный аукцион? Последовательные аукционы с объявлением ставок между продажами кажутся предпочтительными, поскольку ставки могут передавать информацию о стоимости объектов, которые будут проданы позже. В литературе по аукционам показано, что этот информационный эффект увеличивает ожидаемый доход продавца, поскольку уменьшает проклятие победителя . Однако существует и эффект обмана, который развивается при последовательных продажах. Если участник торгов знает, что его текущая ставка раскроет информацию о последующих объектах, у него есть стимул снизить ставку. ^[9]
2. Если используется последовательный аукцион, в каком порядке следует продавать предметы, чтобы максимизировать доход продавца?

Предположим, есть два товара и есть группа участников торгов, на которых распространяются бюджетные ограничения. Объекты имеют общую ценность для всех участников торгов, но не обязательно должны быть идентичными и могут быть либо дополняющими товарами , либо товарами-заменителями . В игре с полной информацией : ^[2]

1. Последовательный аукцион приносит больший доход, чем одновременный аукцион по возрастанию, если: (а) разница между ценами предметов велика или (б) существует значительная взаимодополняемость.
Гибридная одновременно-последовательная форма приносит более высокий доход, чем последовательный аукцион.
2. Если объекты продаются посредством серии открытых аукционов по возрастанию, то всегда оптимально сначала продать более ценный объект (при условии, что стоимость объектов общеизвестна).

Более того, бюджетные ограничения могут возникать эндогенно. Т.е. компания-участник торгов может сказать своему представителю: «Вы можете потратить не более X на этом аукционе», хотя у самой компании есть гораздо больше денег, которые можно потратить. Заблаговременное ограничение бюджета дает участникам торгов некоторые стратегические преимущества.

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

Сборные механизмы

Последовательные аукционы и одновременные аукционы являются частным случаем более общей ситуации, в которой одни и те же участники торгов участвуют в нескольких разных механизмах. Сыргканис и Тардос ^[10] предложить общую основу для эффективного проектирования механизмов с гарантированными хорошими свойствами, даже когда игроки участвуют в нескольких механизмах одновременно или последовательно. Класс плавных механизмов – механизмы, генерирующие приблизительно рыночные клиринговые цены – привести к получению высококачественного результата как в равновесии, так и в результатах обучения в условиях полной информации, а также в байесовском равновесии с неопределенностью относительно участников. Плавные механизмы хорошо комбинируются: локальная гладкость каждого механизма подразумевает глобальную эффективность. Для механизмов, где хорошие результаты требуют, чтобы участники торгов не предлагали цену выше своей стоимости, можно использовать механизмы со слабой плавностью , такие как аукцион Викри. Они приблизительно эффективны при условии отсутствия завышения ставок, а свойство слабой гладкости также поддерживается композицией. Некоторые результаты справедливы и тогда, когда участники имеют бюджетные ограничения.

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Леме, Ренато Паес; Сыргканис, Василис; Тардос, Ева (2012). «Последовательные аукционы и внешние эффекты». Материалы двадцать третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . п. 869. arXiv : 1108.2452 . дои : 10.1137/1.9781611973099.70 . ISBN 978-1-61197-210-8 .
^ Jump up to: ^а ^б Бенуа, Ж.-П.; Кришна, В. (2001). «Аукционы с несколькими объектами с участниками с ограниченным бюджетом» . Обзор экономических исследований . 68 : 155–179. дои : 10.1111/1467-937X.00164 .
^ Фактически, Алиса может заплатить чуть больше 4 долларов (например, если ставки указаны в целых центах, Алиса может заплатить 4,01 доллара). Для простоты мы игнорируем эту бесконечно малую разницу.
^ хасидим, Авинатан; Каплан, Хаим; Мансур, Ишай; Нисан, Ноам (2011). «Неценовые равновесия на рынках дискретных товаров». Материалы 12-й конференции ACM по электронной коммерции – EC '11 . п. 295. arXiv : 1103.3950 . дои : 10.1145/1993574.1993619 . ISBN 9781450302616 .
^ Бэ, Джунджик; Бейгман, Эяль; Берри, Рэндалл ; Хониг, Майкл; Вохра, Ракеш (2008). «Последовательные аукционы пропускной способности и мощности для распределенного совместного использования спектра». Журнал IEEE по избранным областям коммуникаций . 26 (7): 1193. doi : 10.1109/JSAC.2008.080916 . S2CID 28436853 .
^ Бэ, Джунджик; Бейгман, Эяль; Берри, Рэндалл ; Хониг, Майкл Л.; Вохра, Ракеш (2009). «Об эффективности последовательных аукционов по совместному использованию спектра». Международная конференция 2009 г. по теории игр для сетей . п. 199. CiteSeerX 10.1.1.148.7218 . дои : 10.1109/gamenets.2009.5137402 . ISBN 978-1-4244-4176-1 .
^ Фельдман, Михал ; Люсье, Брендан; Сыргканис, Василис (2013). «Пределы эффективности последовательных аукционов». Экономика Интернета и Интернета . Конспекты лекций по информатике. Том. 8289. с. 160. arXiv : 1309.2529 . дои : 10.1007/978-3-642-45046-4_14 . ISBN 978-3-642-45045-7 .
^ Сыргканис, Василис; Тардос, Ева (2012). «Байесовские последовательные аукционы». Материалы 13-й конференции ACM по электронной коммерции – EC '12 . п. 929. arXiv : 1206.4771 . дои : 10.1145/2229012.2229082 . ISBN 9781450314152 .
^ Хауш, Дональд Б. (1986). «Многообъектные аукционы: последовательные и одновременные продажи». Наука управления . 32 (12): 1599–1610. дои : 10.1287/mnsc.32.12.1599 .
^ Сыргканис, Василис; Тардос, Ева (2013). «Компонируемые и эффективные механизмы». Материалы 45-го ежегодного симпозиума ACM по теории вычислений – STOC '13 . п. 211. arXiv : 1211.1325 . дои : 10.1145/2488608.2488635 . ISBN 9781450320290 .

[lst12-1] Jump up to: ^а ^б ^с ^д ^и ^ж Леме, Ренато Паес; Сыргканис, Василис; Тардос, Ева (2012). «Последовательные аукционы и внешние эффекты». Материалы двадцать третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . п. 869. arXiv : 1108.2452 . дои : 10.1137/1.9781611973099.70 . ISBN 978-1-61197-210-8 .

[bk01-2] Jump up to: ^а ^б Бенуа, Ж.-П.; Кришна, В. (2001). «Аукционы с несколькими объектами с участниками с ограниченным бюджетом» . Обзор экономических исследований . 68 : 155–179. дои : 10.1111/1467-937X.00164 .

[3] Фактически, Алиса может заплатить чуть больше 4 долларов (например, если ставки указаны в целых центах, Алиса может заплатить 4,01 доллара). Для простоты мы игнорируем эту бесконечно малую разницу.

[hkmn11-4] хасидим, Авинатан; Каплан, Хаим; Мансур, Ишай; Нисан, Ноам (2011). «Неценовые равновесия на рынках дискретных товаров». Материалы 12-й конференции ACM по электронной коммерции – EC '11 . п. 295. arXiv : 1103.3950 . дои : 10.1145/1993574.1993619 . ISBN 9781450302616 .

[bbbhv08-5] Бэ, Джунджик; Бейгман, Эяль; Берри, Рэндалл ; Хониг, Майкл; Вохра, Ракеш (2008). «Последовательные аукционы пропускной способности и мощности для распределенного совместного использования спектра». Журнал IEEE по избранным областям коммуникаций . 26 (7): 1193. doi : 10.1109/JSAC.2008.080916 . S2CID 28436853 .

[bbbhv09-6] Бэ, Джунджик; Бейгман, Эяль; Берри, Рэндалл ; Хониг, Майкл Л.; Вохра, Ракеш (2009). «Об эффективности последовательных аукционов по совместному использованию спектра». Международная конференция 2009 г. по теории игр для сетей . п. 199. CiteSeerX 10.1.1.148.7218 . дои : 10.1109/gamenets.2009.5137402 . ISBN 978-1-4244-4176-1 .

[fls13-7] Фельдман, Михал ; Люсье, Брендан; Сыргканис, Василис (2013). «Пределы эффективности последовательных аукционов». Экономика Интернета и Интернета . Конспекты лекций по информатике. Том. 8289. с. 160. arXiv : 1309.2529 . дои : 10.1007/978-3-642-45046-4_14 . ISBN 978-3-642-45045-7 .

[st12-8] Сыргканис, Василис; Тардос, Ева (2012). «Байесовские последовательные аукционы». Материалы 13-й конференции ACM по электронной коммерции – EC '12 . п. 929. arXiv : 1206.4771 . дои : 10.1145/2229012.2229082 . ISBN 9781450314152 .

[h86-9] Хауш, Дональд Б. (1986). «Многообъектные аукционы: последовательные и одновременные продажи». Наука управления . 32 (12): 1599–1610. дои : 10.1287/mnsc.32.12.1599 .

[st13-10] Сыргканис, Василис; Тардос, Ева (2013). «Компонируемые и эффективные механизмы». Материалы 45-го ежегодного симпозиума ACM по теории вычислений – STOC '13 . п. 211. arXiv : 1211.1325 . дои : 10.1145/2488608.2488635 . ISBN 9781450320290 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]