I have a problem in Game Theory that I'm even struggling to start solving. It's a homework thus I ask for a hint.
We have a bipartite graph $G=(A\cup B, E)$ and a game for vertices in A. Each vertex $a_i$ chooses one of the edges between itself and some vertex $b_j$ in $B$. The payoff it gets for choosing some strategy is the weight $v_{ij}$ that is associated with the chosen edge, unless there is another agent $a_k$ that chose $b_j$ and $v_{kj} > v_{ij}$. We assume there are no ties. The task is to show a bound on the Price of Anarchy.
My attempts get stuck at the beginning, when I'm trying to nicely express the payoff an agent gets if he/she deviates from Nash Equilibrium strategy to some other one (in particular, the optimal one). My goal is to write $\Pi_i(e^*_i,e_{-i})$ in some nice form to later disentangle it and say $\sum_i\Pi_i(e^*_i,e_{-i}) \geq \alpha\sum_i\Pi_i(e^*_i,e^*_{-i}) - \gamma\sum_i\Pi_i(e_i,e_{-i})$ for some computed $\alpha, \gamma$ and bound PoA by $\frac{\alpha}{1+\gamma}$. But the problem is I can't really think of a way to do that and to me $$\Pi_i(e^*_i,e_{-i}) = v_{ij^*}\mathbb{\chi}_{\{v_{ij^*} = \max_k\{v_{kj^*}\}\}}$$ that is if player(vertex) $i$ deviates it gets the weight of the edge between itself and some vertex in $B$ from the optimal solution iff no other player have already chosen the same vertex and had higher weight. Sadly, that form doesn't allow me to infer anything about the total payoff, i.e. I can't see how I could disentangle it.
I kindly ask for you help.