Ordres médians et ordres de Slater des tournois

Charon, Irène; Hudry, Olivier; Woirgard, Frédéric

Mathématiques informatique et sciences humaines, Tome 133 (1996), pp. 23-56.

Dans cet article, nous essayons de faire le point sur les résultats concernant les aspects combinatoires et algorithmiques des ordres médians et des ordres de Slater des tournois. La plupart des résultats recensés sont tirés de différentes publications ; plusieurs sont originaux.

In this paper, we try to enumerate the results dealing with the combinatorial and algorithmic aspects of the median orders and Slater orders of tournaments. Most of the quoted results may be found in the different papers devoted to these topics ; some others are new ones.

[1] Adám, A. (1964) "Problem" in Theory of graphs and its applications, Proc. Coll. Smolenice, Czech. Acad. Sci. Publ.

[2] Alon, N. (1990) "The maximum number of Hamiltonian paths in tournaments ", Combinatorica, 10, 319-324. | MR | Zbl

[3] Alon, N. et J. Spencer, The probabilistic method, J. Wiley, New York, 1992. | MR | Zbl

[4] Alspach, B. (1967) "Cycles of each length in regular tournaments", Canad. Math. Bull., 10, 283-286. | MR | Zbl

[5] Arditti, D. (1984) "Un nouvel algorithme de recherche d'un ordre induit par des comparaisons par paires", in Data analysis and informatics III, E. Diday et al. (sd), North Holland, Amsterdam, 323-343. | MR | Zbl

[6] Banks, J. (1985) "Sophisticated voting outcomes and agenda control ", Social Choice and Welfare, 2, 295-306. | Zbl

[7] Banks, J., G. Bordes et M. Le Breton (1991) "Covering relations, closest orderings and hamiltonian bypaths in tournaments", Social Choice and Welfare, 8, 355-363. | MR | Zbl

[8] Barthélemy, J.-P., G. Cohen et A. Lobstein (1992), Complexité algorithmique et problèmes de communication, Masson, Paris. | MR | Zbl

[9] Barthélemy, J.-P., A. Guénoche et O. Hudry (1989) "Median linear orders: heuristics and a branch and bound algorithm", EJOR, 41, 313-325. | MR | Zbl

[10] Barthélemy, J.-P., O. Hudry, G. Isaak, F.S. Roberts et B. Tesman (1995) "The reversing number of a digraph", Discrete Applied Mathematics, 60, 39-76. | MR | Zbl

[11] Barthélemy, J.-P. et B. Monjardet (1981) "The median procedure in cluster analysis and social choice theory", Mathematical Social Sciences, 1, 235-267. | MR | Zbl

[12] Barthélemy, J.-P. et B. Monjardet (1988) "The median procedure in data analysis : new results and open problems", in Classification and related methods of data analysis, H.H. Bock (sd), North Holland, Amsterdam. | MR

[13] Berge, C. (1970) Graphes, Gauthier-Villars.

[14] Berge, C. (1987) Hypergraphes, Gauthier-Villars. | Zbl

[15] Bermond, J.-C. (1972) "Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux", Math. Sci. hum, 37, 5-25. | Numdam | MR | Zbl

[16] Bermond, J.-C. et Y. Kodratoff (1976) "Une heuristique pour le calcul de l'indice de transitivité d'un tournoi", RAIRO, 10 (3), 83-92. | Numdam | MR

[17] Black, D. (1958) The theory of committees and elections, Cambridge University Press, Londres. | Zbl

[18] Charon-Fournier, I., A. Germa et O. Hudry (1992) "Encadrement de l'indice de Slater d'un tournoi à l'aide de ses scores", Math. Inf. Sci. hum, 118,53-68. | Numdam | Zbl

[19] Charon-Fournier, I., A. Germa et O. Hudry (1992) "Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois", Math. Inf. Sci. hum, 119, 53-74. | Numdam | MR | Zbl

[20] Charon-Fournier, I., A. Germa et O. Hudry, "Random generation of tournaments and asymmetric digraphs with given out-degrees", à paraître dans EJOR. | Zbl

[21] Charon, I., A. Guénoche, O. Hudry et F. Woirgard, "A branch and bound method applied to ordinal data analysis", Actes de l' "International Conference on Ordinal and Symbolic Data Analysis" (OSDA), Springer Verlag, à paraître.

[22] Charon, I., A. Guénoche, O. Hudry et F. Woirgard, "New results on the computation of median orders", Actes du "5e Colloque International de Théorie des Graphes et Combinatoire ", soumis pour publication.

[23] Charon, I. et O. Hudry, "Lamarckian genetic algorithms applied to the search of median orders", soumis pour publication.

[24] Charon, I., O. Hudry et F. Woirgard, "A 16-vertex tournament for which Banks set and Slater set are disjoint ", soumis pour publication. | Zbl

[25] Chartrand, G., D. Geller et S. Hedetniemi (1971) "Graphs with forbidden subgraphs", Journal of Combinatorial Theory, 10, 1, série B, 12-41. | MR | Zbl

