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

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

Определение

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

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

Функция называется дробно-субаддитивной (или 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 \{\alpha _{i},T_{i}\}_{i=1}^{k}}$ ${\displaystyle \alpha _{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]

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

Ссылки

1. Nisan, Noam (2000). "Торги и распределение на комбинаторных аукционах". Труды 2-й конференции ACM по электронной коммерции - EC '00 . стр. 1. doi :10.1145/352871.352872. ISBN 1581132727.
2. Фейге, Уриэль (2009). «О максимизации благосостояния, когда функции полезности являются субаддитивными». Журнал SIAM по вычислениям . 39 : 122–142. CiteSeerX 10.1.1.86.9904 . doi :10.1137/070680977. 
3. Христодулу, Джордж; Ковач, Аннамария; Шапира, Майкл (2016). «Байесовские комбинаторные аукционы». Журнал ACM . 63 (2): 1. CiteSeerX 10.1.1.721.5346 . doi :10.1145/2835172.