<p>This is a special case of metric $1$-medians, where the metric space is $S_n$ (the symmetric group on $n$ elements) with distance function number of inversions (i.e. the distance between two permutations is the number of pairs $i, j: i&lt;j$ s.t. $i$ and $j$ are ordered differently). This distance metric is also known as Kemeny distance and is related to the weak Bruhat order. </p>

<p>This <a href="http://dl.acm.org/citation.cfm?id=1411513" rel="nofollow">paper</a> by Ailon, Charikar, and Newman considers this and related problems. The problem you're asking about is called Rank Aggregation in their paper. Look at their intro for more references. The problem is NP-hard. A simple 2-approximation is to pick the best of the given $k$ permutations (i.e. the permutation that minimizes the objective function). Here is a proof:</p>

<p>Let $\pi$ be the optimal permutation and $\pi_{j^*}$ the best of $\pi_1, \ldots, \pi_k$. For any $i, j \in [k]$, by the triangle inequality, $d(\pi_i, \pi) + d(\pi_j, \pi) \geq d(\pi_i, \pi_j)$. Sum over all $i, j$, and you get $2n\mathsf{OPT} \geq \sum_j{\mathsf{ALG}(j)}$, where $\mathsf{ALG(j)}$ is the cost of choosing $\pi_j$ as the solution, and $\mathsf{OPT}$ is the cost of the optimal solution. Since $\pi_{j^*}$ was chosen so that $\mathsf{ALG}(j^*)$ is minimum over all $\mathsf{ALG}(j)$ for $j \in [k]$, we have $\mathsf{ALG}(j^*) \leq \sum_j{\mathsf{ALG}(j)} /n$ and we have $\mathsf{ALG}(j^*) \leq 2\mathsf{OPT}$.</p>

<p>The paper I referred you to above has another, almost equally simple 2-approximation (but the proof is not that simple, though still not bad). They can show that the bad cases for the two approximation algorithms are different, and taking the better solution of the two gives 11/7 approximation factor. </p>

<p>Then there is also a PTAS by Mathieu and Schudy (Warren sometimes visits this site btw), by a reduction to weighted Minimum Feedback Arc Set in Tournamets (the same reduction is used in the previous paper, I think). Here is the <a href="http://www.cs.brown.edu/~ws/papers/fast_journal.pdf" rel="nofollow">link</a></p>

CC BY-SA 3.0
2011-09-21T02:52:26.780Z
of course the simple 2-approximation works for finding an approximate median in any metric space
Sasho Nikolov
CC BY-SA 3.0
2011-09-21T02:23:18.450Z
2011-09-21T20:30:55.203Z
2011-09-21T20:30:55.203Z
Sasho Nikolov
<p>Your conflict measure is called the <a href="http://en.wikipedia.org/wiki/Kendall_tau_distance" rel="nofollow">Kendall tau distance</a>. The total order that minimizes these conflicts is the winner of the <a href="http://en.wikipedia.org/wiki/Kemeny%E2%80%93Young_method" rel="nofollow">Kemeny-Young voting method</a>.  <a href="http://en.wikipedia.org/wiki/Kemeny%E2%80%93Young_method#Calculation_methods" rel="nofollow">Computing the winner</a> of the Kemney-Young voting method is NP-hard.</p>

CC BY-SA 3.0
2011-09-21T05:03:45.877Z
2011-09-21T05:03:45.877Z
Tyson Williams
<p>If you are looking for different approaches/algorithms to the problem, perhaps the right "google keywords" are <strong>Rank aggregation</strong> or <strong>Weighted rank aggregation</strong>.</p>

<p>For example see the paper "<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113.2507&amp;rep=rep1&amp;type=pdf" rel="nofollow">Rank Aggregation Revisited</a>" by C.Dwork, R.Kumar, M.Naor, D.Sivakumar.</p>

<p>The <em>rank aggregation problem</em> is to combine many different rank orderings on the same set of candidates, or alternatives, in order to obtain a “better” ordering. Rank aggregation has been studied extensively in the context of social choice theory, where several “voting paradoxes” have been discovered. The problem also arises in many other settings:</p>

<ul>
<li>Sports and Competition: How to determine the winner of a season, how to rank players or how to compare players from different eras?</li>
<li>Machine Learning: Collaborative filtering and meta-search; Statistics: Notions of Correlation;</li>
<li>Database Middleware: Combining results from multiple databases.</li>
</ul>

<p>...</p>

<p>At the bottom of the article there are plenty of references.</p>

CC BY-SA 3.0
2011-09-21T22:51:43.693Z
2011-09-21T22:51:43.693Z
Marzio De Biasi
<p>Suppose that $k$ different voters have each produced a partial ordering of candidates $1,\ldots,n$. For example, if $k=3$ and $n=4$, the voters may have produced the partial orders</p>

<ul>
<li>$1&lt;2$</li>
<li>$2&lt;1&lt;3&lt;4$</li>
<li>$2&lt;3&lt;1$</li>
</ul>

<p>Our goal is to fuse all these into a single ranking of the candidates in a way that minimizes conflicts. The following seems like a natural way to do this. Given a total order $L$, let $C(i,j)$ be the number of the partial orders which rank $i$ and $j$ in the opposite way from $L$ (i.e., if $L$ ranks $i$ before $j$, $C(i,j)$ equals the number among the $k$ partial orders that rank $j$ before $i$).  We seek to find a total order $L$ which minimizes $\sum_{i&lt;j} C(i,j)$.</p>

<p>This seems like it would be a well-studied problem, but I have been unable to find any references, likely because I'm not aware of the right keywords. Can any one point me towards papers where algorithms for this problem were considered? </p>

