Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142831 | Operations Research Letters | 2009 | 4 Pages |
Abstract
We call a market competitive if increasing the endowment of one buyer does not increase the equilibrium utility of another. We show that every competitive uniform utility allocation market is a submodular utility allocation market, answering a question of Jain and Vazirani [K. Jain, V.V. Vazirani, Eisenberg–Gale markets: Algorithms and structural properties, in: STOC, 2007]. Our proof proceeds via characterizing non-submodular fractionally sub-additive functions.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Deeparnab Chakrabarty, Nikhil Devanur,