Two-stage quadratic games under uncertainty and their solution by progressive hedging algorithms
A model of a two-stage N-person noncooperative game under uncertainty is studied, in which at the first stage each player solves a quadratic program parameterized by other players’ decisions and then at the second stage the player solves a recourse quadratic program parameterized by the realization...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Language: | English |
| Published: |
SIAM PUBLICATIONS
2019
|
| Subjects: | |
| Online Access: | http://purl.org/au-research/grants/arc/DP160102819 http://hdl.handle.net/20.500.11937/91438 |
| _version_ | 1848765520707321856 |
|---|---|
| author | Zhang, M. Sun, Jie Xu, Honglei |
| author_facet | Zhang, M. Sun, Jie Xu, Honglei |
| author_sort | Zhang, M. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | A model of a two-stage N-person noncooperative game under uncertainty is studied, in which at the first stage each player solves a quadratic program parameterized by other players’ decisions and then at the second stage the player solves a recourse quadratic program parameterized by the realization of a random vector, the second-stage decisions of other players, and the first-stage decisions of all players. The problem of finding a Nash equilibrium of this game is shown to be equivalent to a stochastic linear complementarity problem. A linearly convergent progressive hedging algorithm is proposed for finding a Nash equilibrium if the resulting complementarity problem is monotone. For the nonmonotone case, it is shown that, as long as the complementarity problem satisfies an additional elicitability condition, the progressive hedging algorithm can be modified to find a local Nash equilibrium at a linear rate. The elicitability condition is reminiscent of the sufficient second-order optimality condition in nonlinear programming. Various numerical experiments indicate that the progressive hedging algorithms are efficient for mid-sized problems. In particular, the numerical results include a comparison with the best response method that is commonly adopted in the literature. |
| first_indexed | 2025-11-14T11:36:34Z |
| format | Journal Article |
| id | curtin-20.500.11937-91438 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T11:36:34Z |
| publishDate | 2019 |
| publisher | SIAM PUBLICATIONS |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-914382024-04-11T03:36:33Z Two-stage quadratic games under uncertainty and their solution by progressive hedging algorithms Zhang, M. Sun, Jie Xu, Honglei Science & Technology Physical Sciences Mathematics, Applied Mathematics multistage noncooperative game under uncertainty progressive hedging algorithm stochastic linear complementarity problem stochastic variational inequality A model of a two-stage N-person noncooperative game under uncertainty is studied, in which at the first stage each player solves a quadratic program parameterized by other players’ decisions and then at the second stage the player solves a recourse quadratic program parameterized by the realization of a random vector, the second-stage decisions of other players, and the first-stage decisions of all players. The problem of finding a Nash equilibrium of this game is shown to be equivalent to a stochastic linear complementarity problem. A linearly convergent progressive hedging algorithm is proposed for finding a Nash equilibrium if the resulting complementarity problem is monotone. For the nonmonotone case, it is shown that, as long as the complementarity problem satisfies an additional elicitability condition, the progressive hedging algorithm can be modified to find a local Nash equilibrium at a linear rate. The elicitability condition is reminiscent of the sufficient second-order optimality condition in nonlinear programming. Various numerical experiments indicate that the progressive hedging algorithms are efficient for mid-sized problems. In particular, the numerical results include a comparison with the best response method that is commonly adopted in the literature. 2019 Journal Article http://hdl.handle.net/20.500.11937/91438 10.1137/17M1151067 English http://purl.org/au-research/grants/arc/DP160102819 SIAM PUBLICATIONS fulltext |
| spellingShingle | Science & Technology Physical Sciences Mathematics, Applied Mathematics multistage noncooperative game under uncertainty progressive hedging algorithm stochastic linear complementarity problem stochastic variational inequality Zhang, M. Sun, Jie Xu, Honglei Two-stage quadratic games under uncertainty and their solution by progressive hedging algorithms |
| title | Two-stage quadratic games under uncertainty and their solution by progressive hedging algorithms |
| title_full | Two-stage quadratic games under uncertainty and their solution by progressive hedging algorithms |
| title_fullStr | Two-stage quadratic games under uncertainty and their solution by progressive hedging algorithms |
| title_full_unstemmed | Two-stage quadratic games under uncertainty and their solution by progressive hedging algorithms |
| title_short | Two-stage quadratic games under uncertainty and their solution by progressive hedging algorithms |
| title_sort | two-stage quadratic games under uncertainty and their solution by progressive hedging algorithms |
| topic | Science & Technology Physical Sciences Mathematics, Applied Mathematics multistage noncooperative game under uncertainty progressive hedging algorithm stochastic linear complementarity problem stochastic variational inequality |
| url | http://purl.org/au-research/grants/arc/DP160102819 http://hdl.handle.net/20.500.11937/91438 |