Treffer: Ranking sports teams and the inverse equal paths problem

Title:
Ranking sports teams and the inverse equal paths problem
Authors:
HOCHBAUM, Dorit S
Source:
Internet and network economics (Second International workshop, WINE 2006, Patras, Greece, December 15-17, 2006)Lecture notes in computer science. :307-318
Publisher Information:
Berlin; Heidelberg: Springer, 2006.
Publication Year:
2006
Physical Description:
print, 25 ref 1
Original Material:
INIST-CNRS
Subject Terms:
Economy, Economie, Computer science, Informatique, Telecommunications, Télécommunications, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Flots dans les réseaux. Problèmes combinatoires, Flows in networks. Combinatorial problems, Théorie de la décision. Théorie de l'utilité, Decision theory. Utility theory, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Logiciel, Software, Systèmes informatiques et systèmes répartis. Interface utilisateur, Computer systems and distributed systems. User interface, Intelligence artificielle, Artificial intelligence, Algorithmique, Algorithmics, Algorítmica, Analyse multicritère, Multicriteria analysis, Análisis multicriterio, Apprentissage(intelligence artificielle), Learning (artificial intelligence), Classification hiérarchique, Hierarchical classification, Clasificación jerarquizada, Contrôle qualité, Quality control, Control calidad, Décision multiple, Multiple decision, Decisión múltiple, Evaluation performance, Performance evaluation, Evaluación prestación, Flot réseau, Network flow, Flujo red, Fonction convexe, Convex function, Función convexa, Fonction pénalité, Penalty function, Función penalidad, Intelligence artificielle, Artificial intelligence, Inteligencia artificial, Internet, Modèle agrégé, Aggregate model, Modelo agregado, Modèle économique, Economic model, Modelo económico, Méthode polynomiale, Polynomial method, Método polinomial, Optimisation combinatoire, Combinatorial optimization, Optimización combinatoria, Prise décision, Decision making, Toma decision, Problème NP difficile, NP hard problem, Problema NP duro, Problème combinatoire, Combinatorial problem, Problema combinatorio, Problème inverse, Inverse problem, Problema inverso, Routage, Routing, Enrutamiento, Réseau web, World wide web, Red WWW, Site Web, Web site, Sitio Web, Sport équipe, Team sport, Deporte equipo, Système aide décision, Decision support system, Sistema ayuda decisíon, Temps polynomial, Polynomial time, Tiempo polinomial, Théorie décision, Decision theory, Teoría decisión, Vecteur propre, Eigenvector, Vector propio
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Industrial Engineering and Operations Research and Walter A. Haas School of Business, University of California, Berkeley, United States
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=19150980
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Operational research. Management
Accession Number:
edscal.19150980
Database:
PASCAL Archive

Weitere Informationen

The problem of rank aggregation has been studied in contexts varying from sports, to multi-criteria decision making, to machine learning, to academic citations, to ranking web pages, and to descriptive decision theory. Rank aggregation is the mapping of inputs that rank subsets of a set of objects into a consistent ranking that represents in some meaningful way the various inputs. In the ranking of sports competitors, or academic citations or ranking of web pages the inputs are in the form of pairwise comparisons. We present here a new paradigm using an optimization framework that addresses major shortcomings in current models of aggregate ranking. Ranking methods are often criticized for being subjective and ignoring some factors or emphasizing others. In the ranking scheme here subjective considerations can be easily incorporated while their contributions to the overall ranking are made explicit. The inverse equal paths problem is introduced here, and is shown to be tightly linked to the problem of aggregate ranking optimally. This framework is useful in making an optimization framework available and by introducing specific performance measures for the quality of the aggregate ranking as per its deviations from the input rankings provided. Presented as inverse equal paths problem we devise for the aggregate ranking problem polynomial time combinatorial algorithms for convex penalty functions of the deviations; and show the NP-hardness of some forms of nonlinear penalty functions. Interestingly, the algorithmic setup of the problem is that of a network flow problem. We compare the equal paths scheme here to the eigenvector method, Google PageRank for ranking web sites, and the academic citation method for ranking academic papers.