CMSS 2014 Summer Workshop - Arkadii Slinko
Channel: Centre for Mathematical Social Sciences
Date: 2014-12-15

The Single-crossing Property on Median Graphs. Presented by Arkadii Slinko at the Centre for Mathematical Social Sciences 2014 Summer Workshop.


Abstract:
We generalize the classical single-crossing property to single-crossing property on me- dian graphs. Examples of median graphs are trees and grid graphs. We assume that agents are located at the vertices of a median graph and each is endowed with a linear preference order over a set of alternatives A. The single-crossing property stipulates that if two agents situated at vertices U and V agree on their assessment of two alter- natives, say a and b, then all voters on the shortest path between U and V also agree with them in assessment of these alternatives.
For such a society the majority relation is always transitive, hence the respective linear orders form the so-called Condorcet domain. Condorcet domains are sets of linear orders which possess the property that every profile composed from those orders have transitive majority relation. We show that maximal Condorcet domains are single-crossing on a certain median graph. We also prove that for any median graph there exist profiles that are single-crossing on that graph and we provide a polynomial- time algorithm to recognize whether or not a given profile is single-crossing with respect to some median graph. We also show that finding winners for the NP-hard Chamberlin- Courant rule is polynomial for profiles that are single-crossing on median graphs.