Двойной аукцион

Двойной аукцион является процесс покупки и продажи товаров с несколькими продавцами и несколькими покупателями. ^[1] Потенциальные покупатели подают свои заявки, а потенциальные продавцы представляют свои цены продажи в рыночный институт, а затем рыночный институт выбирает некоторую цену p, которая очищает рынок: все продавцы, которые попросили меньше, чем p, продают, и все покупатели, предлагающие больше, чем p купить по этой цене p . Также включены покупатели и продавцы, предлагающие или запрашивающие ровно p . Типичный пример двойного аукциона - биржа .

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

Простой пример двойного аукциона является двусторонней торговли сценарий, в котором есть один продавец , который ценит свой продукт как S (например , затраты на производство продукта), и один покупатель , который ценит этот продукт как B .

Экономический анализ [ править ]

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

В простом сценарии двусторонней торговли, если B ≥ S, то любая цена в диапазоне [ S , B ] является равновесной ценой, поскольку и предложение, и спрос равны 1. Любая цена ниже S не является равновесной ценой, поскольку существует избыточный спрос, и любая цена выше B не является равновесной ценой, поскольку существует избыточное предложение. Когда B < S , любая цена в диапазоне ( B , S ) является равновесной ценой, поскольку и предложение, и спрос равны 0 (цена слишком высока для покупателя и слишком низка для продавца).

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

Естественный порядок [ править ]

• Расположите покупателей в порядке убывания их заявки: b ₁ ≥ b ₂ ≥ ... ≥ b _n .
• Расположите продавцов в порядке возрастания их ставок: s ₁ ≤ s ₂ ≤ ... ≤ s _n .
• Пусть k - наибольший индекс такой, что b _k ≥ s _k («индекс безубыточности»).

Каждая цена в диапазоне [max ( s _k , b _{k + 1} ), min ( b _k , s _{k + 1} )] является равновесной ценой, поскольку и спрос, и предложение равны k . В этом легче убедиться, рассмотрев диапазон равновесных цен в каждом из 4 возможных случаев (обратите внимание, что по определению k , b _{k + 1} < s _{k + 1} ):

Теоретико-игровой анализ [ править ]

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

Рассмотрим сценарий двусторонней торговли, в котором покупатель подает заявку на сумму b, а продавец - на s .

Предположим, аукционист устанавливает цену следующим образом:

• Если s > b, то торговля не происходит (продавец хочет больше, чем платит покупатель);
• Если s ≤ b, то p = ( b + s ) / 2.

Полезность покупателя:

• 0, если s > b ;
• Bp, если s ≤ b (где B - истинная стоимость покупателя).

Полезность продавца:

• 0, если s > b ;
• pS, если s ≤ b (где S - истинная стоимость продавца).

В полной информации случае , когда оценки являются общими знаниями для обеих сторон, можно показать , что континуум чистой стратегии эффективных равновесий Нэша существует с Это означает , что, если B> S , не будет не равновесие , в котором оба игрока объявить их истинные значения: либо покупатель сможет выиграть, объявив более низкую стоимость, либо продавец сможет выиграть, объявив более высокую стоимость.${\ displaystyle b = s = p \ in [B, S].}$

В случае неполной информации (асимметричной информации) покупатель и продавец знают только свои собственные оценки. Предположим, что эти оценки равномерно распределены на одном интервале. Тогда можно показать, что такая игра имеет байесовское равновесие по Нэшу с линейными стратегиями. То есть существует равновесие, когда ставки обоих игроков являются линейными функциями их оценок. Это также приносит игрокам более высокую ожидаемую прибыль, чем любое другое байесовское равновесие по Нэшу (см. Теорему Майерсона – Саттертуэйта ).

Дизайн механизма [ править ]

Как аукционисту следует определять торговую цену? Идеальный механизм должен обладать следующими свойствами:

1. Индивидуальная рациональность (ИР): никто не должен проиграть от участия в аукционе. В частности, для каждого торгового покупателя: р ≤ B , и для каждого торгового продавца: р ≥ S .

2. Сбалансированный бюджет (BB) бывает двух видов:

• Сильный сбалансированный бюджет (SBB): все денежные переводы должны осуществляться между покупателями и продавцами; аукционист не должен терять или получать деньги.
• Слабый сбалансированный бюджет (WBB): аукционист не должен терять деньги, но может получить деньги.

3. Правдивость (TF), также называемая совместимостью по стимулам (IC) или устойчивостью к стратегии : также бывает двух видов (когда неквалифицированный TF обычно означает более сильную версию):

• Более сильное понятие - это совместимость с доминирующей стратегией и стимулом (DSIC), что означает, что сообщение истинной ценности должно быть доминирующей стратегией для всех игроков. То есть, игрок не должен иметь возможность выиграть, шпионя за другими игроками и пытаясь найти «оптимальное» объявление, которое отличается от его истинного значения, независимо от того, как играют другие игроки.
• Более слабое понятие - это равновесие-стимулы-совместимость по Нэшу (NEIC), что означает, что существует равновесие по Нэшу, при котором все игроки сообщают о своих истинных оценках. То есть, если все игроки, кроме одного, правдивы, лучше, чтобы оставшийся игрок тоже был правдивым.

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

