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

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

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

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

• 1 Экономический анализ
  • 1.1 Естественное упорядочение
• 2 Теоретико-игровой анализ
• 3 Дизайн механизма
  • 3.1 Средний механизм
  • 3.2 Механизм VCG
  • 3.3 Торговля механизм сокращения
  • 3.4 Механизм McAfee
  • 3.5 Вероятностные механизмы сокращения
  • 3.6 Сравнение
• 4 Двойные аукционы в цепочке поставок
• 5 Модульный подход
• 6 См. также
• 7 Примечания
• 8 Ссылки

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

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

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

Естественный порядок

• Заказ покупателей в порядке убывания их ставки: b1≥b2≥... ≥b n.
• Заказ продавцов в порядке возрастания их ставки: s1≤ s2≤... ≤s n.
• Пусть k будет наибольшим индексом, таким что b k≥sk(«индекс безубыточности»).

Каждая цена в диапазоне [max (s k,bk + 1), min (b k,sk + 1)] является равновесной ценой, поскольку и спрос, и предложение равны k. Это легче увидеть, если рассмотреть диапазон равновесных цен в каждом из 4 возможных случаев (обратите внимание, что по определению k, b k + 1 < sk + 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\; =\; p\; \in \; [B,\; S].\; \{\backslash \; displaystyle\; b\; =\; s\; =\; p\; \backslash \; in\; [B,\; S].\}$Это означает, что, если B>S, не будет равновесия, в котором оба игрока декларируют свои истинные ценности: либо покупатель будет иметь возможность получить прибыль, объявив более низкую стоимость, или продавец сможет получить прибыль, объявив более высокую стоимость.

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

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

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

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

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

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

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

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

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

Механизм среднего

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

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

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

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

Механизм VCG

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Механизм McAfee

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

• Закажите покупателям и продавцы в естественном порядке и найдите индекс безубыточности 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 / мин (количество покупателей, количество продавцов).

Вероятностные механизмы сокращения

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

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

В варианте этого механизма, после подачи заявок, k-1 дешевых продавцов торгуют с k-1 дорогими покупателями; каждый из них получает / платит ожидаемый платеж исходного механизма, то есть каждый покупатель платит $pbk\; +\; (1\; -\; p)\; max\; (bk\; +\; 1,\; sk)\; \{\backslash \; displaystyle\; pb\_\; \{k\}\; +\; (1-p)\; \backslash \; max\; \{(b\_\; \{k\; +\; 1\},\; s\_\; \{k\})\}\}$и каждый продавец получает $psk\; +\; (1\; -\; p)\; min\; (sk\; +\; 1,\; bk)\; \{\backslash \; displaystyle\; ps\_\; \{\; k\}\; +\; (1-p)\; \backslash \; min\; \{(s\_\; \{k\; +\; 1\},\; b\_\; \{k\})\}\}$. Затем с вероятностью p покупатель k платит $max\; (bk\; +\; 1,\; sk)\; \{\backslash \; displaystyle\; \backslash \; max\; \{(b\_\; \{k\; +\; 1\},\; s\_\; \{k\})\}\}$и покупает товар от продавца k, получившего $min\; (sk\; +\; 1,\; bk)\; \{\backslash \; displaystyle\; \backslash \; min\; \{(s\_\; \{k\; +\; 1\},\; b\_\; \{k\})\}\}$. Как и первый вариант, этот вариант является IR и имеет такую ​​же ожидаемую эффективность и прибыль. Его преимущество в том, что он «скрывает» свой рандомизированный характер почти от всех трейдеров. Обратной стороной является то, что теперь этот механизм является правдивым только заранее; То есть трейдер, нейтральный к риску, не может получить выгоду, неверно сообщая свою стоимость, но после того, как он узнает результаты лота, он может сожалеть о том, что не сообщил иначе.

Сравнение

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

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

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

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

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