
The discrete moment problem is a foundational problem in distributionfree
robust optimization, where the goal is to find a worstcase distribution that
satisfies a given set of moments. This paper studies the discrete moment
problems with additional "shape constraints" that guarantee the worst case
distribution is either logconcave or has an increasing failure rate. These
classes of shape constraints have not previously been studied in the
literature, in part due to their inherent nonconvexities. Nonetheless, these
classes of distributions are useful in practice. We characterize the structure
of optimal extreme point distributions by developing new results in reverse
convex optimization, a lesserknown tool previously employed in designing
global optimization algorithms. We are able to show, for example, that an
optimal extreme point solution to a moment problem with $m$ moments and
logconcave shape constraints is piecewise geometric with at most $m$ pieces.
Moreover, this structure allows us to design an exact algorithm for computing
optimal solutions in a lowdimensional space of parameters. Moreover, We
describe a computational approach to solving these lowdimensional problems,
including numerical results for a representative set of instances.

Finitedimensional linear programs satisfy strong duality (SD) and have the
"dual pricing" (DP) property. The (DP) property ensures that, given a
sufficiently small perturbation of the righthandside vector, there exists a
dual solution that correctly "prices" the perturbation by computing the exact
change in the optimal objective function value. These properties may fail in
semiinfinite linear programming where the constraint vector space is infinite
dimensional. Unlike the finitedimensional case, in semiinfinite linear
programs the constraint vector space is a modeling choice. We show that, for a
sufficiently restricted vector space, both (SD) and (DP) always hold, at the
cost of restricting the perturbations to that space. The main goal of the paper
is to extend this restricted space to the largest possible constraint space
where (SD) and (DP) hold. Once (SD) or (DP) fail for a given constraint space,
then these conditions fail for all larger constraint spaces. We give sufficient
conditions for when (SD) and (DP) hold in an extended constraint space. Our
results require the use of linear functionals that are singular or purely
finitely additive and thus not representable as finite support vectors. The key
to understanding these linear functionals is the extension of the
FourierMotzkin elimination procedure to semiinfinite linear programs.

We consider discrete bilevel optimization problems where the follower solves
an integer program with a fixed number of variables. Using recent results in
parametric integer programming, we present polynomial time algorithms for pure
and mixed integer bilevel problems. For the mixed integer case where the
leader's variables are continuous, our algorithm also detects whether the
infimum cost fails to be attained, a difficulty that has been identified but
not directly addressed in the literature. In this case it yields a ``better
than fully polynomial time'' approximation scheme with running time polynomial
in the logarithm of the relative precision. For the pure integer case where the
leader's variables are integer, and hence optimal solutions are guaranteed to
exist, we present two algorithms which run in polynomial time when the total
number of variables is fixed.

We explore the computational complexity of computing pure Nash equilibria for
a new class of strategic games called integer programming games with difference
of piecewise linear convex payoffs. Integer programming games are games where
players' action sets are integer points inside of polytopes. Using recent
results from the study of short rational generating functions for encoding sets
of integer points pioneered by Alexander Barvinok, we present efficient
algorithms for enumerating all pure Nash equilibria, and other computations of
interest, such as the pure price of anarchy, and pure threat point, when the
dimension and number of "convex" linear pieces in the payoff functions are
fixed. Sequential games where a leader is followed by competing followers (a
StackelbergNash setting) are also considered.