Аукционы множественных объектов

Аннотация

В данной работе разбираются и продолжаются основные результаты статьи Пола Милгрома и Ильи Сегала ’Deferred-Acceptance Auctions and Radio Spectrum Reallocation’ [1]. Мы рассматриваем два типа оптимальных механизмов, которые часто применяются в наше время, исследуем их свойства и сравниваем между собой. Для таких актуальных сейчас задач, как "переупаковка" частот, применение данных механизмов занимает очень много времени, так как сама проблема является NP-полной. В связи с этим, требуются эффективные аппроксимации, которые ускорят этот процесс. Будет представлен один из таких алгоритмов, а также возможные модификации механизмов и функций очков в аукционе с запаздывающим принятием.

Введение

В данной работе мы рассматриваем два типа механизмов: deferred−acceptance (DA) и descending clock (DC), – которые широко применяются в наше время для достижения оптимальных результатов. Это означает, что товар достается тому агенту, который извлечет из него максимальную пользу. Механизм является правилом (алгоритмом), задающим распределение товаров среди участников и соответствующие платежи при заявленных типах игроков. Предполагается, что платежи получают только те игроки, которые стали победителями, поэтому эти механизмы также являются аукционами. На первый взгляд данные классы механизмов имеют разные определения и свойства. Однако будет доказана их эквивалентность друг другу при добавлении некоторых естественных условий, например, использование игроками стратегий отсечек или, что правило платежа является пороговым. Данная связь между механизмами позволит моделировать гораздо более сложные ситуации, которые необходимо решать в жизни.

Одним из важных примеров таких задач является проблема Федеральной Комиссии Связи по "переупаковке" частот. Она заключается в следующем. Телевизионные (ТВ) компании готовы продать свои права (лицензии) на вещание, освобождая при этом радиочастоты, которые после определенной "переупаковки" продаются телефонным компаниям для внедрения инновационных типов связи, таких как 3G, LTE и других. Для осуществления проекта необходима третья сторона, которая купит у телекомпаний их рабочие частоты, разобьет на заранее определенные блоки, а затем продаст телефонным компаниям. Посредническую роль выполняет правительство, которое определяет правила аукционов и является стабилизирующим фактором для обеих сторон.

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

Мы сконцентрируемся на первой части этого большого процесса: покупки частот у ТВ компаний. Для решения задачи используется класс deferred − acceptance аукционов, обобщающих идею одноименного мэтчинг механизма, описанного Д. Гейлом и Л. Шепли в 1962 году [3]. Кроме того, алгоритм "отложенного принятия" подробно описан в статье Е. Железовой, С. Измалкова, К. Сонина, И. Хованской [4], а также его практические применения. Основной принцип DA заключается в итеративном удалении игроков с наибольшим количеством очков (наименее привлекательных) в каждом раунде, а оставшиеся в конце агенты объявляются победителями.

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

DA принято использовать для решения задачи с теоретической точки зрения, в то время как правила и стратегии в DC прозрачны для участников. Последний аукцион устроен следующим образом. На каждом этапе процесса всем активным участникам предлагается цена. Если они соглашаются на нее, они остаются активными, и цена запоминается, остальные же покидают аукцион без возможности вернуться в будущем. Процедура повторяется, пока цены в периоде t полностью не совпадут с ценами в t + 1. Таким образом, эквивалентность данных классов механизмов позволит эффективно смоделировать процесс для каждой из сторон (покупателя и продавцов): с помощью DA добиться необходимой цели для покупателя и внедрить эквивалентный DC в помощь продавцам.

Телевизионные компании имеют три возможности: 1) полностью продать права на вещание, 2) перейти на более высокую частоту или 3) остаться на своей нынешней частоте. При этом победителями в механизмах могут стать только игроки, выбравшие один из первых двух вариантов.

Статья устроена следующим образом. Вначале мы введем основные понятия и некоторые их обобщения, как например, "Монотонная функция распределения", "Пороговый аукцион". Во второй главе будут описаны два основных типа механизмов deferred − acceptance и descending clock и рассмотрена модель из статьи Пола Милгрома и Ильи Сегала ’Deferred-Acceptance Auctions and Radio Spectrum Reallocation’[1], позволяющая компаниям победить единственным способом: получить деньги, полностью продав лицензию на вещание. Будет доказана эквивалентность аукционов и некоторые их свойства. После этого мы определим естественным образом двумерную модель (имеющую практическое применение), добавив вторую возможность победить в аукционе, и докажем для нее аналог предыдущей теоремы. В четвертой главе будет представлен один из видов аппроксимации DA механизма и подсчитана его эффективность и применимость в реальных условиях. В пятой главе, мы предложим некоторые добавления в основной механизм и новые методы подсчета функций очков.

