Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP

Christoph Grüne, Berit Johannes, James B. Orlin +1

Many natural optimization problems derived from $\mathsf{NP}$ admit bilevel and multilevel extensions in which decisions are made sequentially by multiple players with conflicting objec…