“Fractionally subadditive”的意思、由来-开放百科全书

词条

Fractionally subadditive

释义

Definition
Relation to other utility functions
References

A set function is called fractionally subadditive (or XOS) if it is the maximum of several additive set functions.

This valuation class was defined, and termed XOS, by Noam Nisan, in the context of combinatorial auctions.^[1] The term fractionally-subadditive was given by Uriel Feige.^[2]

Definition

There is a finite base set of items, .

There is a function which assigns a number to each subset of .

The function is called fractionally-subadditive (or XOS) if there exists a collection of set functions, , such that:^[3]

Each is additive, i.e., it assigns to each subset , the sum of the values of the items in .
The function is the pointwise maximum of the functions . I.e, for every subset :

Relation to other utility functions

Every submodular set function is XOS, and every XOS function is a subadditive set function.^[1]

See also: Utility functions on indivisible goods.

References

1. ^¹{{cite conference|doi=10.1145/352871.352872|chapter=Bidding and allocation in combinatorial auctions|title=Proceedings of the 2nd ACM conference on Electronic commerce - EC '00|pages=1|year=2000|last1=Nisan|first1=Noam|isbn=1581132727}}
2. ^{{cite journal|doi=10.1137/070680977|title=On Maximizing Welfare when Utility Functions Are Subadditive|journal=SIAM Journal on Computing|volume=39|pages=122–142|year=2009|last1=Feige|first1=Uriel|citeseerx=10.1.1.86.9904}}
3. ^{{cite journal|doi=10.1145/2835172|title=Bayesian Combinatorial Auctions|journal=Journal of the ACM|volume=63|issue=2|pages=1|year=2016|last1=Christodoulou|first1=George|last2=Kovács|first2=Annamária|last3=Schapira|first3=Michael|citeseerx=10.1.1.721.5346}}

1 : Utility function types

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。