A последовательный аукцион - это аукцион, на котором несколько товаров продаются один за другим одной и той же группе потенциальных покупателей. На последовательном аукционе первой цены (SAFP) каждый отдельный предмет продается с использованием аукциона первой цены, тогда как на последовательном аукционе второй цены (SASP) каждый отдельный предмет продается с использованием Аукцион второй цены.
Последовательный аукцион отличается от комбинаторного аукциона, на котором одновременно выставляется много предметов, и агенты могут делать ставки на пакеты предметов. Последовательный аукцион намного проще в реализации и более распространен на практике. Однако участники каждого аукциона знают, что будут проводиться будущие аукционы, и это может повлиять на их стратегические соображения. Вот несколько примеров.
Пример 1 . Есть два предмета для продажи и два потенциальных покупателя: Алиса и Боб, со следующими оценками:
В SASP каждый предмет выставляется на аукцион второй цены. Обычно такой аукцион правдивый механизм, поэтому, если каждый предмет продается отдельно, Алиса выигрывает оба предмета и платит 4 за каждый предмет, ее общий платеж составляет 4 + 4 = 8, а ее чистая полезность составляет 5 + 5 - 8 = 2. Но, если Алиса знает оценки Боба, у нее есть лучшая стратегия: она может позволить Бобу выиграть первый предмет (например, поставив 0). Тогда Боб вообще не будет участвовать во втором аукционе, поэтому Алиса выиграет второй предмет и заплатит 0, и ее чистая полезность будет 5 - 0 = 5.
Аналогичный результат происходит в SAFP. Если каждый товар продается отдельно, существует равновесие по Нэшу, в котором Алиса делает небольшую ставку. выше 4 и выигрывает, а ее чистая полезность s немного ниже 2. Но, если Алиса знает оценки Боба, она может отклониться от стратегии, которая позволяет Бобу выиграть в первом раунде, чтобы во втором раунде она могла выиграть по цене немного выше 0.
Пример 2 . На аукционе выставляется несколько одинаковых объектов, и у агентов есть бюджетные ограничения. Для участника торгов может быть выгодно активно предлагать цену на один объект с целью повышения цены, уплачиваемой его соперником, и истощения его бюджета, чтобы затем второй объект мог быть получен по более низкой цене. Фактически, участник торгов может пожелать «повысить издержки конкурента» на одном рынке, чтобы получить преимущество на другом. Такие соображения, по-видимому, сыграли значительную роль в аукционах по продаже лицензий на спектр, проводимых Федеральной комиссией по связи. Оценка бюджетных ограничений конкурирующих участников торгов была основным компонентом предварительной подготовки тендерной группы GTE.
Последовательный аукцион - это особый случай последовательной игры. Естественный вопрос, который следует задать для такой игры, - это когда существует идеальное равновесие в чистых стратегиях (SPEPS). Когда игроки имеют полную информацию (т.е.они знают последовательность аукционов заранее) и в каждом раунде продается один предмет, SAFP всегда имеет SPEPS, независимо от оценок игроков. Доказательство - обратная индукция :
Примечания:
Как только мы узнаем, что существует подигра совершенное равновесие, следующий естественный вопрос - насколько оно эффективно - обеспечивает ли оно максимальное социальное благосостояние? Это количественно выражается ценой анархии (PoA) - отношением максимально достижимого общественного благосостояния к общественному благосостоянию в наихудшем равновесии. Во вводном примере 1 максимально достижимое социальное благосостояние равно 10 (когда Алиса выигрывает оба пункта), но благосостояние в равновесии равно 9 (Боб выигрывает первый пункт, а Алиса выигрывает второй), поэтому PoA составляет 10/9. В общем, PoA последовательных аукционов зависит от функций полезности участников торгов.
Первые пять результатов относятся к агентам с полной информацией (все агенты знают оценки всех других агентов):
Случай 1: Идентичные элементы . Есть несколько одинаковых предметов. Есть два участника торгов. По крайней мере, один из них имеет вогнутую функцию оценки (убывающая отдача ). PoA для SASP не превышает . Численные результаты показывают, что, когда есть много участников торгов с вогнутыми функциями оценки, потеря эффективности уменьшается по мере увеличения числа пользователей.
Случай 2: Участники торгов . Позиции разные, и все участники торгов рассматривают все позиции как независимые товары, поэтому их оценки являются дополнительными функциями набора. PoA SASP неограничен - благосостояние в SPEPS может быть сколь угодно низким.
Случай 3: участники торгов на единицу спроса . Все участники торгов рассматривают все позиции как чистые товары-заменители, поэтому их оценка составляет спрос на единицу. PoA SAFP составляет не более 2 - благосостояние в SPEPS составляет не менее половины от максимума (если разрешены смешанные стратегии, PoA не превышает 4). Напротив, PoA в SASP снова неограничен.
Эти результаты удивительны, и они подчеркивают важность проектного решения об использовании аукциона первой цены (а не аукциона второй цены) в каждом раунде.
Случай 4: субмодульные участники торгов . Оценки участников торгов являются произвольными функциями субмодульного набора (обратите внимание, что аддитивный и единичный спрос являются частными случаями субмодульных функций). В этом случае PoA как SAFP, так и SASP неограничен, даже если участников торгов всего четыре. Интуиция подсказывает, что участник с высокой стоимостью может предпочесть позволить победителю конкурса с низкой стоимостью, чтобы уменьшить конкуренцию, с которой он может столкнуться в будущих раундах.
Случай 5: добавка + UD . Некоторые участники торгов используют аддитивные оценки, а другие - оценки спроса на единицу продукции. PoA SAFP может быть не менее , где m - количество элементов, а n - количество участников торгов. Более того, неэффективные равновесия сохраняются даже при повторном исключении слабо доминируемых стратегий. Это подразумевает линейную неэффективность для многих естественных условий, в том числе:
Случай 6: заявители на единицу спроса с неполной информацией . Агенты не знают оценок других агентов, а знают только распределение вероятностей, из которого они получают свои оценки. В таком случае последовательный аукцион является байесовской игрой, и его PoA может быть выше. Когда все участники торгов имеют оценки удельного спроса, PoA для байесовского равновесия по Нэшу в SAFP не превышает 3.
Важный практический вопрос для продавцов, продающих несколько предметов, - как спроектировать аукцион, который максимизирует их доход. Есть несколько вопросов:
Предположим, есть два предмета и есть группа участников торгов, на которые распространяются бюджетные ограничения. Объекты имеют общие значения для всех участников торгов, но не обязательно должны быть идентичными и могут быть либо дополнительными товарами, либо замещающими товарами. В игре с полная информация :
Более того, бюджетные ограничения могут возникать эндогенно. То есть компания-участник торгов может сказать своему представителю: «Вы можете потратить не более X на этом аукционе», хотя сама компания может потратить гораздо больше денег. Заблаговременное ограничение бюджета дает участникам торгов некоторые стратегические преимущества.
Когда продается несколько объектов, бюджетные ограничения могут иметь некоторые другие непредвиденные последствия. Например, резервная цена может повысить доход продавца, даже если она установлена на таком низком уровне, что никогда не будет иметь обязательного равновесия.
Последовательные аукционы и одновременные аукционы являются частным случаем более общей настройки, в которой одни и те же участники торгов участвуют в нескольких различных механизмах. Сиргканис и Тардос предлагают общую основу для разработки эффективных механизмов с гарантированно хорошими свойствами, даже когда игроки участвуют в нескольких механизмах одновременно или последовательно. Класс плавных механизмов - механизмов, которые генерируют приблизительно клиринговые цены рынка - приводит к высококачественному результату как в равновесии, так и в результатах обучения в условиях полной информации, а также в байесовском равновесии с неопределенностью относительно участников. Сглаженные механизмы складываются хорошо: слаженность каждого механизма локально подразумевает глобальную эффективность. Для механизмов, в которых для хорошей производительности необходимо, чтобы участники торгов не предлагали цену выше их стоимости, могут использоваться слабо плавные механизмы, такие как аукцион Викри. Они приблизительно эффективны в предположении отсутствия завышенной цены, а свойство слабой гладкости также поддерживается композицией. Некоторые результаты действительны также, когда участники имеют бюджетные ограничения.