К сожалению, невозможно выполнить все эти требования одним и тем же механизмом (см. Теорему Майерсона – Саттертуэйта ). Но есть механизмы, которые удовлетворяют некоторых из них.

Средний механизм [ править ]

Механизм, описанный в предыдущем разделе, можно обобщить на n игроков следующим образом.

• Закажите покупателей и продавцов в естественном порядке и найдите индекс безубыточности k .
• Установите цену как среднее значение k- го значения: p = ( b _k + s _k ) / 2.
• Пусть первые k продавцов продают товар первым k покупателям.

Этот механизм:

• IR - потому что согласно порядку, первые k игроков оценивают каждый предмет как минимум как p, а первые k продавцов оценивают каждый предмет как максимум p .
• BB - потому что все денежные переводы происходят между покупателями и продавцами.
• EE - потому что n предметов принадлежат n игрокам, которые их больше всего ценят.
• Не TF - потому что покупатель k имеет стимул сообщать о более низкой стоимости, а продавец k имеет стимул сообщать о более высокой стоимости.

Механизм VCG [ править ]

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

В условиях простой двусторонней торговли это выражается в следующем механизме:

• Если b ≤ s, торговля не производится и товар остается у продавца;
• Если b > s, то товар переходит к покупателю, покупатель платит s, а продавец получает b .

Этот механизм:

• IR, поскольку покупатель платит меньше своей стоимости, а продавец получает больше своей стоимости.
• TF, поскольку цена, уплачиваемая покупателем, определяется продавцом и наоборот. Любая попытка составить неверный отчет сделает полезность неверного отчета либо нулевой, либо отрицательной.
• ЭЭ, потому что товар достается тому, кто его больше всего ценит.
• Не BB, потому что аукционист должен заплатить b - s . Аукционист фактически должен субсидировать торговлю.

При обычном двойном аукционе механизм упорядочивает покупателей и продавцов в естественном порядке и находит индекс безубыточности k . Затем первые k продавцов передают товар первым k покупателям. Каждый покупатель платит самую низкую равновесную цену max ( s _k , b _{k + 1} ), а каждый продавец получает самую высокую равновесную цену min ( b _k , s _{k + 1} ), как показано в следующей таблице:

Подобно сценарию двусторонней торговли, механизмом является IR, TF и ​​EE (оптимизирует социальное благосостояние), но это не BB - аукционист субсидирует торговлю.

Теорема об уникальности цен ^[3] подразумевает, что эта проблема субсидий неизбежна - любой правдивый механизм, оптимизирующий социальное благосостояние, будет иметь одинаковые цены (вплоть до функции, не зависящей от цен спроса / предложения каждого трейдера). Если мы хотим, чтобы механизм был правдивым, и при этом не нужно было субсидировать торговлю, мы должны пойти на компромисс в отношении эффективности и реализовать неоптимальную функцию социального обеспечения.

Механизм сокращения торговли [ править ]

Следующий механизм отказывается от единственной сделки, чтобы сохранить правдивость: ^[4]

• Закажите покупателей и продавцов в естественном порядке и найдите индекс безубыточности k .
• Первые k -1 продавцов отдают товар и получают s _k от аукциониста;
• Первые k -1 покупателей получают товар и платят b _k аукционисту.

Этот механизм:

• ИК, как и раньше.
• TF: у первых k -1 покупателей и продавцов нет стимула изменять свои декларации, поскольку это не повлияет на их цену; к - й покупатель и продавец не имеют стимулов к изменению , так как они не торгуют так или иначе, и если они делают ввести торговлю (например , б _к увеличивает свою декларацию выше Ь _{к -1} ), их прибыль от торговли будет отрицательным.
• Не BB, потому что у аукциониста остается излишек ( k -1) ( b _k - s _k ). (однако он считается слабо сбалансированным по бюджету , поскольку аукционист, по крайней мере, не должен субсидировать торговлю, а скорее остается с профицитом).
• Не EE, потому что b _k и s _k не торгуются, хотя покупатель k ценит товар больше, чем продавец k .

Если бы мы попытались сделать этот механизм эффективным, позволив k- му покупателю и продавцу торговать, это сделало бы его неправдивым, потому что тогда у них будет стимул изменить свои цены.

Хотя социальное обеспечение не является оптимальным, оно почти оптимально, поскольку запрещенная сделка - наименее выгодная сделка. Следовательно, прибыль от торговли, по крайней мере, является оптимальной.${\ displaystyle 1-1 / k}$

Обратите внимание, что в условиях двусторонней торговли k = 1, и мы отказываемся от единственной эффективной сделки, поэтому торговли нет вообще, а прибыль от торговли равна 0. Это соответствует теореме Майерсона-Саттертуэйта .

