Wycena ułamkowo-subaddytywna

Funkcja zbioru nazywana jest ułamkowo subaddytywną (lub XOS ), jeśli jest to maksimum kilku addytywnych funkcji zbioru . Ta klasa wyceny została zdefiniowana i nazwana XOS przez Noama Nisana w kontekście aukcji kombinatorycznych . Termin ułamkowo subaddytywny został podany przez Uriela Feige.

Definicja

Istnieje skończony podstawowy zestaw elementów, ${\ Displaystyle M: ​​= \ {1, \ ldots, m \}}$ .

Istnieje funkcja $liczbę$$która przypisuje$ do każdego .

Funkcja $XOS$ jest ułamkowo subaddytywną (lub ), jeśli istnieje zbiór funkcji zestawu, ${\ Displaystyle \ {a_ {1}, \ ldots, a_ { l}\}}$ , takie, że:

• Każdy jest $addytywny$ , tj . przypisuje każdemu podzbiorowi wartości elementów w $\ subseteq M}$$Displaystyle$ .
• Funkcja jest punktowym maksimum funkcji $j}}$${ \ displaystyle a_$ . Tj. dla każdego podzbioru ${\ Displaystyle X \ subseteq M}: X ⊆ M {\ Displaystyle X \ subseteq M$ }:

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

Równoważna definicja

Nazwa ułamkowo subaddytywna pochodzi z następującej równoważnej definicji: funkcja zbioru ${\ Displaystyle \ {\ alpha _ {i}, T_ {i} \} _ {i = 1} ^ {k}}$$kolekcji$$T$ jeśli dla dowolnego dowolnej z ${\ Displaystyle \ alpha _ {i}> 0}$ i $}$$i$ \ takie wszystko ${\ Displaystyle j \ w S}$ , mamy ${\ Displaystyle v (S) \ równoważnik \ suma _ {i = 1} ^ {k}\alpha_{i}v(T_{i})}$ .

Stosunek do innych funkcji użytkowych

Każda podmodułowa funkcja zbioru jest XOS, a każda funkcja XOS jest subaddytywną funkcją zbioru .

Zobacz też: Funkcje użytkowe dóbr niepodzielnych .