Incidence Bimatrix Games

We solve a natural bimatrix game related to graphs. We consider a finite directed graph $G=(V,E),$ where the strategy set of Player I is the set of vertices $V$ and that of Player II is the set of edges $E.$ There are two sets of positive weights ${\{α_e\}}_{e\in E}$ and ${\{β_e\}}_{e\in E}.$ If Player I chooses a vertex $v$ and Player II chooses an edge $e,$ then the payoff to both players is zero if $v$ and $e$ are not incident. If $e$ originates from $v,$ then Player I obtains $α_e$ and Player II obtains $-β_e.$ If $e$ terminates at $v,$ then Player I obtains $-α_e$ and Player II obtains $β_e.$ For this game the payoff matrices are weighted incidence matrices of the graph $G.$ We show that when the graph is acyclic, Player I has a unique strategy in any equilibrium. At this strategy, every vertex is chosen with a probability that is proportional to the maximum length over all directed paths originating from that vertex. Defining the path matrix of the graph, it is shown that the set of all equilibrium strategies of Player II is the convex hull of the column vectors of the path matrix. This work extends earlier results of Bapat and Tijs (1997) for zero-sum games.