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

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

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 3 Аукцион Для каждого участника аукциона ценности делятся на три вида: Личная ценность (private value) Общая ценность (common value) Коррелированная ценность (correlated value)

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 4 Пример ценностей Непередаваемые билеты на концерт (личная ценность) Билеты на концерт (коррелированная) Коллекционная марка (общая или коррелированная)

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 5 Типы аукционов Существуют 4 основных вида аукционов: прямой (английский) голландский (оптовый) янки (своей цены) обратный

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 6 Английский аукцион Самый распространенный Проводится с гласными торгами и поднятием цены Начинается с минимальной цены Покупатели выставляют по очереди более высокие цены Товар достается давшему максимальную цену. При этом, покупатель оказывается в невыгодном положении, если вещь представляет собой общую или коррелированную ценность (winners curse) Не всегда торги заканчиваются продажей

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 7 Обратный аукцион Покупатели выставляют запросы на требуемые товары Продавцы соревнуются, предлагая лучшую цену и условия

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 8 Аукцион янки Главная особенность закрытые от других участников торги Каждый участник подает свою цену в конверте Продавец выбирает наибольшую Покупатель покупает товар по той цене, которую назвал Не имеет доминирующих стратегий Способствует шпионажу

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 9 Голландский аукцион Название происходит от рынка цветов в Голландии Это оптовый аукцион, на котором продавец может выставлять много единиц товара одновременно Покупатели могут претендовать на покупку многих единиц товара Все выигравшие покупатели платят только минимальную из выигравших цен

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 10 Аукцион Викри (Vickreys auction) Побеждает вторая по величине цена Для частных ценностей называние честной цены является доминантной стратегией Не способствует построению выигрышных стратегий Люди не любят их

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 11 Реализация IP Английского аукциона в FIPA Сообщение аукционера являются multicast- сообщениями В отличие от реального аукциона, возможна ситуация когда >=2 агента выставляют одну цену Продолжается пока есть хотя бы один покупатель

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 12 Реализация IP Английского аукциона в FIPA Возможно, что аукционер получает две и более заявки на один товар Протокол, в этом случае, позволяет отвергнуть предложение

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 13 Эквивалентность доходов В каком из аукционов продавцы получают больший доход? Согласно теореме об эквивалентности доходов: все четыре типа аукционов дают одинаковый ожидаемый доход в случае продажи частных ценностей и участия нейтральных к риску покупателей

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 14 Эквивалентность доходов Если покупатели совсем несклонны к риску, то Голландский и янки лучше В случае продажи общих или коррелированных ценностей, Английский аукцион дает больший доход

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 15 Trading Agent Competition В TAC-соревновании агенты участвуют в online аукционе комплементарных (взаимодополняющих друг друга, составляющих единое целое) и взаимозаменяемых вещей Цель агента – организовать для группы клиентов путешествие из TACTown в Бостон и обратно на 5 дней в середине июля

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 16 Trading Agent Competition Ценности аукциона: Авиабилеты, места в отеле и тд. – комплементарные Билеты на развлекательные мероприятия – взаимозаменяемые (например, на Boston Red Sox и Boston Symphony Orchestra)

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

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 18 Схема TAC соревнования

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 19 Аукционы в TAC-системе Для агентов формируется рынок из следующих вещей: Билеты в Бостон и обратно Резервирование комнат в двух конкурирующих отелях (the Grand Hotel и Le Fleabag Inn) Билеты на развлекательные мероприятия – на Boston Red Sox (r), the Boston Symphony (s) и Phantom of the Opera (t)

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 20 Для каждой комбинации (вещь, день) проводится отдельный аукцион. Всего их получается 28: –8 аукционов для авиабилетов –8 отель аукционов (2 отеля * 4 ночи) –12 аукционов для увеселительных мероприятий Все 28 аукционов происходят одновременно Аукционы в TAC-системе

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 21 Правила проведения аукционов для авиабилетов Авиабилеты не ограничены в количестве Продаются на аукционе, в котором цена генерируются случайно из диапазона [$250; $400] Каждые 30 секунд, к цене добавляется случайное число из диапазона [-$10; $10] Цена всегда должна находится в пределах [$150; $600] Перепродажа билетов запрещена

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 22 Правила проведения аукционов для комнат в отеле Продаются по 16 комнат в каждом отеле на каждую ночь Аукцион является Английским аукционом с выставлением сразу множества предметов Побеждает тот, кто попал в 16 наивысших цен для конкретного предмета и предложил 16-ю по величине цену в среднем Перепродажа комнат запрещена

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 23 Правила проведения аукционов для развлечений Билеты продаются среди TAC-агентов на двойном аукционе В этом аукционе каждый агент может выступать в роли покупателя и продавца и транзакции происходят постоянно Каждый агент получает начальное количество билетов на каждое мероприятие на каждый вечер: –0 билетов с вероятностью 25% –1 билет с вероятностью 50% –2 билета с вероятностью 25% Перепродажа билетов разрешена

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

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

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 26 Выигрыш агента Для каждого клиента, для каждого правильно сформированного пакета выигрыш агента считается как: 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}

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 27 Типичный пример динамики цены на номера в отеле Изображена зависимость цены на номер в отеле в зависимости от времени аукциона Аукцион длится 15 минут По мере приближения к концу аукциона цена начинает расти к бесконечности

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 28 Ссылки 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

Сошников Д. В., Устюжанин А. Е., Поляков А.О., Миханов С.В. Многоагентные интеллектуальные системы Слайд 29 Спасибо за внимание! Ваши вопросы?