New Models and Methodologies for Group Decision Making,
Rank Aggregation, Clustering, and Data Mining
Dorit Hochbaum
Department of Industrial Engineering and Operations Research
University of California, Berkeley
Wednesday, November 30, 2005
4:30 - 5:45 PM
Terman Engineering Center, Room 453
Abstract:
We introduce models for problems of group decision making, aggregate
ranking and clustering techniques for data mining. The problems are
modeled as graph problems. One of these problems we call the equal
paths problem. This problem as well as all problems studied here have
convex objective function representing penalties for deviating from
specified a-priori comparison/ranking beliefs. These problems are
shown to be solvable in polynomial time using network flow techniques
such as parametric cut and fractional multicommodity linear
programming.
One application of the aggregate ranking problem is to determine the
ranking of sports teams based on the outcomes of games played.
Current
techniques are based on finding a maximum eigenvector. Our
alternative model has a number of advantages including the ability to
differentiate between games based on some measure of significance.
Further, the problem is stated as a combinatorial graph problem. This
problem is shown to be solved in polynomial time even with a convex
objective function, using flow techniques.
We point out several problems relating to the robustness of a set of
evaluations (game outcomes) with respect to generating a ranking.
These problems appear to be new and are shown to be NP-hard.
Another area that addresses various forms of rankings has to do with
data mining with applications to customer segmentation, patient
diagnosis and assessment of bankrupcy risk. We demonstrate new models
for these problems and how to solve them with flow techniques.
Problems of group decision making and of multi-criteria decision
making are closely related to the problems above. We demonstrate that
the dominant problems in these areas can also be modeled and solved
with flow related techniques.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html