S-Convexity and Market Equilibrium

Description

Resource allocation in a fair and efficient manner is a fundamental problem in manyfields including economics, operations research, and theoretical computer science. Competitiveequilibrium (CE), an important concept in economics, is often used as a benchmarkof efficiency and fairness for allocating goods. The efficiency of a CE is guaranteedby the well-known first welfare theorem, and the popular notion of competitive equilibriumwith equal incomes (CEEI) is shown to be envy-free (a central fairness notion ineconomics). Due to these salient properties, the computation of CE in various marketshas attracted extensive research interest in economics and theoretical computer science.Among the literature, the compelling concept of gross substitutability (GS) has beenshown to be crucial in the design of efficient and practical algorithms for CE. A utilityfunction is said to satisfy GS if as the prices of some goods increase and the others remainunchanged, then the demand of each good with an unchanged price does not decrease.Although the concept of GS is important, it has been difficult to identify utility functionssatisfying it. Maximum Nash welfare (MNW) allocation is another benchmark ofefficiency and fairness and is closely related to CE. It is defined as the allocation of multipledifferentiated goods that maximizes the product of the valuation functions of all theagents. Although MNW allocation enjoys “unreasonable” fairness, it is notoriously hardto solve even under simple linear valuation functions. In this project, we propose to employ discrete convex analysis to characterize GSand investigate its applications in the analysis of simple and practical market dynamicsand MNW problems. In particular, we propose to use S-concavity, a notion of discreteconvexity, to provide a complete characterization of GS in auction markets of divisiblegoods and derive monotonicity properties of a natural price adjustment dynamics as wellas provide a characterization of tractable MNW problems using M-concavity (anothernotation of discrete convexity). If successful, the research output of this project willsignificantly contribute to the literature by providing a fundamental understanding of therole of GS in the design of algorithms for CE and MNW problems from a discrete convexanalysis perspective, and the insights derived from our project can guide decision-makersto adjust prices in their markets to achieve CE and to achieve efficient and fair allocationsof resources.