Лекция 6. Сложные взаимодействия. Аукционы презентация

Лекция 6. Сложные взаимодействия.
Аукционы

Аукцион

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

Аукцион

Для каждого участника аукциона ценности делятся на три вида:
Личная ценность (private value)
Общая ценность (common value)
Коррелированная ценность (correlated value)

Пример ценностей

Непередаваемые билеты на концерт (личная ценность)
Билеты на концерт (коррелированная)
Коллекционная марка (общая или коррелированная)

Типы аукционов

Существуют 4 основных вида аукционов:
прямой (английский)
голландский (оптовый)
янки (своей цены)
обратный

Английский аукцион

Самый распространенный
Проводится с гласными торгами и поднятием цены
Начинается с минимальной цены
Покупатели выставляют по очереди более высокие цены
Товар достается давшему максимальную цену. При этом, покупатель оказывается в невыгодном положении, если вещь представляет собой общую или коррелированную ценность (winner’s curse)
Не всегда торги заканчиваются продажей

Обратный аукцион

Покупатели выставляют запросы на требуемые товары
Продавцы соревнуются, предлагая лучшую цену и условия

Аукцион янки

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

Голландский аукцион

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

Аукцион Викри (Vickrey’s auction)

Побеждает вторая по величине цена
Для частных ценностей называние честной цены является доминантной стратегией
Не способствует построению выигрышных стратегий
Люди не любят их

Реализация IP Английского аукциона в FIPA

Сообщение аукционера являются multicast-сообщениями
В отличие от реального аукциона, возможна ситуация когда >=2 агента выставляют одну цену
Продолжается пока есть хотя бы один покупатель

Реализация IP Английского аукциона в FIPA

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

Эквивалентность доходов

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

Эквивалентность доходов

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

Trading Agent Competition

В TAC-соревновании агенты участвуют в online аукционе комплементарных (взаимодополняющих друг друга, составляющих единое целое) и взаимозаменяемых вещей
Цель агента – организовать для группы клиентов путешествие из TACTown в Бостон и обратно на 5 дней в середине июля

Trading Agent Competition

Ценности аукциона:
Авиабилеты, места в отеле и тд. – комплементарные
Билеты на развлекательные мероприятия – взаимозаменяемые (например, на Boston Red Sox и Boston Symphony Orchestra)

Суть соревнования

Организовать путешествие на 5 дней из TACTown в Boston для группы людей
Товары для развлечений и путешествий выставляются на online аукционе, который длится 15 минут
Цель агента – приобрести вещи таким образом, чтобы удовлетворить потребности клиентов и потратить минимум денег
Баллы агента – разность между стоимостью услуг, которые он приносит своим клиентам и его расходами

Схема TAC соревнования

Аукционы в TAC-системе

Для агентов формируется рынок из следующих вещей:
Билеты в Бостон и обратно
Резервирование комнат в двух конкурирующих отелях (the Grand Hotel и Le Fleabag Inn)
Билеты на развлекательные мероприятия – на Boston Red Sox (r), the Boston Symphony (s) и Phantom of the Opera (t)

Для каждой комбинации (вещь, день) проводится отдельный аукцион. Всего их получается 28:
8 аукционов для авиабилетов
8 отель аукционов (2 отеля * 4 ночи)
12 аукционов для увеселительных мероприятий
Все 28 аукционов происходят одновременно

Аукционы в TAC-системе

Правила проведения аукционов для авиабилетов

Авиабилеты не ограничены в количестве
Продаются на аукционе, в котором цена генерируются случайно из диапазона [$250; $400]
Каждые 30 секунд, к цене добавляется случайное число из диапазона [-$10; $10]
Цена всегда должна находится в пределах [$150; $600]
Перепродажа билетов запрещена

Правила проведения аукционов для комнат в отеле

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

Правила проведения аукционов для развлечений

Билеты продаются среди TAC-агентов на двойном аукционе
В этом аукционе каждый агент может выступать в роли покупателя и продавца и транзакции происходят постоянно
Каждый агент получает начальное количество билетов на каждое мероприятие на каждый вечер:
0 билетов с вероятностью 25%
1 билет с вероятностью 50%
2 билета с вероятностью 25%
Перепродажа билетов разрещена

Требования игры

Соревнуются 8 TAC-агентов
Каждый агент представляет интересы 8-ми клиентов
Каждый клиент характеризуется случайным набором предпочтений:
Об идеальных датах прилета и отлета (числа IAD, IDD, которые зависят от дней [1;4] и [2;5] соответственно)
Желание жить в Grand Hotel (HV, целое число из диапазона [50;150]
Важность развлекательных мероприятий (RV, SV, TV – целые числа в диапазоне [0;200] для каждого из мероприятий)

Задача агента – сформировать правильный пакет предложений для каждого из клиентов
В этот пакет входят:
Даты прилета и отлета (AD и DD)
Тип отеля (H для Grand Hotel, F для Le Fleabag Inn)
Билеты на развлечения (I(j,k) – включает ли пакет билет в вечер j на мероприятие k, k {r, s, t}
Правильный пакет – это пакет, в котором:
AD < DD
Один и тот же отель зарезервирован на все время пребывания
Максимум одно развлечение на каждый вечер присутствует
Максимум по одному билету на каждый тип развлечений имеется

Требования игры

Выигрыш агента

Для каждого клиента, для каждого правильно сформированного пакета выигрыш агента считается как:
utility = 100 – travelPenalty + hotelBonus + funBonus
travelPenalty = 100*(|IAD – AD| + |IDD – DD|
hotelBonus = HV, если H = GrandHotel; иначе 0
funBonus = Σ {I(j,r) * RV + I(j,s) * SV + I(j,t) * TV}

Типичный пример динамики цены на номера в отеле

Изображена зависимость цены на номер в отеле в зависимости от времени аукциона
Аукцион длится 15 минут
По мере приближения к концу аукциона цена начинает расти к бесконечности

Ссылки

Wurman, P. R., Wellman, M. P., and Walsh, W. E. Specifying rules for electronic auctions. AI Magazine, 23(3):15–23., 2002
Wooldridge, M. Introduction to MultiAgent Systems. John Wiley and Sons, 2002

Спасибо за внимание! Ваши вопросы?