Towards a deeper understanding of cooperative equilibrium: characterization and complexity
Nash equilibrium (NE) assumes that players always make a best response. However, this is not always true; sometimes people cooperate even it is not a best response to do so. For example, in the Prisoner's Dilemma, people often cooperate. We consider two solution concepts that were introduced recently that try to capture such cooperation in two-player games: perfect cooperative equilibrium (PCE) (and an extension called maximum PCE (M-PCE)) [8] and the coco value [11]. We show that, despite their definitions being quite different, these notions are closely related, both in terms of axiomatization and algebraic characterization. We also consider the problem of computing how well players do when they cooperate according to these solution concepts, and show that in both cases in polynomial time. In the case of the coco value, this follows easily from the definition; in the case of the corresponding M-PCE value, it follows from a theorem showing that bilinear programming for a class of 2 X 2 matrices is in constant time, a result that may be of independent interest.