  This paper introduces algorithm instance games (AIGs) as a conceptual
classification applying to games in which outcomes are resolved from joint
strategies algorithmically. For such games, a fundamental question asks: How do
the details of the algorithm's description influence agents' strategic
behavior?
  We analyze two versions of an AIG based on the set-cover optimization
problem. In these games, joint strategies correspond to instances of the
set-cover problem, with each subset (of a given universe of elements)
representing the strategy of a single agent. Outcomes are covers computed from
the joint strategies by a set-cover algorithm. In one variant of this game,
outcomes are computed by a deterministic greedy algorithm, and the other
variant utilizes a non-deterministic form of the greedy algorithm. We
characterize Nash equilibrium strategies for both versions of the game, finding
that agents' strategies can vary considerably between the two settings. In
particular, we find that the version of the game based on the deterministic
algorithm only admits Nash equilibrium in which agents choose strategies (i.e.,
subsets) containing at most one element, with no two agents picking the same
element. On the other hand, in the version of the game based on the
non-deterministic algorithm, Nash equilibrium strategies can include agents
with zero, one, or every element, and the same element can appear in the
strategies of multiple agents.
