Acyclic domains of linear orders: a survey

Bernard Monjardet (1)

1 CES - Centre d'économie de la Sorbonne

Among the many significant contributions of Fishburn to social choice theory some have borne on what he has called «acyclic sets», i.e. these sets of linear orders where majority rule applies without «Condorcet effect» (majority relation never has cycles). Search for large such domains is a fascinating topic. I review the works in this field and in particular a recent one allowing to show the connections between some of them unrelated up to now.

Un domaine condorcéen (ou «acyclic set» dans Fishburn) est un ensemble d'ordres totaux où la règle majoritaire s'applique sans «effet Condorcet» : la relation majoritaire de tout profil de préférences choisies dans cet ensemble n'admet aucun circuit. La recherche de domaines condorcéens de grande taille (voire de taille maximum) est un sujet fascinant (mais très difficile). On présente un historique et une vue d'ensemble des principaux résultats obtenus et notamment de ceux tout récents de Galambos et Reiner (2006) qui permettent d'établir des liens -insoupçonnés jusqu'ici- entre plusieurs de ces résultats.

Mots clés: Acyclic set; alternating scheme; distributive lattice; effet Condorcet; maximal chain; permutoedre lattice; weak Bruhat order; value restriction

Mots clés: permutoèdre; ordre faible de Bruhat; Ensemble acyclique de permutations; ordre total; treillis distributif; permutations restreintes

Domaines: Economies et finances

Bernard Monjardet. Acyclic domains of linear orders: a survey. 2007. ⟨halshs-00130205v2⟩