Дробно субаддитивная оценка

Функция множества называется дробно-субаддитивной , или XOS (не путать с OXS ), если она является максимальной из нескольких аддитивных функций множества . Этот класс оценки был определен и назван XOS Ноамом Нисаном в контексте комбинаторных аукционов . Термин «дробно субаддитивный» был введен Уриэлем Файги.

Определение

Существует конечный базовый набор элементов, $M:=\{1,\ldots ,m\}$.

Есть функция $v$ который присваивает номер каждому подмножеству $M$.

Функция $v$ называется дробно-субаддитивным (или XOS), если существует набор функций множества, $\{a_{1},\ldots ,a_{l}\}$, такой, что:

• Каждый $a_{j}$ является аддитивным, т. е . присваивает каждому подмножеству $X\subseteq M$, сумма значений элементов в $X$.
• Функция $v$ является поточечным максимумом функции $a_{j}$. Т.е. для каждого подмножества $X\subseteq M$:

$v(X)=\max _{j=1}^{l}a_{j}(X)$

Эквивалентное определение

Название дробно-субадитивная происходит от следующего эквивалентного определения: функция множества. $v$ является дробно субаддитивным , если для любого $S\subseteq M$ и любая коллекция $\{\alpha _{i},T_{i}\}_{i=1}^{k}$ с $\alpha _{i}>0$ и $T_{i}\subseteq M$ такой, что $\sum _{T_{i}\ni j}\alpha _{i}\geq 1$ для всех $j\in S$, у нас есть $v(S)\leq \sum _{i=1}^{k}\alpha _{i}v(T_{i})$.

Связь с другими служебными функциями

Каждая субмодульная функция множества является XOS, а каждая функция XOS является субаддитивной функцией множества .

См. также: Функции полезности для неделимых благ .