Advanced Search
Article Contents
Article Contents

Weight set decomposition for weighted rank and rating aggregation: An interpretable and visual decision support tool

  • *Corresponding author: Amy N. Langville

    *Corresponding author: Amy N. Langville 
Abstract Full Text(HTML) Figure(11) / Table(1) Related Papers Cited by
  • The problem of interpreting or aggregating multiple rankings is common to many real-world applications. Perhaps the simplest and most common approach is a weighted rank aggregation, wherein a (convex) weight is applied to each input ranking and then ordered. This paper describes a new tool for visualizing and displaying ranking information for the weighted rank aggregation method. Traditionally, the aim of rank aggregation is to summarize the information from the input rankings and provide one final ranking that hopefully represents a more accurate or truthful result than any one input ranking. While such an aggregated ranking is, and clearly has been, useful to many applications, it also obscures information. In this paper, we show the wealth of information that is available for the weighted rank aggregation problem due to its structure. We apply weight set decomposition to the set of convex multipliers, study the properties useful for understanding this decomposition, and visualize the indifference regions. This methodology reveals information–that is otherwise collapsed by the aggregated ranking–into a useful, interpretable, and intuitive decision support tool. Included are multiple illustrative examples, along with heuristic and exact algorithms for computing the weight set decomposition.

    Mathematics Subject Classification: Primary: 90-04, 68W99, 52A15; Secondary: 62F07, 68T37, 68T01.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  The set of convex weights $ \Lambda $ creates a triangle in $ \mathbb{R}^3 $ (left) that can be visualized in $ \mathbb{R}^2 $ (right). When the weights are equally weighted, i.e., $ \lambda = (\frac{1}{3}, \frac{1}{3}, \frac{1}{3}) $, the aggregated ranking is equidistant from the three corners, and hence, the three input rankings

    Figure 2.  The triangle on the left shows the weight set $ \Lambda $ for Patient A, Anne, visualized in $ \mathbb{R}^2 $. Two sets of weights are shown. The weights $ (\frac{1}{2}, \frac{1}{2}, 0) $ is midway along the boundary between $ \bar r^1 $ and $ \bar r^2 $, and so it compromises between only two criteria (longevity and simplicity). The weight $ (\frac{5}{12}, \frac{5}{12}, \frac{1}{6}) $ is in the interior of the triangle, moved slightly toward the third criterion of cost. The triangle on the right shows colored axes that indicate the relative weight of a goal and guide users in movement toward or away from a particular goal

    Figure 3.  (Left) Rank colormap for Patient A, Anne. (Right) Barchart displaying the percentage of $ \Lambda $ on the $ y $-axis per region with the corresponding ranking labeled on the $ x $-axis. A quick scan of this barchart shows the relative area associated with each ranking

    Figure 4.  Rank colormap for Patient B, Bob. While Bob's colormap contains $ |A| = 18 $ regions, more than Anne's, several regions, and hence rankings, have insignificant areas

    Figure 5.  Pairwise item analysis. (Left) Item 1 is ranked better than 5 in 96% of the weighted ranks, shown in blue. (Right) Item 2 is ranked better than 3 in 75% of the weighted ranks, shown in blue

    Figure 6.  Illustrating the steps of the exact algorithm

    Figure 7.  (left) The rating colormap shows $ |A| = 20 $ regions. When the data is converted to rankings as input, the ranking colormap (right) also has $ |A| = 14 $ regions. Clearly, the two colormaps differ. In short, our colormap work allows for input vectors $ \bar r^1 $, $ \bar r^2 $, and $ \bar r^3 $ that are either rating vectors or ranking vectors

    Figure 8.  The map on the left shows the heatmap for Treatment $ T_1 $ Temozolomide. Lighter regions indicate that Treatment $ T_1 $ ranks better in the aggregated ranking associated with that region. Treatment $ T_1 $ scores poorly when quality of life is the most important consideration. The map on the right shows the heatmap for another treatment, $ T_3 $ Gliovac, which scores better on quality of life and not as well in the compromise area between quality of life and simplicity of the treatment regimen

    Figure 9.  Sensitivity Map. The darker points near the center of a region are most robust, i.e., their ranking of treatments is least sensitive to small changes in the input weights $ \lambda_i $

    Figure 10.  The $ j = 4 $ polytope in $ \mathbb{R}^3 $ (left). Planes through the polytope for fixed values of $ \lambda_4 $ (right). The largest plane is the $ \lambda_4 = 1 $ plane through the polytope, which is a face of the $ j = 4 $ polytope. The other planes are the when $ \lambda_4 = .75 $, $ \lambda_4 = .5 $, and $ \lambda_4 = .25 $. The origin corresponds to $ \lambda_4 = 0 $. There are infinitely many planes at fixed $ \lambda_4 $ through this polytope, each with color-coded points mapped to aggregated rankings

    Figure 11.  (Left) Nonlinear function for weight $ \lambda_3 $ associated with cost. Cost of a treatment has little impact for small values of $ \lambda_3 $ but then increases rapidly. (Right) This nonlinear transformation affects the geometry of the indifference regions

    Table 1.  The scale of instances are indicated by number of ranked items, $ n $, and the number of resulting indifference regions (IRs). For Step 1, heuristic grid search, column 3 indicates the number of subintervals in the partitioned grid. Run time is reported for steps 1-5

    $ n $ IRs Grid Step 1 (sec) Step 2 (sec) Step 3 (sec) Step 4 (sec) Step 5 (sec)
    5 18 $ 10^3 $ 0.242 0.140 0.077 0.064 0.008
    10 115 $ 10^4 $ 1.159 0.135 0.194 0.529 0.015
    15 1189 $ 10^5 $ 32.218 0.127 0.596 27.905 0.130
    20 4029 $ 10^6 $ 1952.166 0.451 3.447 385.059 0.423
     | Show Table
    DownLoad: CSV
  • [1] Software Rights Archive, LLC v. Google Inc.; Yahoo! Inc.; IAC Search Media, Inc.; AOL LLC; and Lycos, Inc., US Northern District of California, Case No. cv-08-3172 2012.,
    [2] Valtrus Innovations Ltd v. Google LLC., US Northern District of Texas, Case No. 3: 22-cv-00066-N 2022.,
    [3] M. J. Alves and J. P. Costa, Graphical exploration of the weight space in three-objective mixed integer linear programs, European Journal of Operational Research, 248 (2016), 72-83.  doi: 10.1016/j.ejor.2015.06.072.
    [4] P. AndersonT. Chartier and A. Langville, The rankability of data, SIAM Journal on the Mathematics of Data Science, 1 (2019), 121-143.  doi: 10.1137/18M1183595.
    [5] P. E. Anderson, T. P. Chartier, A. N. Langville and K. E. Pedings-Behling, The rankability of weighted data from pairwise comparisons, Foundations of Data Science, (2021), 1-26. doi: 10.3934/fods.2021002.
    [6] P. E. Anderson, T. P. Chartier, A. N. Langville and K. E. Pedings-Behling, Fairness and the set of optimal rankings for the linear ordering problem, Optimization and Engineering, (2021), 1-29. doi: 10.1007/s11081-021-09650-y.
    [7] J. Bennett, S. Lanning, et al., The Netflix prize, in Proceedings of KDD Cup and Workshop, vol. 2007, New York, 2007, p. 35.
    [8] H. P. Benson and E. Sun, Outcome space partition of the weight set in multiobjective linear programming, Journal of Optimization Theory and Applications, 105 (2000), 17-36.  doi: 10.1023/A:1004605810296.
    [9] T. R. CameronA. N. Langville and H. C. Smith, On the graph Laplacian and the rankability of data, Linear Algebra and its Applications, 588 (2020), 81-100.  doi: 10.1016/j.laa.2019.11.026.
    [10] C. Dwork, R. Kumar, M. Naor and D. Sivakumar, Rank aggregation methods for the web, in Proceedings of the 10th International Conference on World Wide Web, 2001,613-622. doi: 10.1145/371920.372165.
    [11] M. Ehrgott, Multicriteria Optimization, vol. 491, Springer Science & Business Media, 2005.
    [12] S. C. Geyik, S. Ambler and K. Kenthapadi, Fairness-aware ranking in search & recommendation systems with application to linkedin talent search, in Proceedings of the 25th Acm Sigkdd International Conference on Knowledge Discovery & Data Mining, 2019, 2221-2231. doi: 10.1145/3292500.3330691.
    [13] J. GuoY. FanL. PangL. YangQ. AiH. ZamaniC. WuW. B. Croft and X. Cheng, A deep look into neural ranking models for information retrieval, Information Processing & Management, 57 (2020), 102067.  doi: 10.1016/j.ipm.2019.102067.
    [14] G. Karakaya and M. Köksalan, Evaluating solutions and solution sets under multiple objectives, European Journal of Operational Research, 294 (2021), 16-28.  doi: 10.1016/j.ejor.2021.01.021.
    [15] P. Kidwell, G. Lebanon and W. Cleveland, Visualizing incomplete and partially ranked data, IEEE Trans Vis Comput Graph, 6 (2008), 1356-1363. doi: 10.1109/TVCG.2008.181.
    [16] S.-H. Kim and B. L. Nelson, Recent advances in ranking and selection, in 2007 Winter Simulation Conference, IEEE, 2007,162-172.
    [17] G. A. Kramer, System and method for selecting weighting for searching and for presentation of search results, U.S. Patent 20090164948A1, Dec. 2007, https://patentimages.storage.googleapis.com/d1/93/3c/977340213bf726/US20090164948A1.pdf
    [18] A. N. Langville and  C. D. MeyerWho's# 1? The Science of Rating and Ranking, Princeton University Press, 2012. 
    [19] K. Massey, Statistical Models Applied to the Rating of Sports Teams, Bluefield College, 1077 (1997).
    [20] N. McJames, D. Malone and O. Mason, A supervised learning approach to rankability, Tech. Report, arXiv: 2203.07364, Hamilton Institute, Maynooth University, 2022.
    [21] T. A. Perini, Techniques for Multiobjective Optimization with Discrete Variables: Boxed Line Method and Tchebychev Weight Set Decomposition, PhD thesis, Georgia Institute of Technology, 2021.
    [22] A. PrzybylskiX. Gandibleux and M. Ehrgott, A recursive algorithm for finding all nondominated extreme points in the outcome set of a multiobjective integer programme, INFORMS Journal on Computing, 22 (2010), 371-386.  doi: 10.1287/ijoc.1090.0342.
    [23] M. G. SchimekE. BudinskáK. G. KuglerV. ŠvendováJ. Ding and S. Lin, Topklists: A comprehensive R package for statistical inference, stochastic aggregation, and visualization of multiple omics ranked lists, Statistical Applications in Genetics and Molecular Biology, 14 (2015), 311-316.  doi: 10.1515/sagmb-2014-0093.
    [24] B. Smith and G. Linden, Two decades of recommender systems at Amazon.com, IEEE Internet Computing, 21 (2017), 12-18.  doi: 10.1109/MIC.2017.72.
  • 加载中




Article Metrics

HTML views(2009) PDF downloads(161) Cited by(0)

Access History



    DownLoad:  Full-Size Img  PowerPoint