We demonstrate the use of linear programming techniques in the analysis of mechanism design problems. We use these techniques to analyze the extent to which a first-price auction is robust to collusion when, contrary to some prior literature on collusion at first-price auctions, the cartel cannot prevent its members from bidding at the auction. In … Read more
By introducing some redundant Klee-Minty constructions, we have previously shown that the central path may visit every vertex of the Klee-Minty cube having $2^n-2$ “sharp” turns in dimension $n$. In all of the previous constructions, the maximum of the distances of the redundant constraints to the corresponding facets is an exponential number of the dimension … Read more
Abstract: After developing necessary background theory, the original primal and dual are specified, and the invariant primal and dual LP’s are defined. Pairs of linear mappings are defined which establish an effectively one-to-one correspondences between solutions to the original and invariant problems. The invariant problems are recast as a fixed-point problem and precise solution conditions … Read more
In this paper we present the convergence analysis of the inexact infeasible path-following(IIPF) interior point algorithm. In this algorithm the preconditioned conjugate gradient method is used to solve the reduced KKT system (the augmented system). The augmented system is preconditioned by using a block triangular matrix. The KKT system is solved approximately. Therefore, it becomes … Read more
The transportation paradox is related to the classical transportation problem. For certain instances of this problem an increase in the amount of goods to be transported may lead to a decrease in the optimal total transportation cost. Even though the paradox has been known since the early days of linear programming, it has got very … Read more
Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm^2) operations. When n>>m it is often the case that at … Read more
We propose a new gradient based scheme to approximate Nash equilibria of large sequential two-player, zero-sum games. The algorithm uses modern smoothing techniques for saddle-point problems tailored specifically for the polytopes used in the Nash equilibrium problem. CitationWorking Paper, Tepper School of Business, Carnegie Mellon UniversityArticleDownload View PDF
In this paper we present a scaling-invariant interior-point predictor-corrector type algorithm for linear programming (LP) whose iteration-complexity is polynomially bounded by the dimension and the logarithm of a certain condition number of the LP constraint matrix. At the predictor stage, the algorithm either takes the step along the standard affine scaling direction or a new … Read more
We consider the problem of finding an $\epsilon-$optimal solution of a standard linear program with real data, i.e., of finding a feasible point at which the objective function value differs by at most $\epsilon$ from the optimal value. In the worst-case scenario the best complexity result to date guarantees that such a point is obtained … Read more
In this paper we devise a new version of primal simplex algorithms in which the classical iteration is decomposed two basic operations: the move and the pivot. The move operation decreases the primal objective value and the pivot operation increases the dual objective. We define the condition number of the pivot operation and present a … Read more