Recently, while working on a project, I encountered an algorithmic problem that I had been stuck on for quite some time. It would be great to hear ideas about possible approaches (right now, I haven’t even been able to come up with a polynomial-time algorithm) or an idea to show its reduction from some NP-hard problem.
Consider a single-voter election where a set of candidates C1, C2, …, Cn are participating. The voter’s preference profile is represented by a permutation of these candidates — this permutation encodes the order from most to least preferred.
In addition to the preference order, we are given a cost matrix A of size n × (n − 1), where:
A[i][j] = cost of the campaign to shift candidate Ci by j positions upward/downward in the permutation.
That is, if candidate Ci currently appears in position p, then moving it to position (p — j) (i.e., moving it up by j ranks) or moving it to position (p + j) incurs a cost of A[i][j]. Note that the relative order of any other candidate does not change in this single operation. So, we may pay a cost of A[3][2] to convert the order {C1, C3, C5, C2, C4} to {C1, C5, C2, C3, C4}.
The goal is to make candidate C1 the top-ranked candidate in the preference profile by performing a sequence of shifts (possibly involving other candidates too) while minimizing the total cost.
Formally: Find the minimum total cost required to rearrange the permutation such that candidate C1 occupies the first position. (The ranking of other candidates does not matter.)
Please let me know if any part of the statement feels ambiguous. I am looking forward to even discuss if you have any ideas or thoughts on a possible solution.
Auto comment: topic has been updated by Soumojitkgp (previous revision, new revision, compare).
Presumably, costs are non-negative? Is it okay to move someone "too far"? i.e. if C1 is second from the top and A[1][1] is expensive but A[1][2] is cheap, can we use the cheaper option to move C1 to the top, or would it require a down-then-up sequence?
Yes, all costs are non-negative. We also make the following practical assumptions on the cost matrix:
Monotonicity: ( A[i][j] >= A[i][j'] ) whenever ( j >= j' ). (Intuitively, shifting a candidate by a larger distance should never be cheaper.)
Submodularity: (A[i][x + y] <= A[i][x] + A[i][y]). (In other words, combining two consecutive shifts should not cost more than performing them separately.)
Under the monotonicity assumption, it is never optimal to move a candidate “too far”. Under the submodularity assumption, it is never optimal to shift the same candidate multiple times consecutively.
That makes things easier. I think I can intuit the form of the optimal solution, though I can't quite make the exchange argument rigorously. It should be clear we should never move an enemy up or C1 down. Say the initial list begins E1,...,Em,C1 for enemies E1 to Em.
Claim: there is an optimal sequence in which each enemy is shifted at most once, and in the downward direction, and these happen in decreasing order of index, i.e. a move of Ei happens after a move of Ej iff i<j. There can be any number of upward moves of C1 interspersed between these. My intuition for this is that it is only harmful for Ei and Ej to be leapfrogging each other, so we should preserve the relative ordering of enemies.
If we accept the claim, we can search this subspace of sequences for optimal cost in O(n^3) time by doing DP where the sub problem dp[i][j] is the optimal cost to solve when the list begins with E1,...,Ei and C1 is at position j>i and we are only allowed to shift C1 and E1 through Ei.