Функция набора называется дробно субаддитивной (или XOS ), если она является максимумом из нескольких аддитивных функций набора . Этот класс оценки был определен и назван XOS Ноамом Нисаном в контексте комбинаторных аукционов . [1] Термин «дробно-субаддитивный» был дан Уриэлем Фейге. [2]
Определение
Есть конечный базовый набор предметов, .
Есть функция который присваивает номер каждому подмножеству .
Функция называется дробно-субаддитивным (или XOS), если существует набор заданных функций,, такое что: [3]
- Каждый является аддитивным, т.е. присваивает каждому подмножеству, сумма значений элементов в .
- Функция - поточечный максимум функций. Т.е. для каждого подмножества:
Эквивалентное определение
Название дробно субаддитивное происходит от следующего эквивалентного определения: функция набора является дробно субаддитивным, если для любого и любая коллекция с участием а также такой, что для всех , у нас есть . Это можно рассматривать как частичное ослабление определения субаддитивности.
Отношение к другим служебным функциям
Каждая функция субмодульного набора - это XOS, а каждая функция XOS - функция субаддитивного набора . [1]
См. Также: Вспомогательные функции для неделимых товаров .
Рекомендации
- ^ а б Нисан, Ноам (2000). «Торги и размещение на комбинаторных аукционах». Материалы 2-й конференции ACM по электронной коммерции - EC '00 . п. 1. дои : 10,1145 / 352871,352872 . ISBN 1581132727.
- ^ Файги, Уриэль (2009). «О максимизации благосостояния при субаддитивных функциях полезности». SIAM Journal on Computing . 39 : 122–142. CiteSeerX 10.1.1.86.9904 . DOI : 10.1137 / 070680977 .
- ^ Христодулу, Джордж; Ковач, Аннамария; Шапира, Майкл (2016). «Байесовские комбинаторные аукционы». Журнал ACM . 63 (2): 1. CiteSeerX 10.1.1.721.5346 . DOI : 10.1145 / 2835172 .