The fashion game: Network extension of Matching Pennies

It is impossible, in general, to extend an asymmetric two-player game to networks, because there must be two populations, the row one and the column one, but we do not know how to define inner-population interactions. This is not the case for Matching Pennies, as we can interpret the row player as a conformist, who prefers to coordinate her opponent's action, while the column player can be interpreted as a rebel, who likes to anti-coordinate. Therefore we can naturally define the interaction between two conformists as the coordination game, and that between two rebels as the anti-coordination game. It turns out that the above network extension of Matching Pennies can be used to investigate the phenomenon of fashion, and thus it is named the fashion game. The fashion game possesses an obvious mixed Nash equilibrium, yet we are especially interested in pure Nash equilibrium (PNE for short), whose existence cannot be guaranteed. In this paper, we focus on the PNE testing problem, namely given an instance of the fashion game, answer whether it possesses a PNE or not. Our first result is on the negative side: PNE testing, in general, is hard. For the PNE testing problem restricted to several special structures, i.e. lines, rings, complete graphs and trees, either a simple characterization or an efficient algorithm is provided.