27 November 2009, Computational Social Choice Seminar, Willemien Kets

Abstract

We explore the manner in which the structure of a social network constrains the level of inequality that can be sustained among its members, based on the following considerations: (i) any distribution of value must be stable with respect to coalitional deviations, and (ii) joint deviations require communication and coordination, so the network structure itself determines the coalitions that may form. We show that if players can jointly deviate only if they form a clique in the network, then the degree of inequality that can be sustained depends on the cardinality of the maximum independent set. For bipartite graphs, this criterion allows us to obtain a complete ordering of networks with respect to the levels of inequality they can sustain. For general graphs, we obtain a partial ordering with the following property: extremal inequality cannot be larger in a network with a smaller maximum independent set. These results extend naturally to the case in which a group of players can deviate jointly if they are all within some fixed distance (possibly greater than one) of each other.

For more information, see http://www.illc.uva.nl/~ulle/seminar/, or contact Ulle Endriss (ulle at illc.uva.nl).