Convex Program Duality, Fisher Markets, and Nash Social Welfare
Convex Program Duality, Fisher Markets, and Nash Social Welfare
复制标题
凸规划二元性、渔业市场和纳什社会福利
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Sadra Yazdanbod
中科院分区：
文献类型：
--
作者：
R. Cole;Nikhil R. Devanur;Vasilis Gkatzelis;K. Jain;Tung Mai;V. Vazirani;Sadra Yazdanbod
我们研究Fisher Markets和最大化NASH社会福利（NSW）的问题，尤其显示了几个紧密相关的新结果，我们获得了一个新的整数计划，用于新南威尔士州的最大化问题对比，自然整数程序具有无限的完整性差距。 [7]是2e/e≈2.89我们是通过在先前已知的不同结果之间建立联系而获得的，并且它们有助于揭示其数学基础，我们在艾森伯格和盖尔的凸面计划和shmyrev的凸面计划之间形成了正式联系这两个程序都通过在Shyrev的计划中添加适当的限制来捕捉线性渔民的平衡，我们获得了一个凸出的凸面程序，该计划捕获了在新南威尔士州最大化问题的情况下，捕获了由[7]定义的。我们使用上述新南威尔士州的整数程序的约束是我们使用的基本工具。程序几乎与线性程序双重性相提并论。
We study Fisher markets and the problem of maximizing the Nash social welfare (NSW), and show several closely related new results. In particular, we obtain: A new integer program for the NSW maximization problem whose fractional relaxation has a bounded integrality gap. In contrast, the natural integer program has an unbounded integrality gap. An improved, and tight, factor 2 analysis of the algorithm of [7]; in turn showing that the integrality gap of the above relaxation is at most 2. The approximation factor shown by [7] was 2e 1/e ≈ 2.89. A lower bound of e 1/e ≈ 1.44 on the integrality gap of this relaxation. New convex programs for natural generalizations of linear Fisher markets and proofs that these markets admit rational equilibria. These results were obtained by establishing connections between previously known disparate results, and they help uncover their mathematical underpinnings. We show a formal connection between the convex programs of Eisenberg and Gale and that of Shmyrev, namely that their duals are equivalent up to a change of variables. Both programs capture equilibria of linear Fisher markets. By adding suitable constraints to Shmyrev’s program, we obtain a convex program that captures equilibria of the spendingrestricted market model defined by [7] in the context of the NSW maximization problem. Further, adding certain integral constraints to this program we get the integer program for the NSW mentioned above. The basic tool we use is convex programming duality. In the special case of convex programs with linear constraints (but convex objectives), we show a particularly simple way of obtaining dual programs, putting it almost at par with linear program duality. This simple way of finding duals has been used subsequently for many other applications.