Ostrovsky and Paes Leme's matroid-based valuation conjecture
Ostrovsky and Paes Leme's matroid-based valuation conjecture
Let be a valuation, and define the merging operation (or convolution) of valuations by
An -concave valuation is a valuation in the discrete-concavity class denoted by -concavity, and a weighted matroid rank function is a valuation of that form. Ostrovsky and Paes Leme's matroid-based valuation conjecture. Every -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 -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.