I'm not a mathematician but I working on a problem that feels like it an example of a more general kind of problem and I'm hoping that someone might be able to point me in the right direction. 


The problem is trying to find a convex combination of different ways of ranking n items that satisfy certain constraints. Let me be more concrete: Suppose we have $n$ individuals with endowments $b\_1 > b\_2 > b\_3 \ldots b\_n$. There are positions $1 \dots n$, each of which gives a value of $v\_1 > v\_2 > v\_3 \ldots v\_n \ge 0$ that the individuals can be assigned to. 


I want to create a non-deterministic algorithm for assigning individuals to positions that is in some sense "equitable." so that for each individual, their expected proportional value from their positions is equal to their proportional endowment. E.g., suppose we have some method that assigns individual $i$ to position with 1 with probability $p\_{i1}$, to position 2 with probability $p\_{i2}$ and so on, I want it so that the algorithm generates an allocation such that: 


$\forall i, \frac{\sum\_{j=1}^n p\_{ij} v\_j}{\sum\_{j=1}^n v\_j} = \frac{b\_i}{\sum\_{j=1}^n b\_j} $


### Some observations / thoughts:


For this to work even in the n=2 case, we need to constrain $b\_1$ to that it isn't proportionally larger than $v\_1$ (otherwise even always placing individual 1 at position 1 wouldn't be enough). 


I originally thought this could be framed as a linear programming problem, where the goal is to find weights for each of the $n!$ possible orderings. Maybe this would work, but it would be computationally infeasible. 


A particularly nice approach might be one that sequentially assigns positions by having each remaining individual "buy" probability shares with their budget and then draw a winner. Unfortunately, this doesn't have the equitable property above, but I was thinking that perhaps if we thought of the allocation as happening repeatedly, we could give the "losers" (payoff from position too small) a bigger endowment, taken from the "winners" in such a way that expected payoff converges to the equitable outcome. 


Anyway, thanks for reading this far and I appreciate any comments, suggestions, answers etc. 



Equitable Allocation of Individuals to Positions 
This is not a complete answer but too long for a comment. You wrote,



> 
> I originally thought this could be framed as a linear programming problem, where the goal is to find weights for each of the n! possible orderings. Maybe this would work, but it would be computationally infeasible.
> 
> 
> 


Linear programs with this many variables are solved all the time using column generation:


<http://www.columbia.edu/~cs2035/courses/ieor4600.S07/columngeneration.pdf>


In your problem, let variable $q\_k$ denote the probability of using permutation $\pi\_k$, and let variable $p\_{ij}$ denote the marginal probability that agent $i$ is assigned to $j$, so you have a total of $n! + n^2$ variables. Let $\pi\_k(i,j) = 1$ if agent $i$ is assigned to position $j$ in permutation $k$ and zero otherwise. We can relate the $p\_{ij}$'s and $q\_k$'s via $n^2$ constraints of the form


$\sum\_k q\_k \pi\_k(i,j) = p\_{ij} \forall i,j$


Now, assume as Kevin did that $\sum\_i v\_i = \sum\_j b\_j = 1$. Your equity criterion is just $\sum\_j p\_{ij} v\_j = b\_i \forall i$. We obviously must require that $q\_k \geq 0$ for all $k$. Thus the feasible set of these permutations can be written as:


$\sum\_k q\_k = 1$


$p\_{ij} = \sum\_k q\_k \pi\_k (i,j) \forall i,j$


$q\_k \geq 0 \forall k$


$\sum\_j p\_{ij} v\_j = b\_i \forall i$


There are a total of $1 + n^2 + n$ equality constraints and $n!$ inequality constraints, and you have $n! + n^2$ variables. Any basic feasible solution of this set (i.e. a corner point) therefore must have $n! - (n+1)$ of the inequality constraints active, which means that the corner points have only $n+1$ nonzero $q\_k$'s. Thus, if your problem is feasible at all for particular choices of $v$ and $b$, it's possible to find such a set of assignments using at most $n+1$ possible permutations.


You may gain further insight by looking at the dual of this LP -- the primal problem above has $n^2 + n!$ variables, $1 + n^2 + n$ equality constraints, and $n!$ inequality constraints, so its dual will have $n^2 + n!$ constraints, but only $1 + n^2 + n$ variables. Those constraints should have a nice structure to them (something like, one constraint for each permutation, and that constraint sums over all nonzero $\pi\_k(i,j)$'s or something), which would give you a polynomial-time separation oracle for solving the dual LP. There may likely be a way to recover a primal solution from the dual using complementary slackness.


