Generating Gross Substitutes Valuations from Matroid Ranks

Definitions and mathematical statement

For a finite set $E$, write $2^E$ for its power set and $[n]=\{1,\ldots,n\}$. Under the usual real-valued set-function convention, a valuation is a function $v:2^E\to{\mathbb{R}}$. For prices $p\in{\mathbb{R}}^E$, define the demand correspondence by \[ D_v(p)=\operatorname*{arg\,max}_{S\subseteq E}\left(v(S)-\sum_{i\in S}p_i\right). \] The gross-substitutes condition is that, whenever $p,q\in{\mathbb{R}}^E$ satisfy $p_i\le q_i$ for every $i\in E$, each $S\in D_v(p)$ admits some $T\in D_v(q)$ such that \[ \{i\in S:p_i=q_i\}\subseteq T. \] This gives a standard interpretation of gross substitutes; the supplied record does not specify the valuation codomain, normalization, monotonicity assumptions, or admissible price domain.

A matroid on $E$ is a pair $M=(E,\mathcal I)$, where $\mathcal I\subseteq2^E$ contains $\varnothing$, is closed under taking subsets, and satisfies the augmentation axiom: if $I,J\in\mathcal I$ and $|I|<|J|$, then $I\cup\{j\}\in\mathcal I$ for some $j\in J\setminus I$. Given weights $w_i$, its weighted rank valuation is \[ r_{M,w}(S)=\max\left\{\sum_{i\in I}w_i:I\subseteq S,\ I\in\mathcal I\right\},\qquad S\subseteq E. \] Nonnegative real weights are a standard convention for this terminology, but the permitted weights are not stated in the supplied record.

Source question. For every number $n$ of good types, does there exist a finite integer $m\ge n$, depending only on $n$, such that every gross-substitutes valuation on $[n]$ can be generated from weighted matroid-rank valuations on $[m]$? The order of quantifiers requires a single bound $m$ for all valuations on $[n]$; the generating matroids, weights, and construction may depend on the valuation.

Unresolved formulation. The record does not define "generated," list the permitted operations, or explain how a construction on $[m]$ produces a valuation on $[n]$. Consequently, the generation relation cannot be specified from the supplied evidence, and this draft does not substitute an assumed closure operation. The record also does not explicitly state whether zero good types are included. These points and the valuation conventions above require clarification before the question becomes a fully specified mathematical statement.

Short English statement

The question asks whether, for each number $n$ of goods, some finite bound $m\ge n$ suffices to construct every gross-substitutes valuation on those goods from weighted matroid ranks on $m$ elements. The bound must be uniform over valuations. The permitted construction operations and several valuation conventions are missing from the supplied record.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $30004213$, title "Generating Gross Substitutes Valuations from Matroid Ranks," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the proposed year is recorded as 2019.
• Supplied report citation: Geometric, Algebraic, and Topological Combinatorics (2020), Oberwolfach Reports, pp. 2395--2472, DOI 10.4171/owr/2019/39. https://doi.org/10.4171/owr/2019/39. The background describes Oberwolfach Reports as documenting workshops and their open-problem discussions.
• Supplied literature reference: "Tran, finite matroid-based valuation conjecture." https://doi.org/10.1137/19M1304295.
• Supplied literature reference: "Oberwolfach Report 39, gross substitutes." https://doi.org/10.4171/owr/2019/39.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem partially solved and attributes to Tran a disproof of the conjecture with $m=n$ for $n\ge4$, together with proofs of the cases $n\le3$; it says the existence of a finite $m$ for every $n$ remains open. This is supplied dated curation derived from the OWR record, not an independently verified assessment. The record explicitly requests independent verification of time-sensitive status and cited claims.
• The supplied statement status is corrected_verified; its accompanying explanation says that mathematical content was preserved while notation, typography, and sentence structure were repaired. This registry label does not establish independent mathematical or source verification of this draft.