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

редактировать

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

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

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

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

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

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

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

Содержание

  • 1 Равновесие Нэша
  • 2 Социальное благосостояние
  • 3 Максимизация доходов
  • 4 Составные механизмы
  • 5 Ссылки

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

Последовательный аукцион - это особый случай последовательной игры. Естественный вопрос, который следует задать для такой игры, - это когда существует идеальное равновесие в чистых стратегиях (SPEPS). Когда игроки имеют полную информацию (т.е.они знают последовательность аукционов заранее) и в каждом раунде продается один предмет, SAFP всегда имеет SPEPS, независимо от оценок игроков. Доказательство - обратная индукция :

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

Примечания:

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

Социальное благосостояние

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

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

Случай 1: Идентичные элементы . Есть несколько одинаковых предметов. Есть два участника торгов. По крайней мере, один из них имеет вогнутую функцию оценки (убывающая отдача ). PoA для SASP не превышает 1 / (1 - e) ≈ 1,58 {\ displaystyle 1 / (1-e) \ приблизительно 1,58}{\ displaystyle 1 / (1-e) \ приблизительно 1,58 } . Численные результаты показывают, что, когда есть много участников торгов с вогнутыми функциями оценки, потеря эффективности уменьшается по мере увеличения числа пользователей.

Случай 2: Участники торгов . Позиции разные, и все участники торгов рассматривают все позиции как независимые товары, поэтому их оценки являются дополнительными функциями набора. PoA SASP неограничен - благосостояние в SPEPS может быть сколь угодно низким.

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

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

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

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

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

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

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

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

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

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

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

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

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

Составные механизмы

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

Список литературы

Последняя правка сделана 2021-06-07 10:46:03
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте