Optimizing social welfare for network bargaining games in the face of unstability, greed and spite

Abstract

Stable and balanced outcomes of network bargaining games have been investigated recently, but the existence of such outcomes requires that the linear program relaxation of a certain maximum matching problem has integral optimal solution. We propose an alternative model for network bargaining games in which each edge acts as a player, who proposes how to split the weight of the edge among the two incident nodes. Based on the proposals made by all edges, a selection process will return a set of accepted proposals, subject to node capacities. An edge receives a commission if its proposal is accepted. The social welfare can be measured by the weight of the matching returned. The node users, as opposed to being rational players as in previous works, exhibit two characteristics of human nature: greed and spite. We define these notions formally and show that the distributed protocol by Kanoria et. al can be modified to be run by the edge players such that the configuration of proposals will converge to a pure Nash Equilibrium, without the LP integrality gap assumption. Moreover, after the nodes have made their greedy and spiteful choices, the remaining ambiguous choices can be resolved in a way such that there exists a Nash Equilibrium that will not hurt the social welfare too much. © 2012 Springer-Verlag.