Механизм сокращения торговли можно обобщить на рынок, который распределен в пространстве , т.е. покупатели и продавцы находятся в нескольких разных местах, и некоторые единицы товара, возможно, придется транспортировать между этими местами. Стоимость транспортировки, таким образом, добавляется к стоимости продукции продавцов. ^[5]

Механизм McAfee [ править ]

Следующий механизм ^[4] представляет собой разновидность механизма сокращения торговли:

• Закажите покупателей и продавцов в естественном порядке и найдите индекс безубыточности k .
• Вычислить: p = ( b _{k +1} + s _{k +1} ) / 2.
• Если b _k ≥ p ≥ s _k , то первые k покупателей и продавцов торгуют товаром по цене p .
• В противном случае первые k -1 продавцов торгуют за s _k, а первые k -1 покупателей торгуют за b _k, как в механизме сокращения торговли.

Подобно механизму сокращения торговли, этот механизм - IR, TF, а не BB (во втором случае) и не EE (во втором случае). Предполагая, что все значения покупателей и продавцов ограничены выше нуля, можно доказать, что потеря эффективности торговли ограничена 1 / мин (количество покупателей, количество продавцов). ^[4]

Механизмы вероятностной редукции [ править ]

При p ∈ [0,1] после подачи заявок используйте механизм сокращения сделок с вероятностью p и механизм VCG с вероятностью 1– p . ^[6] Этот механизм наследует все свойства своих родителей, то есть это IR и TF. Параметр p контролирует компромисс между EE и BB:

• Потеря прибыли от торговли равна 0 (достигается VCG) или 1 / k (достигается за счет сокращения торговли); следовательно, ожидаемая потеря прибыли от торговли не превышает: p / k .
• Положительное сальдо аукциониста либо отрицательное (в случае VCG), либо положительное (в случае сокращения торговли); следовательно, ожидаемое профицитное сальдо равно p * (сокращение торгового баланса) - (1- p ) * (дефицит в VCG). Если значения трейдеров берутся из известного распределения, p можно выбрать так, чтобы ожидаемый профицит был равен 0, т. Е. Механизм - прогнозируемый BB.

В варианте этого механизма ^[6] после подачи заявок k -1 дешевых продавцов торгуют с k -1 дорогими покупателями; каждый из них получает / платит ожидаемый платеж первоначального механизма, т.е. каждый покупатель платит, а каждый продавец получает . Тогда с вероятностью p покупатель k платит и покупает товар у продавца k, который получает${\ displaystyle pb_ {k} + (1-p) \ max {(b_ {k + 1}, s_ {k})}}$${\ displaystyle ps_ {k} + (1-p) \ min {(s_ {k + 1}, b_ {k})}}$${\ displaystyle \ max {(b_ {k + 1}, s_ {k})}}$${\ displaystyle \ min {(s_ {k + 1}, b_ {k})}}$. Как и первый вариант, этот вариант является IR и имеет такую ​​же ожидаемую эффективность и прибыль. Его преимущество в том, что он «скрывает» свой рандомизированный характер почти от всех трейдеров. Обратной стороной является то, что теперь механизм достоверен только заранее; то есть, трейдер, нейтральный к риску, не может получить выгоду, неверно сообщая свою стоимость, но после того, как он узнает результаты лота, он может сожалеть о том, что не сообщил иначе.

Сравнение [ править ]

^[6] (глава 4) обеспечивает как теоретическое сравнение, так и эмпирическое сравнение различных механизмов.

Двойные аукционы в цепочке поставок [ править ]

Базовая модель двойного аукциона предполагает единый рынок. Его можно расширить для управления цепочкой поставок - цепочкой рынков, в которой покупатели на одном рынке становятся продавцами на следующем рынке. Например, фермеры продают фрукты на фруктовом рынке; производители соков покупают фрукты на фруктовом рынке, производят сок и продают их потребителям на рынке соков. ^[6]

Модель может быть расширена для обработки рынков в произвольном ориентированном ациклическом графе . ^[7]

Модульный подход [ править ]

Модульный подход к организации двойных аукционов был недавно предложен Dütting, Roughgarden и Talgam-Cohen. ^[8] Эта структура рассматривает двойные аукционы как составные из алгоритмов ранжирования для каждой стороны рынка и правила состава и может применяться к сложным рынкам. Непосредственным следствием этой структуры является то, что классические механизмы двойного аукциона, такие как механизм сокращения торговли, не только устойчивы к стратегии, но и слабо защищены от групповой стратегии (это означает, что никакая группа покупателей и продавцов не может получить выгоду от совместного неверного отчета о своих предпочтениях).

См. Также [ править ]

• Аукцион цепочки поставок - обобщение двойного аукциона на более чем две категории агентов.
• Теорема Майерсона – Саттертуэйта - нет механизма IR, TF, BB и EE, даже когда есть только один покупатель, один продавец и один товар.

Заметки [ править ]

Ссылки [ править ]