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

Двойной товаров с аукцион — это процесс покупки и продажи участием нескольких продавцов и нескольких покупателей. ^[1] Потенциальные покупатели подают свои предложения, а потенциальные продавцы представляют свои цены предложения рыночному институту, а затем рыночный институт выбирает некоторую цену 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 ):

	s _k+1 > b _k	s _k+1 ≤ b _k
бк ₊ < ск ₁	[ s _k , б _k ]	[ s _k , s _k+1 ]
бк ₊ ≥ sк ₁	[ бк ₊ , бк _] 1	[ б _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=p\in [B,S].$ Это означает, что, если B>S будет , не равновесия, в котором оба игрока заявляют о своих истинных ценностях: либо покупатель сможет выиграть, объявив более низкую стоимость, либо продавец сможет выиграть, объявив более высокую стоимость. .

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

Конструкция механизма

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

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

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

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

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

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

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

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

Средний механизм

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

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

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

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

Механизм ВКГ

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

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

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

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

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

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

	s _k+1 > b _k	s _k+1 ≤ b _k
бк ₊ < ск ₁	Каждый покупатель платит s _k , а каждый продавец получает b _k.	Каждый покупатель платит s _k , а каждый продавец получает s _k+1.
бк ₊ ≥ sк ₁	Каждый покупатель платит bk ₊₁ , а каждый продавец получает bk _.	Каждый покупатель платит b _k+1 , а каждый продавец получает s _k+1.

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

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

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

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

Расположите покупателей и продавцов в естественном порядке и найдите индекс безубыточности k .
Первые k -1 продавцов отдают предмет и получают s _{k ;} от аукциониста
Первые k -1 покупателей получают лот и платят . _{аукционисту} bk

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

ИР, как и прежде.
IC: у первых k -1 покупателей и продавцов нет стимула менять свою декларацию, поскольку это не повлияет на их цену; у k -го покупателя и продавца нет стимула меняться, поскольку они все равно не торгуют, и если они вступят в торги (например, b _k увеличит свою декларацию выше b _{k -1} ), их прибыль от торговли будет отрицательной.
Не SBB, потому что у аукциониста остается излишек в размере ( k -1)( b _k - s _k ). Но это WBB, поскольку аукционисту, по крайней мере, не нужно субсидировать торговлю.
Не EE, поскольку bk _{продавец} и sk _чем не торгуются, хотя покупатель k ценит товар выше, k .

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

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

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

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

Механизм McAfee

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

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

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

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

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

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

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

механизм SBBA

Сегал-Халеви, хасиды и Ауманн ^[7] представить механизм сокращения торговли, который является SBB, в дополнение к IR и IC и достигает (1-1/k) оптимального GFT.

Сравнение

Бабаёв и Нисан ^[6]^{: Глава 4} обеспечить как теоретическое, так и эмпирическое сравнение различных механизмов.

Модульный подход

Дюттинг, Рафгарден и Талгам-Коэн ^[8] предложил модульный подход к построению двойных аукционов. Их концепция рассматривает двойные аукционы как состоящие из алгоритмов ранжирования для каждой стороны рынка и правила композиции и может применяться к сложным рынкам. Непосредственным следствием этой концепции является то, что классические механизмы двойных аукционов, такие как механизм сокращения торговли, не только устойчивы к стратегии, но и слабо защищены от групповой стратегии (это означает, что ни одна группа покупателей и продавцов не может получить выгоду от совместного неверного сообщения о своих предпочтениях).

За пределами двух категорий

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

Гилор, Гонен и Сегал-Халеви ^[10] изучить многосторонний рынок с набором G категорий агентов. Рынок характеризуется целочисленным вектором r размера | G |, называемый рецептом рынка. каждой сделке на рынке участвует r _g агентов категории g для каждого g из G. В Стандартный рынок двойных аукционов представляет собой особый случай, в котором имеются две категории (покупатели и продавцы), а рецепт r =(1,1). Они представляют алгоритмы SBB, IC, IR и достигают (1-1/ k ) оптимального GFT. Один алгоритм представляет собой механизм прямого выявления, основанный на сокращении торговли, а другой — механизм возрастания цен , который является не только IC, но и, очевидно, IC .

Гилор, Гонен и Сегал-Халеви ^[11] Изучите более общий многосторонний рынок, на котором существует множество различных рецептов, организованных в виде леса , где каждый рецепт представляет собой путь от корня к листу. Они представляют рандомизированные механизмы возрастания цен, которые универсально являются IR, очевидно, IC, SBB и достигают асимптотически оптимального GFT.

См. также

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

Примечания

^ Фридман, Дэниел (1992). Институт рынка двойных аукционов: обзор (PDF) .
^ Тагиев, Рустам (22 мая 2009 г.). «К бартерному двойному аукциону как модель двустороннего социального сотрудничества». arXiv : 0905.3709 [ cs.GT ].
^ Нисан, Ноам (2007). «Введение в проектирование механизмов для компьютерщиков». В Нисане Ноам; Рафгарден, Тим; Тардос, Ева; Вазирани, Виджай (ред.). Алгоритмическая теория игр . стр. 230–231. дои : 10.1017/CBO9780511800481.011 . ISBN 978-0521872829 . S2CID 154357584 .
^ Перейти обратно: ^а ^б ^с Макафи, Р.П. (1992). «Двойной аукцион доминирующей стратегии». Журнал экономической теории . 56 (2): 434–450. дои : 10.1016/0022-0531(92)90091-у .
^ Бабаёв М.; Нисан, Н.; Павлов, Е. (2004). «Механизмы пространственно распределенного рынка». Материалы 5-й конференции ACM по электронной коммерции - EC '04 . п. 9. дои : 10.1145/988772.988776 . ISBN 1-58113-771-0 .
^ Перейти обратно: ^а ^б ^с ^д М. Бабаев; Н. Нисан (2004). «Одновременные аукционы по всей цепочке поставок». Журнал исследований искусственного интеллекта . 21 : 595–629. arXiv : 1107.0028 . дои : 10.1613/jair.1316 . S2CID 58535404 .
^ Сегал-Халеви, Эрель; хасидим, Авинатан; Ауманн, Йонатан (2016). «SBBA: механизм двойного аукциона с сильным бюджетом и сбалансированным бюджетом» . В Гейринге, Мартин; Савани, Рахул (ред.). Алгоритмическая теория игр . Конспекты лекций по информатике. Берлин, Гейдельберг: Springer. стр. 260–272. arXiv : 1607.05139 . дои : 10.1007/978-3-662-53354-3_21 . ISBN 978-3-662-53354-3 .
^ Дюттинг, Пол; Рафгарден, Тим; Талгам-Коэн, Инбал (2014). Модульность и жадность на двойных аукционах (PDF) . Материалы 15-й конференции по экономике и вычислениям (EC'14). стр. 241–258. дои : 10.1145/2600057.2602854 . ISBN 9781450325653 .
^ Бабаёв М.; Уолш, МЫ (2005). «Соответствующие стимулам, сбалансированные по бюджету, но высокоэффективные аукционы для формирования цепочки поставок». Системы поддержки принятия решений . 39 : 123–149. CiteSeerX 10.1.1.4.4123 . дои : 10.1016/j.dss.2004.08.008 .
^ Гилор, Двир; Гонен, Рика; Сегал-Халеви, Эрель (01 ноября 2021 г.). «Аукционы со строгим бюджетным балансом для многосторонних рынков» . Искусственный интеллект . 300 : 103548. arXiv : 1911.08094 . дои : 10.1016/j.artint.2021.103548 . ISSN 0004-3702 .
^ Гилор, Двир; Гонен, Рика; Сегал-Халеви, Эрель (1 декабря 2023 г.). «Механизм восходящих цен для общих многосторонних рынков» . Искусственный интеллект . 325 : 104022. doi : 10.1016/j.artint.2023.104022 . ISSN 0004-3702 .

Ссылки

Фуденберг, Дрю; Тироль, Жан (1991). Теория игр . МТИ Пресс. ISBN 978-0-262-06141-4 .
Гиббонс, Роберт (1992). Теория игр для экономистов-прикладников . Издательство Принстонского университета. ISBN 978-0-691-00395-5 .

[1] Фридман, Дэниел (1992). Институт рынка двойных аукционов: обзор (PDF) .

[2] Тагиев, Рустам (22 мая 2009 г.). «К бартерному двойному аукциону как модель двустороннего социального сотрудничества». arXiv : 0905.3709 [ cs.GT ].

[agt09-3] Нисан, Ноам (2007). «Введение в проектирование механизмов для компьютерщиков». В Нисане Ноам; Рафгарден, Тим; Тардос, Ева; Вазирани, Виджай (ред.). Алгоритмическая теория игр . стр. 230–231. дои : 10.1017/CBO9780511800481.011 . ISBN 978-0521872829 . S2CID 154357584 .

[mcafee92-4] Перейти обратно: ^а ^б ^с Макафи, Р.П. (1992). «Двойной аукцион доминирующей стратегии». Журнал экономической теории . 56 (2): 434–450. дои : 10.1016/0022-0531(92)90091-у .

[5] Бабаёв М.; Нисан, Н.; Павлов, Е. (2004). «Механизмы пространственно распределенного рынка». Материалы 5-й конференции ACM по электронной коммерции - EC '04 . п. 9. дои : 10.1145/988772.988776 . ISBN 1-58113-771-0 .

[bn04-6] Перейти обратно: ^а ^б ^с ^д М. Бабаев; Н. Нисан (2004). «Одновременные аукционы по всей цепочке поставок». Журнал исследований искусственного интеллекта . 21 : 595–629. arXiv : 1107.0028 . дои : 10.1613/jair.1316 . S2CID 58535404 .

[7] Сегал-Халеви, Эрель; хасидим, Авинатан; Ауманн, Йонатан (2016). «SBBA: механизм двойного аукциона с сильным бюджетом и сбалансированным бюджетом» . В Гейринге, Мартин; Савани, Рахул (ред.). Алгоритмическая теория игр . Конспекты лекций по информатике. Берлин, Гейдельберг: Springer. стр. 260–272. arXiv : 1607.05139 . дои : 10.1007/978-3-662-53354-3_21 . ISBN 978-3-662-53354-3 .

[8] Дюттинг, Пол; Рафгарден, Тим; Талгам-Коэн, Инбал (2014). Модульность и жадность на двойных аукционах (PDF) . Материалы 15-й конференции по экономике и вычислениям (EC'14). стр. 241–258. дои : 10.1145/2600057.2602854 . ISBN 9781450325653 .

[bn05-9] Бабаёв М.; Уолш, МЫ (2005). «Соответствующие стимулам, сбалансированные по бюджету, но высокоэффективные аукционы для формирования цепочки поставок». Системы поддержки принятия решений . 39 : 123–149. CiteSeerX 10.1.1.4.4123 . дои : 10.1016/j.dss.2004.08.008 .

[10] Гилор, Двир; Гонен, Рика; Сегал-Халеви, Эрель (01 ноября 2021 г.). «Аукционы со строгим бюджетным балансом для многосторонних рынков» . Искусственный интеллект . 300 : 103548. arXiv : 1911.08094 . дои : 10.1016/j.artint.2021.103548 . ISSN 0004-3702 .

[11] Гилор, Двир; Гонен, Рика; Сегал-Халеви, Эрель (1 декабря 2023 г.). «Механизм восходящих цен для общих многосторонних рынков» . Искусственный интеллект . 325 : 104022. doi : 10.1016/j.artint.2023.104022 . ISSN 0004-3702 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]