On competitiveness in uniform utility allocation markets |
| |
| Authors: | Deeparnab Chakrabarty Nikhil Devanur |
| |
| Institution: | a Department of Combinatorics and Optimization, University of Waterloo, Canada
b Microsoft Research, Redmond, WA, USA |
| |
| 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. |
| |
| Keywords: | Market equilibrium Submodular functions Fractionally sub-additive functions |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
