  In many multiagent environments, a designer has some, but limited control
over the game being played. In this paper, we formalize this by considering
incompletely specified games, in which some entries of the payoff matrices can
be chosen from a specified set. We show that it is NP-hard for the designer to
make these choices optimally, even in zero-sum games. In fact, it is already
intractable to decide whether a given action is (potentially or necessarily)
played in equilibrium. We also consider incompletely specified symmetric games
in which all completions are required to be symmetric. Here, hardness holds
even in weak tournament games (symmetric zero-sum games whose entries are all
-1, 0, or 1) and in tournament games (symmetric zero-sum games whose
non-diagonal entries are all -1 or 1). The latter result settles the complexity
of the possible and necessary winner problems for a social-choice-theoretic
solution concept known as the bipartisan set. We finally give a mixed-integer
linear programming formulation for weak tournament games and evaluate it
experimentally.