CC BY-SA 3.0
2011-09-21T01:31:55.117Z
What is your formal definition of a conflict?
Aaron Sterling
CC BY-SA 3.0
2011-09-21T01:35:08.467Z
I thought I defined it formally in the question. Is it that my definition of $C(i,j)$ is unclear?
morgan
CC BY-SA 3.0
2011-09-21T01:36:50.897Z
Perhaps an example would help. The ranking $1<2<3<4$ has three conflicts with the list in the question: two $(1,2)$-conflicts, one $(1,3)$ conflict, and zero $(1,4),(2,3), (2,4)$ conflicts.
morgan
<ds.algorithms>
Finding a ranking which minimizes the number of conflicts
morgan
# Finding a ranking which minimizes the number of conflicts

(Asked by: username_0 on 2011-09-21)

Suppose that $k$ different voters have each produced a partial ordering of candidates $1,\ldots,n$. For example, if $k=3$ and $n=4$, the voters may have produced the partial orders

* $1<2$
* $2<1<3<4$
* $2<3<1$

Our goal is to fuse all these into a single ranking of the candidates in a way that minimizes conflicts. The following seems like a natural way to do this. Given a total order $L$, let $C(i,j)$ be the number of the partial orders which rank $i$ and $j$ in the opposite way from $L$ (i.e., if $L$ ranks $i$ before $j$, $C(i,j)$ equals the number among the $k$ partial orders that rank $j$ before $i$). We seek to find a total order $L$ which minimizes $\sum\_{i

This seems like it would be a well-studied problem, but I have been unable to find any references, likely because I'm not aware of the right keywords. Can any one point me towards papers where algorithms for this problem were considered?

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: What is your formal definition of a conflict?  
> **username_0**: I thought I defined it formally in the question. Is it that my definition of $C(i,j)$ is unclear?  
> **username_0**: Perhaps an example would help. The ranking $1<2<3<4$ has three conflicts with the list in the question: two $(1,2)$-conflicts, one $(1,3)$ conflict, and zero $(1,4),(2,3), (2,4)$ conflicts.  

---

## 3 answers

### Answer by username_2 on 2011-09-21. Score: 5 | Accepted answer

This is a special case of metric $1$-medians, where the metric space is $S\_n$ (the symmetric group on $n$ elements) with distance function number of inversions (i.e. the distance between two permutations is the number of pairs $i, j: i

This [paper](http://dl.acm.org/citation.cfm?id=1411513) by Ailon, Charikar, and Newman considers this and related problems. The problem you're asking about is called Rank Aggregation in their paper. Look at their intro for more references. The problem is NP-hard. A simple 2-approximation is to pick the best of the given $k$ permutations (i.e. the permutation that minimizes the objective function). Here is a proof:

Let $\pi$ be the optimal permutation and $\pi\_{j^\*}$ the best of $\pi\_1, \ldots, \pi\_k$. For any $i, j \in [k]$, by the triangle inequality, $d(\pi\_i, \pi) + d(\pi\_j, \pi) \geq d(\pi\_i, \pi\_j)$. Sum over all $i, j$, and you get $2n\mathsf{OPT} \geq \sum\_j{\mathsf{ALG}(j)}$, where $\mathsf{ALG(j)}$ is the cost of choosing $\pi\_j$ as the solution, and $\mathsf{OPT}$ is the cost of the optimal solution. Since $\pi\_{j^\*}$ was chosen so that $\mathsf{ALG}(j^\*)$ is minimum over all $\mathsf{ALG}(j)$ for $j \in [k]$, we have $\mathsf{ALG}(j^\*) \leq \sum\_j{\mathsf{ALG}(j)} /n$ and we have $\mathsf{ALG}(j^\*) \leq 2\mathsf{OPT}$.

The paper I referred you to above has another, almost equally simple 2-approximation (but the proof is not that simple, though still not bad). They can show that the bad cases for the two approximation algorithms are different, and taking the better solution of the two gives 11/7 approximation factor.

Then there is also a PTAS by Mathieu and Schudy (Warren sometimes visits this site btw), by a reduction to weighted Minimum Feedback Arc Set in Tournamets (the same reduction is used in the previous paper, I think). Here is the [link](http://www.cs.brown.edu/~ws/papers/fast_journal.pdf)

> **Comments:**
> **username_2**: of course the simple 2-approximation works for finding an approximate median in any metric space  

---

### Answer by username_3 on 2011-09-21. Score: 4

Your conflict measure is called the [Kendall tau distance](http://en.wikipedia.org/wiki/Kendall_tau_distance). The total order that minimizes these conflicts is the winner of the [Kemeny-Young voting method](http://en.wikipedia.org/wiki/Kemeny%E2%80%93Young_method). [Computing the winner](http://en.wikipedia.org/wiki/Kemeny%E2%80%93Young_method#Calculation_methods) of the Kemney-Young voting method is NP-hard.


---

### Answer by username_4 on 2011-09-21. Score: 1

If you are looking for different approaches/algorithms to the problem, perhaps the right "google keywords" are **Rank aggregation** or **Weighted rank aggregation**.

For example see the paper "[Rank Aggregation Revisited](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113.2507&rep=rep1&type=pdf)" by C.Dwork, R.Kumar, M.Naor, D.Sivakumar.

The *rank aggregation problem* is to combine many different rank orderings on the same set of candidates, or alternatives, in order to obtain a “better” ordering. Rank aggregation has been studied extensively in the context of social choice theory, where several “voting paradoxes” have been discovered. The problem also arises in many other settings:

* Sports and Competition: How to determine the winner of a season, how to rank players or how to compare players from different eras?
* Machine Learning: Collaborative filtering and meta-search; Statistics: Notions of Correlation;
* Database Middleware: Combining results from multiple databases.

...

At the bottom of the article there are plenty of references.


---

