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.