  A popular approach for addressing uncertainty in variational inequality
problems is by solving the expected residual minimization (ERM) problem. This
avenue necessitates distributional information associated with the uncertainty
and requires minimizing nonconvex expectation-valued functions. We consider a
distinctly different approach in the context of uncertain linear
complementarity problems with a view towards obtaining robust solutions.
Specifically, we define a robust solution to a complementarity problem as one
that minimizes the worst-case of the gap function. In what we believe is
amongst the first efforts to comprehensively address such problems in a
distribution-free environment, we show that under specified assumptions on the
uncertainty sets, the robust solutions to uncertain monotone linear
complementarity problem can be tractably obtained through the solution of a
single convex program. We also define uncertainty sets that ensure that robust
solutions to non-monotone generalizations can also be obtained by solving
convex programs. More generally, robust counterparts of uncertain non-monotone
LCPs are proven to be low-dimensional nonconvex quadratically constrained
quadratic programs. We show that these problems may be globally resolved by
customizing an existing branching scheme. We further extend the tractability
results to include uncertain affine variational inequality problems defined
over uncertain polyhedral sets as well as to hierarchical regimes captured by
mathematical programs with uncertain complementarity constraints. Preliminary
numerics on uncertain linear complementarity and traffic equilibrium problems
suggest that the presented avenues hold promise.
