SGER: Linear Optimization vs. Nonlinear Equilibrium

点击翻译按钮获取中文摘要

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.