SGER: Linear Optimization vs. Nonlinear Equilibrium

建议：ID：CCF-0836338标题：SGER：线性优化与非线性均衡PI：Polyak，Roman A.Inst：George Mason University摘要：通过考虑来自市场经济的更现实的场景，该建议正在考虑一种重新制定标准线性规划问题的创新想法。资源分配问题的标准线性规划公式假定商品的成本与生产水平无关。众所周知，实际情况并非如此。通过使成本成为生产的函数，PI用更一般的术语来表述问题。然而，在一些关于代价函数性质的自然但简单化的假设(描述起来有些技术性)下，问题的解的复杂性被证明低于标准线性规划问题解的最坏情况的复杂性。事实上，有迹象表明，在这个非标准公式中，PI可以得到O(n^2)解。这在某种意义上是自相矛盾的(更一般的问题有一个更简单的解！)，但显然不是这样，因为对于LP公式，可行集的几何是多面体，而在新的问题公式下，它是一个简单得多的区域。此外，新的提法与n人博弈理论有着密切的联系。

Proposal: ID: CCF - 0836338 Title: SGER: Linear Optimization vs. Nonlinear Equilibrium PI: Polyak, Roman A.Inst: George Mason University ABSTRACT:An innovative idea for reformulating the standard linear programming problem by taking into account more realistic scenarios from market economics is being considered in this proposal. The standard linear programming formulation of resource allocation problem assumes that the cost of a commodity is independent of the level of production. As one knows this is not the case in reality. By making the cost a function of the production, the PI formulates the problem in more general terms. However, under some natural but simplifying assumptions (which are somewhat technical to describe) on the nature of the cost function, the solution complexity of the problem turns out to be lower than the worst case complexity of the solution to the standard linear programming problem. In fact, there are indications that an O(n^2) solution can be obtained in this nonstandard formulation by the PI. This is paradoxical in some sense (that a more general problem has a simpler solution!), but apparently not so because for the LP formulation the geometry of the feasible set is a polytope, whereas its is a much simpler region under the new formulation of the problem. Also, the new formulation has close ties with the theory of n- person games.