In this paper we present an algorithmic framework for solving a class of combinatorial optimization problems on graphs with bounded pathwidth. The problems are NP-hard in general, but solvable in linear time on this type of graphs. The problems are relevant for assessing network reliability and improving the network’s performance and fault tolerance. The main … Read more
We focus on a permutation betting market under parimutuel call auction model where traders bet on the final ranking of n candidates. We present a Proportional Betting mechanism for this market. Our mechanism allows the traders to bet on any subset of the n x n ‘candidate-rank’ pairs, and rewards them proportionally to the number … Read more
We prove several inequalities on the determinants of sublattices in LLL-reduced bases. They generalize the fundamental inequalities of Lenstra, Lenstra, and Lovasz on the length of the shortest vector, and show that LLL-reduction finds not only a short vector, but also sublattices with small determinants. We also prove new inequalities on the product of the … Read more
We propose an iterated version of Nesterov’s first-order smoothing method for the two-person zero-sum game equilibrium problem $$\min_{x\in Q_1} \max_{y\in Q_2} \ip{x}{Ay} = \max_{y\in Q_2} \min_{x\in Q_1} \ip{x}{Ay}.$$ This formulation applies to matrix games as well as sequential games. Our new algorithmic scheme computes an $\epsilon$-equilibrium to this min-max problem in $\Oh(\kappa(A) \ln(1/\epsilon))$ first-order iterations, … Read more
We develop first-order smoothing techniques for saddle-point problems that arise in the Nash equilibria computation of sequential games. The crux of our work is a construction of suitable prox-functions for a certain class of polytopes that encode the sequential nature of the games. An implementation based on our smoothing techniques computes approximate Nash equilibria for … Read more
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
In this paper, we propose a new recombination operator and test its performance in the context of the multiobjective 0/1 knapsack problem (MOKP). The proposed recombination operator generates only one offspring solution from a selected pair of parents according to the two following stages. In the first stage, called genetic shared-information stage or similarity-preserving stage, … Read more
We describe a dual approach to stochastic dynamic programming: we relax the constraint that the chosen policy must be temporally feasible and impose a penalty that punishes violations of temporal feasibility. We describe the theory underlying this dual approach and demonstrate its use in dynamic programming models related to inventory control, option pricing, and oil … Read more
We propose an extension of Newton’s Method for unconstrained multiobjective optimization (multicriteria optimization). The method does not scalarize the original vector optimization problem, i.e. we do not make use of any of the classical techniques that transform a multiobjective problem into a family of standard optimization problems. Neither ordering information nor weighting factors for the … Read more
Conventional Lagrangean preprocessing for the network Weight Constrained Shortest Path Problem (WCSPP calculates lower bounds on the cost of using each node and edge in a feasible path using a single optimal Lagrange multiplier for the relaxation of the WCSPP. These lower bounds are used in conjunction with an upper bound to eliminate nodes and … Read more