Рюкзачный аукцион

Рюкзачный аукцион — это аукцион, на котором продается несколько одинаковых предметов, и несколько участников с разной оценкой заинтересованы в разном количестве предметов. Цель состоит в том, чтобы выбрать подмножество участников торгов с общим спросом, не превышающим количество позиций, и, при условии этого, максимальную общую стоимость. Чтобы найти этот набор участников торгов, необходимо решить задачу о рюкзаке , что объясняет термин «рюкзачный аукцион».

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

Обозначения

Имеется m одинаковых лотов и n разных участников торгов. Предпочтения каждого участника торгов i обозначаются двумя числами:

Спрос s _i — целое число, определяющее, сколько товаров хочет этот участник торгов. Участнику торгов нужно именно это количество предметов, и он не может использовать большее или меньшее количество предметов.
Значение v _i — число, определяющее, сколько денег участник торгов ожидает получить от получения ровно s _i предметов.

Возможным результатом аукциона является подмножество W победителей торгов , такое, что их общий спрос не превышает m : $\sum _{i\in W}s_{i}\leq m$ . Стоимость : набора W победителей равна сумме значений победителей $\sum _{i\in W}v_{i}$ . Цель состоит в том, чтобы найти возможный набор победителей с максимальной общей стоимостью.

В примере времени трансляции, если на рекламу отведено 5 минут, то m = 300 (количество секунд), n = количество потенциальных рекламодателей, s _i = продолжительность i- й рекламы в секундах и v _i = деньги, которые я рассчитываю получить, если его реклама будет транслироваться.

Базовые решения

Если требования и ценности всех участников торгов публично известны, то задачу можно решить с помощью любого алгоритма задачи о рюкзаке . Задача NP-сложная, но она имеет эффективные алгоритмы аппроксимации с постоянным коэффициентом, а также FPTAS . На практике обычно требования s _i общеизвестны (например, должна быть известна продолжительность рекламы каждого рекламодателя), но оценки vi _. являются частной информацией участников торгов Таким образом, аукционный механизм должен стимулировать участников торгов раскрывать свои истинные оценки.

Аукцион VCG — это правдивый механизм , который можно использовать для максимизации суммы ценностей, одновременно стимулируя агентов раскрывать свою истинную ценность. Однако это работает только в том случае, если результат максимизирует значения; он не работает с приближениями (если результат только приблизительно оптимален, то VCG перестает быть правдивым). Найти оптимальный результат невозможно за полиномиальное время, если только P=NP. Возникает вопрос: существуют ли правдивые механизмы, которые работают за полиномиальное время и достигают примерно оптимального результата?

Правдивые механизмы аппроксимации

Муалем и Нисан дали первый утвердительный ответ на этот вопрос: ^[1] они показали, что объединение двух жадных алгоритмов дает правдивый механизм двухфакторной аппроксимации.

Брист, Криста и Вокинг ^[2] улучшил этот результат, показав правдивый FPTAS .

Даттинг, Гкацелис и Рафгарден ^[3] представил правдивый аукцион с отложенным принятием , который достигает приближения O (log m ), и доказал, что ни один аукцион с отложенным принятием не может достичь лучшего приближения. Это показывает разделение между общим классом правдивых аукционов и подклассом аукционов с отсрочкой акцепта.

Ссылки

^ Муалем, Ахува; Нисан, Ноам (1 ноября 2008 г.). «Правдивые механизмы аппроксимации для ограниченных комбинаторных аукционов» . Игры и экономическое поведение . Специальный выпуск в честь Майкла Б. Машлера. 64 (2): 612–631. дои : 10.1016/j.geb.2007.12.009 . ISSN 0899-8256 .
^ Брист, Патрик; Криста, Петр; Фёкинг, Бертольд (1 января 2011 г.). «Методы аппроксимации проектирования утилитарных механизмов» . SIAM Journal по вычислительной технике . 40 (6): 1587–1622. дои : 10.1137/090772988 . ISSN 0097-5397 .
^ Дюттинг, Пол; Гкацелис, Василис; Рафгарден, Тим (01 июня 2014 г.). «Проведение аукционов отложенного приема» (PDF) . Материалы пятнадцатой конференции ACM по экономике и вычислениям . ЭК '14. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 187–204. дои : 10.1145/2600057.2602861 . ISBN 978-1-4503-2565-3 . S2CID 1950202 .

[1] Муалем, Ахува; Нисан, Ноам (1 ноября 2008 г.). «Правдивые механизмы аппроксимации для ограниченных комбинаторных аукционов» . Игры и экономическое поведение . Специальный выпуск в честь Майкла Б. Машлера. 64 (2): 612–631. дои : 10.1016/j.geb.2007.12.009 . ISSN 0899-8256 .

[2] Брист, Патрик; Криста, Петр; Фёкинг, Бертольд (1 января 2011 г.). «Методы аппроксимации проектирования утилитарных механизмов» . SIAM Journal по вычислительной технике . 40 (6): 1587–1622. дои : 10.1137/090772988 . ISSN 0097-5397 .

[3] Дюттинг, Пол; Гкацелис, Василис; Рафгарден, Тим (01 июня 2014 г.). «Проведение аукционов отложенного приема» (PDF) . Материалы пятнадцатой конференции ACM по экономике и вычислениям . ЭК '14. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 187–204. дои : 10.1145/2600057.2602861 . ISBN 978-1-4503-2565-3 . S2CID 1950202 .

[1]

[2]

[3]