Ostrovsky and Paes Leme's matroid-based valuation conjecture

Let v:2GRv:2^{\mathcal G}\to\mathbb R be a valuation, and define the merging operation (or convolution) of valuations v1,v2v_1,v_2 by

v(S)=maxTSv1(T)+v2(ST)SG.v^*(S)=\max_{T\subseteq S} v_1(T)+v_2(S\setminus T)\quad\forall S\subseteq\mathcal G.

An MM^\natural-concave valuation is a valuation in the discrete-concavity class denoted by MM^\natural-concavity, and a weighted matroid rank function is a valuation of that form. Ostrovsky and Paes Leme's matroid-based valuation conjecture. Every MM^\natural-concave valuation arises by the repeated application of endowment and merging operations starting from weighted matroid rank functions. The source identifies this as a stronger conjecture previously posed by Ostrovsky and Paes Leme and states that it is still open; merging preserves MM^\natural-concavity.

Sources & referencesView supporting material

Primary source

Jugal Garg, Edin Husic and Laszlo A. Vegh, “Approximating Nash Social Welfare under Rado Valuations”, arXiv:2009.14793 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.