Loading...
Please wait, while we are loading the content...
Similar Documents
CS364B: Frontiers in Mechanism Design Lecture #17: Part II: Beyond Smoothness and XOS Valuations
| Content Provider | Semantic Scholar |
|---|---|
| Author | Roughgarden, Tim |
| Copyright Year | 2014 |
| Abstract | 1 Subadditive Valuations 1.1 The Setup In this lecture we study a scenario that generalizes almost all of the ones that we've studied in the course. • A set U of m non-identical items. As always, we also assume that every valuation satisfies v i (∅) = 0 and is monotone (i.e., S ⊆ T implies v i (S) ≤ v(T)). Subadditivity is yet another way to formalize the idea that items are not complements — that getting some items don't suddenly make other items more valuation. Of all the articulations of this idea that we've seen, subadditivity is the most general; see Figure 1. Proposition 1.1 The set of subadditive valuations strictly contains the set of XOS valuations . |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://theory.stanford.edu/~tim/w14/l/l375.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
