Computing Manipulations of Ranking Systems

Ranking systems are widely used by agencies to rank agents, for example U.S. News & World Report ranks colleges. Such rankings are prone to manipulation by the agency (e.g. USNews) for publicity, and also by the agents (e.g. colleges) to get a better rank. We analyze the algorithmic aspects of manipulation in linear ranking systems of m agents using n features. Computing optimal manipulation for the ranking agency is NP-hard: we give a mixed integer linear program solution, and also an efficient linear programming heuristic that formulates the problem as a classification task. Computing optimal manipulations for ranked agents subject to a budget constraint is a minimax problem in a continuous space: we give a general O((m + k) n 2-n m n-1 log m) algorithm, where k is the number of linear constraints on the weight vector and an O(m(log m) 2) algorithm for n = 2. We also present a large class of heuristic algorithms with approximation ratio n. We tested our algorithms on USNews data from the 2015 college rankings. Our algorithms compute agency and agent manipulation strategies in seconds. We present several interesting experiments on the ranking range of the top-100 colleges, including optimal spending plans for these colleges.