  In this work we study a special minimax problem where there are linear
constraints that couple both the minimization and maximization decision
variables. The problem is a generalization of the traditional saddle point
problem (which does not have the coupling constraint), and it finds
applications in wireless communication, game theory, transportation, just to
name a few. We show that the considered problem is challenging, in the sense
that it violates the classical max-min inequality, and that it is NP-hard even
under very strong assumptions (e.g., when the objective is strongly
convex-strongly concave). We then develop a duality theory for it, and analyze
conditions under which the duality gap becomes zero. Finally, we study a class
of stationary solutions defined based on the dual problem, and evaluate their
practical performance in an application on adversarial attacks on network flow
problems.
