789. Geometry of linear bilevel programming with uncertain lower-level costs
Invited abstract in session HD-22: Applications of Game Theory in Operations Management , cluster Game Theory and Operations Management.
Thursday, 14:15-15:45Room: FENH202
Authors (first author is the speaker)
| 1. | David Salas
|
| Instituto de Ciencias de la Ingeniería, Universidad de O'Higgins | |
| 2. | Gonzalo Munoz
|
| Universidad de O'Higgins | |
| 3. | Anton Svensson
|
| Instituto de Ciencias de la Ingeniería, Universidad de O'Higgins |
Abstract
In this talk, we will revise linear bilevel programming problems, whose lower-level objective is given by a random cost vector with known distribution. The cost function is interpreted as the belief of the leader over the uncertain follower's decision process, following the Bayesian approach for bilevel games. Where the distribution is nonatomic, we pose the problem of the leader using vertex-supported beliefs. Under suitable assumptions, this formulation turns out to be piecewise affine over the chamber complex of the feasible set of the high point relaxation.
Two algorithmic approaches solve general problems enjoying this property. The first one is based on enumerating the vertices of the chamber complex. The second one is a Monte-Carlo approximation scheme with randomly drawn points of the domain located, with probability 1, in the interior of full-dimensional chambers; the problem (restricted to this chamber) can be reduced to a linear program.
Keywords
- Bilevel programming
- Stochastic Optimization
- Game Theory
Status: accepted
Back to the list of papers