[26] Condorcet, M.J.A.N. Caritat (marquis de) (1785) Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix, Paris.

[27] Cook, W.D., I. Golan et M. Kress (1988) "Heuristics for ranking players in a round robin tournament", Computers and Operations Research, 15 (2),135-144. | MR

[28] Debord, B. (1987) "Caractérisation des matrices de préférences nettes et méthodes d'agrégation associées", Mathématiques et Sciences Humaines 97, 5-17. | Numdam | MR | Zbl

[30] De La Vega, W.F. (1983) "On the maximal cardinality of a consistent set of arcs in a random tournament", Journal of Combinatorial Theory, 35, série B, 328-332. | MR | Zbl

[31] Erdös, P. et J.W. Moon (1965) "On sets of consistent arcs in a tournament", Canad. Math. Bull., 8, 269-271. | MR | Zbl

[32] Fishburn, P. (1977) "Condorcet social choice functions", SIAM Journal of Applied Mathematics, 33, 469-489. | MR | Zbl

[33] Fishburn, P. (1987) "Decomposing weighted digraphs into sums of chains", Discrete Applied Mathematics, 16, 15-31. | MR | Zbl

[34] Garey, M.R., et D.S. Johnson (1979) Computers and intractability, a guide to the theory of NP-completeness, Freeman, New York. | MR | Zbl

[35] Goddard, S.T. (1983) "Tournament rankings ", Management Science, 29 (12), 1385-1392. | MR | Zbl

[36] Grötschel, M., M. Jünger, G. Reinelt (1984) "A cutting plane algorithm for the linear ordering problem", Operations Research, 32, 1195-1220. | MR | Zbl

[37] Grötschel, M., M. Jünger, G. Reinelt (1984) "Optimal triangulation of large real-world input-output-matrices", Statistische Hefte, 25, 261-295.

[38] Grötschel, M., M. Jünger, G. Reinelt (1985) "Facets of the linear ordering polytope", Mathematical Programming, 33, 43-60. | MR | Zbl

[39] Guénoche, A. (1988) "Order at minimum distance of a valued tournament ", communication à Modélisation, Analyse et Agrégation des Préférences et des Choix (TRAP 3), Marseille-Luminy.

[40] Guénoche, A. (1995) "How to choose according to partial evaluations ", in Advances in Intelligent Computing, B. Bouchon-Meunier et al. (sd), IPMU'94, Lecture Notes in Computer Sciences n° 945, Springer-Verlag, Berlin-Heidelberg, 611-618.

[41] Guénoche, A. (1996) "Vainqueurs de Kemeny et tournois difficiles", Math. Inf. Sci. hum, 133; | Numdam | MR | Zbl

[42] Guénoche, A., B. Vandeputte-Riboud et J.-B. Denis (1994) " Selecting varieties using a séries of trials and a combinatorial ordering method", Agronomie, 14, 363-375.

[43] Guilbaud, G.T. (1952) "Les théories de l'intérêt général et le problème logique de l'agrégation", Économie Appliquée, 5 (4), repris dans Eléments de la théorie des jeux, Dunod, Paris, 1968.

[44] Guy, R.K. (1967) "A coarseness conjecture of Erdös", Journal of Combinatorial Theory, 3, 38-42. | MR | Zbl

[45] Hubert, L. (1976) "Seriation using asymmetric proximity measures", Br. J. Math. Statist. Psychol., 29, 32-52. | MR | Zbl

[46] Hudry, O. (1989) Recherche d'ordres médians : complexité, algorithmique et problèmes combinatoires, thèse de doctorat de l'ENST, Paris.

[47] Hudry, O. (1992) "Sur le nombre d'ordres médians de certains tournois ", Actes des journées Mathématiques Discrètes et Sciences Sociales, Amiens, 56-61.

[48] Hudry, O. et F. Woirgard (1994) "Combinatorics and voting theory : on the number of median orders of tournaments", communication à Conference on combinatorics in the behavioral sciences, Irvine, États-Unis.

[49] Hudry, O. et F. Woirgard (1995) "Lower and upper bounds of the maximum number of Slater's orders of tournaments", communication au 8e Colloque Franco-Japonais/4e Colloque Franco-Chinois Combinatoire et Informatique, Brest.

[50] Isaak, G. (1995) "Tournaments as feedback arc sets", The Electronic Journal of Combinatorics, 2. | MR | Zbl

[51] Jacquet-Lagrèze, É. (1969) "L'agrégation des opinions individuelles", Informatique et Sciences Humaines, 4, 1-21.

[52] Jung, H.A. (1970) "On subgraphs without cycles in a tournament", Combinatorial theory and its applications II, Balatonfüred, P. Erdös, A. Renyi et V.T. Sös (sd), Amsterdam, North-Holland, 675-677. | MR | Zbl

[53] Jünger, M. (1985) Polyhedral combinatorics and the acyclic subdigraph problem, Heldermann Verlag, Berlin. | MR | Zbl

