Двойной аукцион - Double auction

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

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

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

Экономический анализ

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

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

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

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

• Расположите покупателей в порядке убывания их ставок: b1≥Би 2≥...≥б_п.
• Заказывайте продавцов в порядке возрастания их ставок: s1≤s2≤...≤s_п.
• Позволять k - наибольший индекс такой, что б_k≥s_k («индекс безубыточности»).

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

	sк + 1 > бk	sк + 1 ≤ бk
бк + 1 < sk	[sk,бk]	[sk,sк + 1]
бк + 1 ≥ sk	[бк + 1,бk]	[бк + 1,sк + 1]

Теоретико-игровой анализ

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

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

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

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

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

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

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

• 0 если s>б;
• п-с если s≤б (куда S истинная стоимость продавца).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Механизм VCG

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

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

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

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

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

В обычном режиме двойного аукциона механизм упорядочивает покупателей и продавцов в Естественный порядок и находит индекс безубыточности k. Тогда первый k продавцы отдают товар первым k покупатели. Каждый покупатель платит самую низкую максимальную равновесную цену (s_k,б_{к + 1}), и каждый продавец получает максимальную равновесную цену min (б_k,s_{к + 1}), как в следующей таблице:

	sк + 1 > бk	sк + 1 ≤ бk
бк + 1 < sk	Каждый покупатель платит sk и каждый продавец получает бk	Каждый покупатель платит sk и каждый продавец получает sк + 1
бк + 1 ≥ sk	Каждый покупатель платит бк + 1 и каждый продавец получает бk	Каждый покупатель платит бк + 1 и каждый продавец получает sк + 1

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

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

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

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

• Заказывайте покупателей и продавцов в Естественный порядок и найти индекс безубыточности k.
• Первый k-1 продавец отдает товар и получает s_k от аукциониста;
• Первый k-1 покупатель получает товар и оплачивает б_k аукционисту.

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

• ИК, как и раньше.
• ТФ: первый k-1 у покупателей и продавцов нет стимула изменять свои декларации, поскольку это не повлияет на их цену; в kУ покупателя и продавца нет стимула меняться, поскольку они все равно не торгуют, и если они все же участвуют в торговле (например, б_k увеличивает свое заявление выше б_k-1) их прибыль от торговли будет отрицательной.
• Не BB, потому что у аукциониста остается излишек (k-1)(б_k-s_k). (однако считается слабо сбалансированный бюджет, поскольку аукционист, по крайней мере, не должен субсидировать торговлю, а остается с излишком).
• Не EE, потому что б_k и s_k не торгуйте, хотя покупатель k ценит товар больше, чем продавец k.

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

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

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

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

Механизм McAfee

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

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

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

Вероятностные механизмы редукции

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

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

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

Сравнение

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

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

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

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

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

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

Смотрите также

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

Примечания

1. Фридман, Дэниел (1992). Институт двойного аукциона: обзор (PDF).
2. Тагев, Рустам (22 мая 2009 г.). «На пути к бартерному двойному аукциону как модели двустороннего социального сотрудничества». arXiv:0905.3709 [cs.GT ].
3. Ноам Нисам (2007). «Введение в разработку механизмов для компьютерных ученых». В нисане - Ноам; Roughgarden, Тим; Тардос, Ева; Вазирани, Виджай (ред.). Алгоритмическая теория игр. С. 230–231. Дои:10.1017 / CBO9780511800481.011. ISBN  978-0521872829. S2CID  154357584.
4. Макафи, Р. П. (1992). «Доминирующая стратегия двойного аукциона». Журнал экономической теории. 56 (2): 434–450. Дои:10.1016 / 0022-0531 (92) 90091-у.
5. Бабайофф, М .; Nisan, N .; Павлов, Э. (2004). «Механизмы пространственно-распределенного рынка». Материалы 5-й конференции ACM по электронной коммерции - EC '04. п. 9. Дои:10.1145/988772.988776. ISBN  1-58113-771-0.
6. М. Бабайофф; Н. Нисан (2004). «Параллельные аукционы в цепочке поставок». Журнал исследований искусственного интеллекта. 21: 595–629. arXiv:1107.0028. Дои:10.1613 / jair.1316.
7. Бабайофф, М .; Уолш, В. Э. (2005). «Совместимые со стимулами, сбалансированные по бюджету, но высокоэффективные аукционы для формирования цепочки поставок». Системы поддержки принятия решений. 39: 123–149. CiteSeerX  10.1.1.4.4123. Дои:10.1016 / j.dss.2004.08.008.
8. Дюттинг, Пауль; Roughgarden, Тим; Талгам-Коэн, Инбал (2014). Модульность и жадность в двойных аукционах (PDF). Труды 15-й конференции по экономике и вычислениям (EC'14). С. 241–258. Дои:10.1145/2600057.2602854. ISBN  9781450325653.

Рекомендации

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