Lune

SODA2022Top-tier venue

On complete classes of valuated matroids

Edin Husic, Georg Loho, Ben Smith, László A. Végh

Abstract

We characterize a rich class of valuated matroids, called R-minor valuated matroids that includes the indicator functions of matroids, and is closed under operations such as taking minors, duality, and induction by network. We exhibit a family of valuated matroids that are not R-minor based on sparse paving matroids.

Valuated matroids are inherently related to gross substitute valuations in mathematical economics. By the same token we refute the Matroid Based Valuation Conjecture by Ostrovsky and Paes Leme (Theoretical Economics 2015) asserting that every gross substitute valuation arises from weighted matroid rank functions by repeated applications of merge and endowment operations. Our result also has implications in the context of Lorentzian polynomials: it reveals the limitations of known construction operations.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on1

  1. Approximating Nash social welfare under rado valuationsJugal Garg, Edin Husic, László A. VéghSTOC 2021 · 6 citations

Related papers

  1. Interaction Between Skew-representability, Tensor Products, Extension Properties, and Rank InequalitiesKristóf Bérczi, Boglárka Gehér, András Imolay, László Lovász et al.SODA 2026
  2. Weighted Envy-Freeness for Submodular ValuationsLuisa Montanari, Ulrike Schmidt-Kraepelin, Warut Suksompong, Nicholas TehAAAI 2024 · 20 citations
  3. Matroid Products via Submodular CouplingKristóf Bérczi, Boglárka Gehér, András Imolay, László Lovász et al.STOC 2025 · 1 citation
  4. Matroids are EquitableHannaneh Akrami, Roshan Raj, László A. VéghSODA 2026
  5. Representative set statements for delta-matroids and the Mader delta-matroidMagnus WahlströmSODA 2024 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines