Loading...
Please wait, while we are loading the content...
Similar Documents
CS364B: Frontiers in Mechanism Design Bonus Lecture: Gross Substitutes and Greedy Algorithms
| Content Provider | Semantic Scholar |
|---|---|
| Author | Roughgarden, Tim |
| Copyright Year | 2014 |
| Abstract | where A = {j : q(j) > p(j)} is the of items whose prices have increased (in q relative to p). That is, whenever a bidder loses the items of S ∩ A because of being outbid, it still wants to retain the items S \ A it has, at the original prices. We saw several examples of GS valuations, including k-unit demand valuations, downward-sloping valuations for identical items, and so on. In this lecture, we insist that Definition 1.1 holds for all real-valued prices vectors, including those that with some negative prices. We also won’t need to assume that vi(∅) = 0. We only consider valuations that are monotone (S ⊆ T implies v(S) ≤ v(T )). ∗ c ©2014, Tim Roughgarden. †Department of Computer Science, Stanford University, 462 Gates Building, 353 Serra Mall, Stanford, CA 94305. Email: tim@cs.stanford.edu. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://theory.stanford.edu/~tim/w14/l/bonus1.pdf |
| Alternate Webpage(s) | http://timroughgarden.org/w14/l/bonus1.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
