  We study linear bilevel programming problems whose lower-level objective is
given by a random cost vector with known distribution. We consider the case
where this distribution is nonatomic, allowing to reformulate the problem of
the leader using the Bayesian approach in the sense of Salas and Svensson
(2023), with a decision-dependent distribution that concentrates on the
vertices of the feasible set of the follower's problem. We call this a
vertex-supported belief. We prove that this formulation is piecewise affine
over the so-called chamber complex of the feasible set of the high-point
relaxation. We propose two algorithmic approaches to solve general problems
enjoying this last property. The first one is based on enumerating the vertices
of the chamber complex. This approach is not scalable, but we present it as a
computational baseline and for its theoretical interest. The second one is a
Monte-Carlo approximation scheme based on the fact that randomly drawn points
of the domain lie, with probability 1, in the interior of full-dimensional
chambers, where the problem (restricted to this chamber) can be reduced to a
linear program. Finally, we evaluate these methods through computational
experiments showing both approaches' advantages and challenges.
