The finite matroid-based valuation conjecture is false

DOI10.1137/19M1304295MaRDI QIDQ4959128zbMATH OpenOpenAlexWikidataFDO

Authors Ngoc Mai Tran

Publication date 10 September 2021

Published in SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.02287

zbMATH Keywords

\(M\)-convexityendowed assignment valuationGross substitutematroidmatroid-based valuationOXS

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Combinatorial aspects of tropical varieties (14T15) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Discrete geometry (52C99) Applications of statistics to economics (62P20) Auctions, bargaining, bidding and selling, and other market models (91B26) Matching models (91B68)

Abstract: 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 $nleq3$ and fails for all $ngeq4$. In particular, the set of gross substitutes valuations on $ngeq4$ 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.

Recommendations

• Multiple Exchange Property for M^♮-Concave Functions and Valuated Matroids
• Market pricing for matroid rank valuations
• Valuated matroids
• Geometry of gross substitutes valuations
• On the construction of substitutes

Cites work

• \(M\)-convex function on generalized polymatroid
• A Note on Kelso and Crawford's Gross Substitutes Condition
• BINARY MATROID SUMS
• Chow quotients of Grassmannian I
• Combinatorial auctions with decreasing marginal utilities
• Combinatorial geometries, convex polyhedra, and Schubert cells
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Competitive equilibrium in an exchange economy with indivisibilities
• Decomposition of binary matroids
• Designing matching mechanisms under constraints: an approach from discrete convex analysis
• Discrete Convex Analysis
• Discrete convexity and equilibria in economies with indivisible goods and money
• Geometry of Chow quotients of Grassmannians
• Gross substitutability: an algorithmic survey
• Gross substitutes and endowed assignment valuations
• GROSS SUBSTITUTES CONDITION AND DISCRETE CONCAVITY FOR MULTI-UNIT VALUATIONS: A SURVEY
• Gross substitution, discrete convexity, and submodularity
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 4191653 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Job Matching, Coalition Formation, and Gross Substitutes
• Matroid enumeration for incidence geometry
• On the construction of substitutes
• ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
• On the sum of matroids
• Product-mix auctions and tropical geometry
• Recent developments in discrete convex analysis
• Submodular functions and independence structures
• Submodular functions and optimization.
• Triangulations. Structures for algorithms and applications
• Tropical Linear Spaces
• Understanding preferences: ``demand types, and the existence of equilibrium with indivisibilities
• Valuated matroids: A new look at the greedy algorithm
• Verifying gross substitutability.
• Walrasian equilibrium with gross substitutes
• Walrasian's characterization and a universal ascending auction

Cited in

(3)

• Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices
• The polyhedral geometry of truthful auctions
• On complete classes of valuated matroids

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: The finite matroid-based valuation conjecture is false

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4959128)