Nash welfare, valuated matroids, and gross substitutes

Husić, Edin (2021) Nash welfare, valuated matroids, and gross substitutes. PhD thesis, London School of Economics and Political Science.

Text - Submitted Version Download (1MB)

Abstract

We study computational aspects of equilibria and fair division problems with a focus on demand and valuation functions that satisfy the (weak) gross substitutes property. We study the Arrow-Debreu exchange market model with divisible goods where agents’ demands satisfy the weak gross substitutes (WGS) property. We give an auction algorithm that obtains an approximate market equilibrium for WGS demands. Previously, such algorithms were known only for restricted classes of WGS demands. We also derive the implications of our technique for spending-restricted market equilibrium for budget-separable piecewise linear concave (budget-SPLC) utilities. Spending-restricted equilibrium was introduced as a continuous relaxation of the Nash SocialWelfare (NSW) problem. Next, we present the first polynomial-time constant-factor approximation algorithm for the NSW problem under Rado valuations. Rado valuations form a general class of valuation functions that arise from maximum cost independent matching problems. They include as special cases assignment (OXS) valuations and weighted matroid rank functions. Our approach also gives the first polynomial-time constant-factor approximation algorithm for the asymmetric NSW problem under Rado valuations, provided that the maximum ratio between the weights is bounded by a constant. We examine the Matroid Based Valuation (MBV) conjecture by Ostrovsky and Paes Leme (Theoretical Economics 2015). It asserts that every (discrete) gross substitute valuation is a matroid based valuation—a valuation obtained from weighted matroid rank functions by repeated applications of merge and endowment operations. Each matroid based valuation turns out to be an endowment of some Rado valuation. By introducing complete classes of valuated matroids, we exhibit a family of valuations that are gross substitutes but not endowed Rado valuations. This refutes the MBV conjecture. The family is defined via sparse paving matroids.

Item Type:	Thesis (PhD)
Additional Information:	© 2021 Edin Husić
Library of Congress subject classification:	Q Science > QA Mathematics
Sets:	Departments > Mathematics
Supervisor:	Végh, László A.
URI:	http://etheses.lse.ac.uk/id/eprint/4335

Actions (login required)

Record administration - authorised staff only