A = {1,2…i, j,k…n} is a finite set of n elements that I will generally call alternatives (but which could also be called issues, decisions, outcomes, candidates, objects, etc.). The elements of A will be also denoted by letters like x,y, z etc. A subset of cardinality p of A will be called a p-set.
A 2 (respectively, A 3) denotes the set of all ordered pairs (x,y) (respectively, ordered triples (x,y, z) written for convenience as xyz) of A. When the elements of A are denoted by the n first integers, P 2(n) denotes the set of the n(n- 1)/2 ordered pairs (i < j).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abello, J. M. (1981). Toward a maximum consistent set.Technical Report TRCS11—81, Computer Science Department, University of California.
Abello, J. M. (1985a).A study of an independence system arising in group choice via the weak Bruhat order. Ph.D. thesis, University of California, San Diego, CA.
Abello, J. M. (1985b). Intrinsic limitations of the majority rule, an algorithmic approach.SIAM Journal of Algebraic and Discrete Methods, 6, 133–144.
Abello, J. M. (1987). Algorithms for consistent sets.Congressus Numerantium, 53, 23–38.
Abello, J. M. (1988). An extremal problem on Sn. Advanced Research Institute in Discrete Applied Mathematics (ARIDAM) Workshop.
Abello, J. M. (1991). The weak Bruhat order ofS n, consistent sets, and Catalan numbers.SIAM Journal of Algebraic and Discrete Methods, 4(1), 11–16.
Abello, J. M. (2004). The majority rule and combinatorial geometry (via the Symmetric Group).Annales du LAMSADE, 3, 1–13.
Abello, J. M.,&Johnson, C. R. (1984). How large are transitive simple majority domains?SIAM Journal of Algebraic and Discrete Methods, 5(4), 603–618.
Arrow, K. J. (1951,1970).Social choice and individual values. New York: Wiley.
Arrow, K. J.,&Raynaud, H. (1986).Social choice and multicriterion decision-making. Cambridge: MIT.
Barthélemy, J. P.,&Monjardet, B. (1981). The Median procedure in cluster analysis and social choice theory.Mathematical Social Science,1, 235–268.
Barbut, M.,&Monjardet, B. (1970).Ordre et Classification, Algèbre et Combinatoire, tomes I et II. Paris: Hachette.
Bartholdi, J. J., III.,&Trick, M. A. (1986). Stable matching with preferences derived fom a psychological model.Operations Research Letters, 5(4), 165–169.
Berge, C. (1971).Principles of combinatorics. New York: Academic.
Björner, A. (1984). Orderings of Coxeter groups. In C. Greene, (Ed.),Combinatorics and algebra. Contemporary Mathematics 34(pp. 175–195), Providence R.I.: American Mathematical Society.
Black, D. (1948). On the rationale of group decision-making.Journal of Political Economy,56, 23–34.
Black, D. (1958).The theory of committees and elections. Cambridege: Cambridge University Press.
Black, D. (1998). The theory of committees&Committee decisions with complementary valuation by Duncan Black and R.A. Newing, Revised 2nd ed. In I. S. McLean, A. McMillan,&B. L. Monroe (Eds.) Boston: Kluwer.
Blin, J. -M. (1973). The general concept of multidimensional consistency: Some algebraic aspects of the aggregation problem. InConference proceedings of the south carolina seminar on multiple criteria decision making. University of South Carolina Press.
Caspard, N. (2000). The lattice of permutations is bounded.International Journal of Algebra and Computation, 10(4), 481–489.
Chameni-Nembua, C. (1989a).Permutoèdre et choix social. Third cycle thesis, Université de Paris V.
Chameni-Nembua, C. (1989b). Régle majoritaire et distributivité dans le permutoèdre.Mathématiques Informatique et Sciences humaines,108, 5–22.
Condorcet, M. J. A. M. (1785). Essai sur l'application de l'analyse a la probabilité des décisions rendues à la pluralité des voix. Paris.
Craven, J. (1992a).Social choice: a framework for collective decisions and individual judgements. Cambridge: Cambridge University Press.
Craven, J. (1992b). Further notes on Craven's conjecture.Social Choice and Welfare, 11(3), 283– 285.
Craven, J. (1996). Majority consistent preference orderings.Social Choice and Welfare, 13(3), 259–267
Day, W. H. E.,&McMorris, F. R. (2005).Axiomatic consensus theory in group choice and bio-mathematics. Philadelphia: SIAM.
Dumett, M.,&Farquharson, R. (1961). Stability in voting.Econometrica,29, 33–41.
Duquenne, V.,&Cherfouh, A. (1994). On permutation lattices.Mathematical Social Sciences,27(1), 73–89.
Doignon, J. P.,&Falmagne, J. C. (1994). A polynomial algorithm for unidimensional unfolding representations.Journal of Algorithms,16, 218–233.
Edelman, P.,&Greene, C. (1987). Balanced tableaux.Advances in Mathematics,63(1), 42–99.
Fishburn, P. C. (1992). Notes on Craven's conjecture.Social Choice and Welfare,9(3), 259–262.
Fishburn, P. C. (1996). Decision theory and discrete mathematics.Discrete Applied Mathematics,68(3), 209–221.
Fishburn, P. C. (1997). Acyclic sets of linear orders.Social Choice and Welfare,14(1), 113–124.
Fishburn, P. C. (2002). Acyclic sets of linear orders:A progress report. Social Choice and Welfare,19(2), 431–447.
Frey, L. (1971).Parties distributives du treillis des permutations, In Ordres totaux finis Mathématiques et Sciences de l'Homme XII(pp. 115–126). Paris: Gauthier-Villars.
Frey, L.,&Barbut, M. (1971).Technique ordinales en analyse des données, Algèbre et combina- toire. Paris: Hachette.
Galambos, A.,&Reiner, V. (2008). Acyclic sets of linear orders via the Bruhat order,Social Choice and Welfare,30(2), 245–264.
Guilbaud, G. T. H. (1952). Les théories de l'ntérêt général et le problème logique de l'agrégation. Economie Appliquée 5(4) reprinted inEléments de la théorie des jeux, Dunod, Paris, 1968. English translation: Theories of the general interest and the logical problem of aggregation. Electronic Journal for History of Probability and Statistics, 4, 2008.
Guilbaud, G. T. h.,&Rosenstiehl, P. (1963). Analyse algébrique d'un scrutin.Mathématiques et Sciences humaines,4, 9–33.
Inada, K. (1964). A note on the simple majority decision rule.Econometrica,32(4), 525–531.
Johnson, C. R. (1978).Remarks on mathematical social choice. Working paper 78–25, Department of Economics, University of Maryland, College Park.
Kelly, J. S. (1991). Craven's conjecture.Social Choice and Welfare,8(3), 269–274.
Kim, K. H.,&Roush, F. W. (1980).Introduction to mathematical consensus theory. New York: Marcel Dekker.
Kim, K. H., Roush, F. W.,&Intriligator, M. D. (1992). Overview of mathematical social sciences.American Mathematical Monthly,99, 838–844.
Köhler, G. (1978).Choix multicritère et analyse de données ordinales. Third cycle thesis, Univer- sité scientifique et médicale de Grenoble.
Le Conte de Poly-Barbut, C. (1990).Le diagramme du treillis permutoèdre est intersection des diagrammes de deux produits directs d'ordres totaux.Mathématiques, Informatique et Sciences humaines,112, 49–53.
Markowsky, G. (1994). Permutation lattices revisited.Mathematical Social Sciences,27(1), 59–72.
Monjardet, B. (1971).Treillis d'ordres, In Ordres totaux finis, Mathématiques et Sciences de l'Homme XII(pp. 29–45). Paris: Gauthier-Villars.
Monjardet, B. (1978). An axiomatic theory of tournament aggregation.Mathematical and Operation Research,3(4), 334–351.
Monjardet, B. (2006a). Social choice theory and the “Centre de Mathématique Sociale”. Some historical notes.Social choice and Welfare,25(2–3), 433–456.
Monjardet, B. (2006b). Condorcet domains and distributive lattices.Annales du LAMSADE,6, 285–302.
Provan, J. S.,&Ball, M. O. (1983). The complexity of counting cuts and of computing the probability that a graph is connected.SIAM Journal on Computing,12, 777–788.
Raynaud, H. (1981a). Paradoxical results from Inada's conditions for majority rule.Technical Report 331. Institute for mathematical studies in the social sciences, Standford University, Standford, CA.
Raynaud, H. (1981b). Conditions for transitivity of majority rule with algorithmic interpretations.Technical Report 347. Institute for mathematical studies in the social sciences, Standford University, Standford, CA.
Raynaud, H. (1981c). How restrictive actually are the value restriction conditions.Technical Report 348. Institute for mathematical studies in the social sciences, Standford University, Standford, CA.
Raynaud, H. (1982). The individual freedom allowed by the value restriction conditions.Technical Report 360. Institute for mathematical studies in the social sciences, Standford University, Standford, CA.
Raz, R. (2000). VC-dimension of sets of permutations.Combinatoria,20, 1–15.
Romero, D. (1978).Variation sur l'effet Condorcet. Third cycle thesis, Université scientifique et médicale de Grenoble.
Sen, A. K. (1966). A possibility theorem on majority decisions.Econometrica,34(2), 491–499.
Vickrey, W. (1960). Utility, strategy and social decision rules.Quaterly Journal of Economics,74, 507–535.
Ward, B. (1965). Majority voting and the alternative forms of public enterprise. In J. Margolis, (Ed.),The public economy of urban communities. Baltimore, MD: John Hopkins University Press.
Yanagimoto, T.,&Okamoto, M. (1969). Partial orderings of permutations and monotonicity of a rank correlation statistic.Annals Institute of Statistics,21, 489–506.
Ziegler, G. M. (1993). Higher Bruhat orders and cyclic hyperplanes arrangements.Topology,32(2), 259–279.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Monjardet, B. (2009). Acyclic Domains of Linear Orders: A Survey. In: Brams, S.J., Gehrlein, W.V., Roberts, F.S. (eds) The Mathematics of Preference, Choice and Order. Studies in Choice and Welfare. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-79128-7_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-79128-7_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-79127-0
Online ISBN: 978-3-540-79128-7
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)