MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 said convex combination

It seems to me you should be able to work out a formula for $p_{ij}$ explicitly, by solving that system of linear equations you wrote down. More to the point, you can do this before deciding on what algorithm you're going to use to assign the ranks.

For this solution to correspond to a real-world solution to your problem, it seems to me that the matrix $P = (p_{ij})$ ought to be doubly stochastic (its rows and columns should sum to 1), because everyone should get a rank, and every rank should get a person. If this doesn't happen, you're out of luck.

Once you've done this, your doubly stochastic matrix $P$ can be expressed as a sum convex combination of permutation matrices (this is the Birkhoff-Von Neumann theorem). Each of these permutation matrices corresponds to a rank assignment.

You should be able to come up with your algorithm, then, by finding a constructive proof of Birkhoff-Von Neumann and realizing it with code. I sort of doubt that this would be efficient without further cleverness, but it might be a place to start.

1

It seems to me you should be able to work out a formula for $p_{ij}$ explicitly, by solving that system of linear equations you wrote down. More to the point, you can do this before deciding on what algorithm you're going to use to assign the ranks.

For this solution to correspond to a real-world solution to your problem, it seems to me that the matrix $P = (p_{ij})$ ought to be doubly stochastic (its rows and columns should sum to 1), because everyone should get a rank, and every rank should get a person. If this doesn't happen, you're out of luck.

Once you've done this, your doubly stochastic matrix $P$ can be expressed as a sum of permutation matrices (this is the Birkhoff-Von Neumann theorem). Each of these permutation matrices corresponds to a rank assignment.

You should be able to come up with your algorithm, then, by finding a constructive proof of Birkhoff-Von Neumann and realizing it with code. I sort of doubt that this would be efficient without further cleverness, but it might be a place to start.