Все определения взяты из статьи П. Милгрома и И. Сегал ’Deferred-Acceptance Auctions and Radio Spectrum Reallocation’ [1].

1. Основная модель

2. Deferred-Acceptance и Descending Clock Auctions

3. Обобщение

4. Аппроксимация

5. Модификации механизма

Теперь мы опишем несколько возможных модификаций основных механизмов, чтобы повысить их эффективность.

Рассмотрим следующее дополнение. В начале каждого раунда в DC аукционер говорит фирмам, что их цены опустятся до определенного уровня. Агентам разрешается поставить точки на отрезке с концами в нынешней цене и в цене в конце раунда. Они будут означать, что когда цена опустится ниже поставленной точки, опция игрока поменяется указанным им образом (между вариантами 1, 2, 3). Это не усложнит задачу для фирм, потому что они все равно должны понять для себя, как им действовать в этом раунде, если они еще активны. Для государства же это большое количество новой информации. Оно сможет не только узнавать более непрерывно предпочтения компаний, что в свою очередь сильно ускорит весь процесс, но и понимать, как правильнее понижать цену. Фирмы не смогут особо манипулировать с помощью этого, потому что те компании, для которых цены опускаются, аукционер готов отпустить, и результат этого отклонения для одного игрока зависит от других участников. Значит риск того, что компанию отпустят из аукциона (а не зафиксируют ее цену), если она завысит свою стоимость и потребует покинуть аукцион, очень велик. Следовательно его нужно рационально оправдывать соизмеримой прибылью, что влечет к значительному завышению "полезностей". Но государство может посчитать ожидаемую стоимость компаний, и при большом повышении, неправдивость будет ясна. Опасность манипулирования гораздо меньше, чем полезность от получаемой таким образом информации.

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

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

Единственное, что может помешать в данном случае акционеру-коалиции с трансферабельной полезностью. Цены, предложенные игрокам, всегда зависят от уже выбывших из аукциона агентов. Поэтому если один из членов коалиции (в этом примере первая фирма) выйдет сильно раньше, чем предполагается, то это может очень завысить платеж остальным ее членам. Пусть начальные цены 100, и полезности компаний равны 42 и 43. Если первая компания выйдет при цене 99, и вторая захочет покинуть при 98, то последняя фирма получит 98, что больше суммарных полезностей агентов 42 + 43 = 85 < 98. Следовательно, в этом случае есть стимул к коалиционному отклонению.

Следующая модификация относится к функциям очков в аукционе отложенного принятия.

В DC есть задача определения цен в последующем временном периоде. Она включает в себя подзадачу, заключающуюся в понимании того, каким игрокам можно понизить цены. Обычно существует ограничение на объем станций, которые надо приобрести, иначе говоря, какую площадь вещания необходимо покрыть (целевая задача). В начале аукциона выставляются цены, чтобы было достаточно много желающих продать права на вещание, и для тех компаний, которые формируют избыточное предложение в определенной зоне, они понижаются, пока спрос не станет равен предложению.

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

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

Заключение

В этой работе мы изучили два типа механизмов, описанных в модели П. Милгрома и И. Сегала [1], доказали их эквивалентность и продолжили на двумерный случай. Кроме того, был разобран теоретический способ аппроксимации оптимального механизма с запаздывающим принятием и предложены варианты модификаций аукционов. Все эти факты позволяют нам эффективно применять данные механизмы в более сложных задачах, которые встречаются в жизни.

Список литературы

[1] P.Milgrom, I.Segal (2014). ’Deferred-Acceptance Auctions and Radio Spectrum Reallocation’. Доступно по ссылке: http://web.stanford.edu/~isegal/heuristic.pdf

[2] ’Envelope Theorem’. Доступно по ссылке: http://en.wikipedia.org/wiki/Envelope_theorem

[3] D. Gale, L. Shapley (1962). ’College Admissions and the Stability of Marriage’. American Mathematical Monthly 69: 9–14. Доступно по ссылке:http://www.math.umn.edu/~reiner/Classes/GaleShapleyOriginalArticle.pdf

[4] Е. Железова, С. Измалков, К. Сонин, И. Хованская (2013). ’Теория и практика двусторонних рынков’. Доступно по ссылке:http://www.nes.ru/dataupload/files/professors/sonin1-13.pdf

[5] NP-полная задача. Доступно по ссылке: http://en.wikipedia.org/wiki/NP-hard