Спрос оракула

В алгоритмической теории игр , разделе информатики и экономики , оракул спроса — это функция, которая по заданному вектору цен возвращает спрос агента. Он используется многими алгоритмами, связанными с ценообразованием и оптимизацией на онлайн-рынке . Обычно его противопоставляют значению oracle , которое представляет собой функцию, которая по заданному набору элементов возвращает значение, присвоенное им агентом.

Требовать

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

Предположим, что функция полезности агента аддитивна (= стоимость набора равна сумме стоимостей предметов в наборе) и квазилинейна (= полезность набора равна стоимости набора минус его цена). Тогда спрос агента с учетом цен представляет собой набор {Банан, Вишня}, который дает полезность (4+6)–(3+1) = 6. Каждый другой набор дает агенту меньшую полезность. Например, пустой набор дает полезность 0, а набор всех элементов дает полезность (2+4+6)-(5+3+1)=3.

Оракул

При аддитивных оценках функцию спроса легко вычислить — нет необходимости в «оракуле». Однако в целом агенты могут иметь комбинаторные оценки . Это означает, что для каждой комбинации элементов они могут иметь разное значение, которое не обязательно является суммой их значений для отдельных элементов. Для описания такой функции для m элементов может потребоваться до 2 ^m чисел — число для каждого подмножества. Это может быть невозможно, если m велико. Поэтому многие алгоритмы для рынков используют два типа оракулов:

• Оракул значений может отвечать на запросы значений : учитывая пакет, он возвращает его значение.
• Оракул спроса может отвечать на запросы спроса : учитывая вектор цен, он возвращает пакет, который максимизирует квазилинейную полезность (стоимость минус цена).

Приложения

Некоторые примеры алгоритмов, использующих оракулы спроса:

• Максимизация благосостояния : имеется n агентов и m предметов. Каждый агент представлен оракулом стоимости и оракулом спроса. Требуется распределить предметы между агентами так, чтобы сумма значений была максимальной. В общем, проблема NP-трудна, но известны аппроксимации для особых случаев, таких как субмодулярные оценки (это называется «субмодулярная проблема благосостояния»). Некоторые алгоритмы используют только оракул значений; ^[1] другие алгоритмы также используют оракул спроса . ^{[2] [3]}
• Цены без зависти : имеется n агентов и m товаров. Каждый агент представлен оракулом стоимости и оракулом спроса. Требуется найти вектор цен и такое распределение товаров, чтобы ни один агент не завидовал и при этом доход продавца был максимальным.
• Расчет рыночного равновесия . ^[4]
• Изучение спроса на сильные заменители . ^[5]

Смотрите также

• машина Oracle
• Кривая спроса
• Модель запросов Робертсона-Уэбба — аналогичная модель запросов в области разрезания торта.

Рекомендации

1. Вондрак, Январь (17 мая 2008 г.). «Оптимальное приближение субмодульной проблемы благосостояния в модели оракула ценностей». Материалы сорокового ежегодного симпозиума ACM по теории вычислений . СТОК '08. Виктория, Британская Колумбия, Канада: Ассоциация вычислительной техники. стр. 67–74. дои : 10.1145/1374376.1374389. ISBN 978-1-60558-047-0. S2CID  170510.
2. Добзинский, Шахар; Шапира, Майкл (22 января 2006 г.). «Улучшенный алгоритм аппроксимации комбинаторных аукционов с субмодульными участниками торгов». Материалы семнадцатого ежегодного симпозиума ACM-SIAM по дискретному алгоритму - SODA '06 . СОДА '06. Майами, Флорида: Общество промышленной и прикладной математики. стр. 1064–1073. дои : 10.1145/1109557.1109675. ISBN 978-0-89871-605-4. S2CID  13108913.
3. Файги, Уриэль; Вондрак, Ян (9 декабря 2010 г.). «Субмодульная проблема благосостояния с запросами спроса». Теория вычислений . 6 (1): 247–290. дои : 10.4086/toc.2010.v006a011 . ISSN  1557-2862.
4. Коденотти, Бруно; МакКьюн, Бентон; Варадараджан, Кастури (22 мая 2005 г.). «Рыночное равновесие через функцию избыточного спроса». Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений . СТОК '05. Балтимор, Мэриленд, США: Ассоциация вычислительной техники. стр. 74–83. дои : 10.1145/1060590.1060601. ISBN 978-1-58113-960-0. S2CID  15453505.
5. Голдберг, Пол В.; Лок, Эдвин; Мармолехо-Коссио, Франциско (2020). Чен, Сюйджин; Гравин, Николай; Хофер, Мартин; Мехта, Рута (ред.). «Изучение спроса на сильные заменители с помощью запросов». Экономика Интернета и Интернета . Конспекты лекций по информатике. 12495 . Чам: Springer International Publishing: 401–415. arXiv : 2005.01496 . дои : 10.1007/978-3-030-64946-3_28. ISBN 978-3-030-64946-3. S2CID  218487768.