Hypergraphical Clustering Games of Mis-Coordination Academic Article uri icon

abstract

  • Abstract: The price of anarchy was introduced to measure the loss incurred by a society of agents who take actions in a decentralized manner instead of through a central authority. Hypergraph coloring has traditionally been studied in the context of a central designer who chooses colors. In this paper we study the price of anarchy when the choice of color is delegated to each of the vertices which are assumed self-interested. Subjects: Combinatorics (math. CO); Distributed, Parallel, and Cluster Computing (cs. DC); Discrete Mathematics (cs. DM); Computer Science and Game Theory (cs. GT); Social and Information Networks (cs. SI)

publication date

  • January 1, 2017

published in