Anti-coordination games on networks belong to the class of games with negative social interactions. They appear in many contexts including snob goods, product differentiation, resource allocation etc. Graph colouring provides a natural way of modelling anti-coordination games on networks. In this paper, we discuss this class of games with primary focus on social efficiency. Our model captures the social efficiency as the Pareto optimal Nash equilibrium. We will also provide a distributed learning rule to achieve the social efficiency in the network. The strong point of our learning mechanism is that it depends only on the local information and converges always to a Nash equilibrium.
Arko Chatterjee is a senior Ph.D. student in IEOR, well on his path to greater glory.