Аукционы и справедливое разделение ресурсов

4.3.1. Основные определения и классификация

Аукционов

 

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

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

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

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

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

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

Также различают однораундовые и многораундовые аукционы. С повышением и понижением ставок.

По технике проведения можно выделить следующие виды аукционов.

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

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

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

4. Аукцион первой цены – закрытый аукцион, в котором победитель, назвавший наивысшую цену, получает товар за ту цену, которую он предложил. Если выставлен лот из многих единиц товара, то выигрывает не только давший наивысшую цену, но и участники, предложившие цену ниже. Из-за того, что не все победители платят одинаковую цену, такой аукцион называют дискриминационным.

5. Аукцион второй цены (Викри, William Spencer Vickrey) также представляет собой закрытый аукцион, в котором побеждает покупатель, предложивший самую высокую цену. Особенностью аукциона является то, что победитель производит оплату товара не по предложенной им цене, а по второй по величине сумме предложения.

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

У рассмотренных аукционов существует множество свойств, достоинств и недостатков. Остановимся на некоторых из них.

1. Для повышения прибыли продавца, в аукционах часто вводится резервная цена. Если в ходе торгов ставки не достигли размеров резервной цены, то товар не продается.

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

3. Открытые аукционы более сложны для проведения (особенно при автоматическом порядке), возможен сговор участников, а сами торги могут занимать много времени.

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

 

Аукцион второй цены

 

Процедура проведения аукциона второй цены включает следующие основные шаги.

1. Участники одновременно выдвигают заявки (ставки - bid) с ценами, которые они готовы заплатить за представленный товар.

2. Побеждает заявка с наибольшей ценой. Победивший игрок выплачивает за товар вторую по величине цену.

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

Введем следующие обозначения.

 - множество участников аукциона.

 - ценность выставленного на аукционе лота для участника i (private valuation), .

 - ставка (bid) участника i в ходе торгов, .

 - подситуация торгов, вектор ставок, сделанных всеми участниками аукциона кроме i.

 - максимальное значение ставки без учета ставки участника i.

Очевидно, что в общем случае ставка участника  может не совпадать с тем, как он на самом деле оценивает данный товар . Более того, как правило, задачей участника является приобрести товар как можно дешевле, тем самым увеличивая собственный выигрыш.

В случае, если , i -ый участник становится победителем, то функция его полезности в аукционе второй цены равна . В аукционе первой цены в случае победы i -го участника можно было бы записать . Если побеждает заявка другого участника , то полезность .

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

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

Рассмотрим возможные стратегии поведения отдельного игрока.

 

Рис. 4.1. Аукцион второй цены. Участник выставляет ставку выше личной оценки стоимости товара

 

1) Игрок заявляет ставку большую, чем его реальная ценность: . Рассмотрим различные подситуации  и соответствующие им значения  (рис. 4.1).

a) , в этом случае ставка  выигрывает , но для победы достаточно указать и ;

b) , в этом случае участник i выигрывает, но получает нулевой выигрыш: ;

c) , в этом случае ставка выигрывает, однако, участник получает отрицательную полезность: ; большую полезность () можно получить при , при этом ставка не выигрывает;

d) , в этом случае ставка не выигрывает, а полезность игрока .

 

Рис. 4.2. Аукцион второй цены. Участник выставляет ставку ниже личной оценки стоимости товара

 

2) Игрок заявляет ставку меньшую, чем его реальная ценность: . Аналогично рассмотрим различные подситуации  и соответствующие им значения  (рис. 4.2).

a) , в этом случае ставка  выигрывает с полезностью , а аналогичный результат можно получить с ;

b) , заявка не выигрывает, ; больший выигрыш  можно получить при ;

c) , в этом случае ставка не выигрывает, а полезность .

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

Таким образом, в аукционе второй цены наилучшим ответом для каждого игрока является назначение ставки равной личной оценке стоимости товара. Из этого следует следующее утверждение.

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

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

Кроме того, аукцион второй цены максимизирует общественное благо, а именно: , где , если i- й участник побеждает и , если проигрывает (при разыгрывании одного лота, ). Другими словами, товар забирает участник, которому он действительно больше других важен, то есть участник с максимальной личной оценкой данного товара.

Интересно отметить, что данное свойство проявляется в закрытом аукционе, в котором организатор не имеет ни малейшего понятия о личных предпочтениях участников (или даже не имеет представления о личностях участников).