Равновесие дрожащей руки

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

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

Рассмотрим пример на табл. 4.3:

Таблица 4.3

Игровая модель, заданная таблицей 4.3, представляет собой взаимоотношение двух игроков с точки зрения взаимного доверия. В данной модели имеется два равновесия по Нэшу: (Недоверие; Недоверие) и (Доверие; Доверие).

Проанализируем ситуацию с позиции первого игрока в равновесии (Доверие; Доверие). Случайное отклонение Игрока 1 и выбор стратегии Недоверие не изменит его личный выигрыш, а выигрыш соперника уменьшится до 0. Рациональным ответом Игрока 2 в следующем раунде будет изменение стратегии на Недоверие для повышения собственного выигрыша. Таким образом, при последующем разыгрывании рациональные игроки придут к равновесию (Недоверие; Недоверие). В силу симметричности матриц аналогичные рассуждения можно провести при отклонении от равновесия второго игрока.

Рассмотрим теперь последствия единичного отклонения от ситуации (Недоверие; Недоверие). При выборе первым игроком стратегии Доверия, его выигрыш уменьшится до 0, в то время как выигрыш соперника увеличится до 2. В то же время у соперника не будет мотивов изменять собственную стратегию поведения на Доверие, так как это не увеличит его выигрыш. А первому игроку, наоборот, выгодно вернуться к стратегии Недоверия. Таким образом, случайное изменение стратегии любого из игроков не приводит к изменению разыгрываемой ситуации, и равновесие (Недоверие; Недоверие) является равновесием дрожащей руки.

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

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

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

Аукционов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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