  We study the representability of sets that admit extended formulations using
mixed-integer bilevel programs. We show that feasible regions modeled by
continuous bilevel constraints (with no integer variables), complementarity
constraints, and polyhedral reverse convex constraints are all finite unions of
polyhedra. Conversely, any finite union of polyhedra can be represented using
any one of these three paradigms. We then prove that the feasible region of
bilevel problems with integer constraints exclusively in the upper level is a
finite union of sets representable by mixed-integer programs and vice versa.
Further, we prove that, up to topological closures, we do not get additional
modeling power by allowing integer variables in the lower level as well. To
establish the last statement, we prove that the family of sets that are finite
unions of mixed-integer representable sets forms an algebra of sets (up to
topological closures).
