We show that the most cost-efficient subset problem for linear programming games is NP-hard, and in fact inapproximable within a constant factor in polynomial time, unless P = NP. This in turn implies that computing the prices output by an egalitarian mechanism and computing a cost allocation in the equal split-off set for linear programming … Read more
In the paper, we propose a bilevel direct search method for solving a type of leader-follower problems with each decision maker’s objective being a “black-box” function. First, we give a description for a leader-follower optimization problem. Then, we investigate a bilevel direct search method including two algorithms for combinatorially solving the upper and lower level … Read more
It’s shown that a number of variational problems can be cast as finding the maxinf-points (or minsup-points) of bivariate functions, coveniently abbreviated to bifunctions. These variational problems include: linear and nonlinear complementarity problems, fixed points, variational inequalities, inclusions, non-cooperative games, Walras and Nash equilibrium problems. One can then appeal to the theory of lopsided convergence … Read more
In this work, we present new insights into the dynamic stability of electricity markets. In particular, we discuss how short forecast horizons, incomplete gaming, and physical ramping constraints can give rise to stability issues. Using basic concepts of market efficiency, Lyapunov stability, and predictive control, we construct a new stabilizing market design. A numerical case … Read more
We investigate cost-sharing mechanisms for scheduling cost-sharing games. We assume that the demand is general—that is, each player can be allocated one of several levels of service. We show how to design mechanisms for these games that are weakly group strategyproof, approximately budget-balanced, and approximately efficient, using approximation algorithms for the underlying scheduling problems. We … Read more
We address an optimization problem in which two agents, each with a set of weighted items, compete in order to minimize the total weight of their solution sets. The latter are built according to a sequential game consisting in a fixed number of rounds. In every round each agent submits one item that may be … Read more
We present a game-theoretical dynamic model for competitive electricity markets.We demonstrate that the model can be used to systematically analyze the effects of ramp constraints, initial conditions, dynamic disturbances, forecast horizon, bidding frequency, and some other factors on the price signals.We illustrate the capabilities of the model using a numerical case study Article Download View … Read more
This paper presents a two stage stochastic equilibrium problem with equilibrium constraints(SEPEC) model. Some source problems which motivate the model are discussed. Monte Carlo sampling method is applied to solve the SEPEC. The convergence analysis on the statistical estimators of Nash equilibria and Nash stationary points are presented. Article Download View Two stage stochastic equilibrium … Read more
We study the approximation of the least core value and the least core of supermodular cost cooperative games. We provide a framework for approximation based on oracles that approximately determine maximally violated constraints. This framework yields a (3 + \epsilon)-approximation algorithm for computing the least core value of supermodular cost cooperative games, and a polynomial-time … Read more
In 1951, Dantzig showed the equivalence of linear programming and two-person zero-sum games. However, in the description of his reduction from linear programming to zero-sum games, he noted that there was one case in which his reduction does not work. This also led to incomplete proofs of the relationship between the Minmax Theorem of game … Read more