This paper presents a Nash equilibrium model where the underlying objective functions involve uncertainty and nonsmoothness. The well known sample average approximation method is applied to solve the problem and the first order equilibrium conditions are characterized in terms of Clarke generalized gradients. Under some moderate conditions, it is shown that with probability one, a … Read more
We describe a rudimentary branch-and-cut algorithm for solving integer bilevel linear programs that extends existing techniques for standard integer linear programs to this very challenging computational setting. The algorithm improves on the branch-and-bound algorithm of Moore and Bard in that it uses cutting plane techniques to produce improved bounds, does not require specialized branching strategies, … Read more
We study selfish routing in ring networks with respect to minimizing the maximum latency. Our main result is an establishement of constant bounds on the price of stability (PoS) for routing unsplittable flows with linear latency. We show that the PoS is at most 6.83, which reduces to 4:57 when the linear latency functions are … 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 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, oligopolistic competition in a centralized power market is characterized by a multi-leader single-follower game, and formulated as a nonlinear programming (NLP) problem. An AC network is used to represent the transmission system and is modeled using rectangular coordinates. The follower is composed of a set of competitive suppliers, demands, and the system … Read more
An affine supply function equilibrium (SFE) approach is used to discuss voltage constraints and reactive power issues in the modeling of strategic behavior. Generation companies (GenCos) can choose their bid parameters with no restrictions for both energy and spinning reserves. The strategic behavior of generators is formulated as a multi-leader single-follower game. Each GenCo is … Read more
In this paper we formulate the fuzzy bilevel programming problem and describe one possible approach for formulating a crisp optimization problem being attached to it. Due to the nature of fuzzy bilevel programming this is a crisp bilevel programming problem. We compare our approach with one using multicriterial optimization and show, that both approaches are … Read more