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

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

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

Существует функция , которая присваивает номер каждому подмножеству .${\displaystyle v}$${\displaystyle М}$

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

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

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

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

Каждая субмодулярная функция множества является XOS, а каждая функция XOS является субаддитивной функцией множества . ^[1]

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