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

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

Требовать

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

	Ценить	Цена
Яблоко	2	5
Банан	4	3
вишня	6	1

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

Оракул

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

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

Приложения

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

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

См. также

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

Ссылки

^ Вондрак, Ян (17 мая 2008 г.). «Оптимальное приближение субмодульной задачи благосостояния в модели оракула ценностей» . Материалы сорокового ежегодного симпозиума ACM по теории вычислений . СТОК '08. Виктория, Британская Колумбия, Канада: Ассоциация вычислительной техники. стр. 67–74. дои : 10.1145/1374376.1374389 . ISBN 978-1-60558-047-0 . S2CID 170510 .
^ Добзинский, Шахар; Шапира, Майкл (22 января 2006 г.). «Улучшенный алгоритм аппроксимации комбинаторных аукционов с субмодульными участниками торгов» . Материалы семнадцатого ежегодного симпозиума ACM-SIAM по дискретному алгоритму - SODA '06 . СОДА '06. Майами, Флорида: Общество промышленной и прикладной математики. стр. 1064–1073. дои : 10.1145/1109557.1109675 . ISBN 978-0-89871-605-4 . S2CID 13108913 .
^ Файги, Уриэль; Вондрак, Ян (9 декабря 2010 г.). «Субмодульная проблема благосостояния с запросами спроса» . Теория вычислений . 6 (1): 247–290. дои : 10.4086/toc.2010.v006a011 . ISSN 1557-2862 .
^ Кодотти, Бруно; МакКьюн, Бентон; Варадараджан, Кастури (22 мая 2005 г.). «Рыночное равновесие через функцию избыточного спроса» . Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений . СТОК '05. Балтимор, Мэриленд, США: Ассоциация вычислительной техники. стр. 74–83. дои : 10.1145/1060590.1060601 . ISBN 978-1-58113-960-0 . S2CID 15453505 .
^ Голдберг, Пол В.; Лок, Эдвин; Мармолехо-Коссио, Франциско (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 .

[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 .

[1]

[2]

[3]

[4]

[5]