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

А последовательный аукцион является аукцион в котором несколько товаров продаются одна за другой одной и той же группе потенциальных покупателей. В последовательный аукцион первой цены (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}

• В последнем раунде у нас есть простой аукцион первой цены. Он имеет равновесие по Нэшу, основанное на чистой стратегии, в котором агент с наибольшей ценностью выигрывает, предлагая цену чуть выше второго по величине значения.
• В каждом предыдущем раунде ситуация является частным случаем аукцион первой цены с внешние эффекты. На таком аукционе каждый агент может получить ценность не только тогда, когда он выигрывает, но и тогда, когда выигрывают другие агенты. В целом оценка агента ${\displaystyle i}$ представлен вектором ${\displaystyle v_{i}[1],\dots ,v_{i}[n]}$, куда ${\displaystyle v_{i}[j]}$ стоимость агента ${\displaystyle i}$ когда агент ${\displaystyle j}$ побеждает. В последовательных аукционах внешние эффекты определяются результатами равновесия в будущих раундах. Во вводном примере есть два возможных результата:
  • Если Алиса выигрывает в первом раунде, то равновесный исход во втором раунде таков, что Алиса покупает предмет стоимостью 5 долларов за 4 доллара,^[3] Таким образом, ее чистая прибыль составляет 1 доллар. Следовательно, ее общая ценность за победу в первом раунде составляет ${\displaystyle v_{\text{Alice}}[{\text{Alice}}]=5+1=6}$.
  • Если Боб выигрывает в первом раунде, то равновесный результат во втором раунде таков, что Алиса покупает предмет стоимостью 5 долларов за 0 долларов, поэтому ее чистая прибыль составляет 5 долларов. Следовательно, ее общая ценность за то, что она позволила Бобу выиграть, составляет ${\displaystyle 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 не более ${\displaystyle 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 может быть не менее ${\displaystyle \min(n,m)}$, куда м это количество предметов и п количество участников торгов. Более того, неэффективные равновесия сохраняются даже при многократном исключении слабо доминируемых стратегий. Это подразумевает линейную неэффективность для многих естественных условий, включая:

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

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