[54] Kadane, J.B. (1966) "Some equivalence classes in paired comparisons ", Ann. math. Statist., 37, 488-494. | MR | Zbl

[55] Kaykobad, M., Q.N.U. Ahmed, A.T.M. Shafiqul Khalid et R.-A. Bakhtiar (1995) "A new algorithm for ranking players of a round-robin tournament", Computers and Operations Research, 22 (2), 221-226. | Zbl

[56] Kemeny, J.G. (1959) "Mathematics without numbers ", Daedalus, 88, 577-591.

[58] Laffond, G. et J.-F. Laslier (1991) "Slater's winners of a tournament may not be in the Banks set", Social Choice and Welfare, 8, 355-363. | MR | Zbl

[59] Laffond, G., J.-F. Laslier et M. Le Breton (1991) "Choosing from a tournament : a progress report and some new results", document de travail du CNAM.

[60] Landau, H.G. (1953) "On dominance relations and the structure of animal societies III. The condition for a score structure ", Bulletin of Mathematical Biophysics, 13, 1-19. | MR

[61] Laslier, J.-F. (1996) "Solutions de tournois : un spicilège", Math. Inf. Sci. hum, 133. | Numdam | MR | Zbl

[62] Lenstra, J.K. (1977) Sequencing by enumerative methods, Mathematical Centre Tracts n° 69, Mathematisch Centrum, Amsterdam. | MR | Zbl

[63] Marcotorchino, J.-F. et P. Michaud (1979) Optimisation en analyse ordinale de données, Masson, Paris.

[64] Miller, N. (1980) "A new solution set for tournaments and majority voting : Further graph-theoretical approaches to the theory of voting", American Journal of Political Science, 24 (1), 68-96.

[65] Monjardet, B. (1973) "Tournois et ordres médians pour une opinion", Mathématiques et Sciences Humaines, 43, 55-73. | Numdam | MR | Zbl

[66] Monjardet, B. (1990) "Sur diverses formes de la "règle de Condorcet" d'agrégation des préférences", Math. Inf. Sci. hum, 111, 61-71. | Numdam | MR | Zbl

[67] Moon, J.W. (1968) Topics on tournaments, Holt, Rinehart and Winston. | MR | Zbl

[68] Phillips, J.P.N. (1976) "On an algorithm of Smith and Payne for determining Slater's i and all nearest adjoining orders ", British Journal of Mathematical and Statistical Psychology, 29, 126-127.

[69] Poljak, S., V. Rödl et J. Spencer (1988) "Tournament ranking with expected profit in polynomial time", SIAM Journal Disc Math, 1 (3), 372-376. | MR | Zbl

[70] Poljak, S. et D. Turzik (1986) "A polynomial time heuristic for certain subgraph optimization problems with guaranteed lower bound", Discrete Mathematics, 58, 99-104. | MR | Zbl

[71] Reid, K.B. (1969) "On set of arcs containing no cycles in tournaments", Canad. Math. Bull., 12, 261-264. | MR | Zbl

[72] Reinelt, G. (1985) The linear ordering problem : algorithms and applications, Research and Exposition in Mathematics 8, Heldermann Verlag, Berlin. | MR | Zbl

[73] Remage Jr., R. et W.A. Thompsonjr. (1966) "Maximum likelihood paired comparison rankings", Biometrika, 53,143-149. | MR | Zbl

[74] Slater, P. (1961) "Inconsistencies in a schedule of paired comparisons", Biometrika, 48, 303-312.

[75] Smith, A.F.M. et C.D. Payne (1974) "An algorithm for determining Slater's i and all nearest adjoining orders", British Journal of Mathematical and Statistical Psychology 27, 49-52.

[76] Spencer, J. (1971) "Optimal ranking of tournaments ", Networks 1, 135-138. | MR | Zbl

[77] Spencer, J. (1978) "Nonconstructive methods in discrete mathematics ", in Studies in Combinatorics, G.C. Rota (sd), Mathematical Association of America, Washington DC, 142-178. | MR | Zbl

[78] Spencer, J. (1987) Ten lectures on the probabilistic method, CBMS-NSF Regional Conference Series in Applied Mathematics N° 52, SIAM, Philadelphie, États-Unis. | MR | Zbl

[79] Szele, T. (1943) "Kombinatorikai vizsgálatok az iránított teljes gráffal kapesolatban", Mat. Fiz. Lapok., 50, 223-256, traduit en allemand sous le titre " Untersuchungen über gerichtete vollständige Graphen", Publ. Math. Debrecen, 13 (1966), 145-168. | Zbl

[80] Thomassen, C. (1987) "Counterexamples to Adám's conjecture on arc reversals in directed graphs", Journal of Combinatorial Theory, 42, série B, 128-130. | MR | Zbl

[81] Younger, D.H. (1963) "Minimum feedback arc sets for a directed graph", IEEE Trans. of the profes. tech. group in circuit theory, 10 (2), 238-245.