The Finite Matroid-Based Valuation Conjecture is False
2019
Online
report
The matroid-based valuation conjecture of Ostrovsky and Paes Leme states that all gross substitutes valuations on $n$ items can be produced from merging and endowments of weighted ranks of matroids defined on at most $m(n)$ items. We show that if $m(n) = n$, then this statement holds for $n \leq 3$ and fails for all $n \geq 4$. In particular, the set of gross substitutes valuations on $n \geq 4$ items is strictly larger than the set of matroid based valuations defined on the ground set $[n]$. Our proof uses matroid theory and discrete convex analysis to explicitly construct a large family of counter-examples. It indicates that merging and endowment by themselves are poor operations to generate gross substitutes valuations. We also connect the general MBV conjecture and related questions to long-standing open problems in matroid theory, and conclude with open questions at the intersection of this field and economics.
Comment: simpler proofs, corrected minor errors, 22 pages and 11 figures
Titel: |
The Finite Matroid-Based Valuation Conjecture is False
|
---|---|
Autor/in / Beteiligte Person: | Tran, Ngoc Mai |
Link: | |
Veröffentlichung: | 2019 |
Medientyp: | report |
Schlagwort: |
|
Sonstiges: |
|