Combinatorial Auctions with Decreasing Marginal Utilities
| dc.creator | Lehmann, Benny | |
| dc.creator | Lehmann, Daniel | |
| dc.creator | Nisan, Noam | |
| dc.date | 2002-02-15 | |
| dc.date | 2002-09-12 | |
| dc.date.accessioned | 2026-07-07T06:27:57Z | |
| dc.date.available | 2026-07-07T06:27:57Z | |
| dc.description | In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such submodular buyers. The valuations of such buyers are placed within a hierarchy of valuations that exhibit no complementarities, a hierarchy that includes also OR and XOR combinations of singleton valuations, and valuations satisfying the gross substitutes property. Those last valuations are shown to form a zero-measure subset of the submodular valuations that have positive measure. While we show that the allocation problem among submodular valuations is NP-hard, we present an efficient greedy 2-approximation algorithm for this case and generalize it to the case of limited complementarities. No such approximation algorithm exists in a setting allowing for arbitrary complementarities. Some results about strategic aspects of combinatorial auctions among players with decreasing marginal utilities are also presented. | |
| dc.description | To appear in GEB. Preliminary version appeared in EC'01 | |
| dc.identifier | https://arxiv.org/abs/cs/0202015 | |
| dc.identifier | http://arxiv.org/abs/cs/0202015 | |
| dc.identifier | Games and Economic Behavior, Vol 55/2 May 2006 pp 270-296 | |
| dc.identifier | doi:10.1016/j.geb2005.02.006 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/97565 | |
| dc.subject | Computer Science and Game Theory | |
| dc.subject | J.4 | |
| dc.title | Combinatorial Auctions with Decreasing Marginal Utilities | |
| dc.type | text |