[EM] Professorial Office Picking

[Abd ul-Rahman Lomax]

At 05:59 AM 1/25/2010, Juho wrote:
>Here's one simple approach.
>
>- all voters rank all the rooms
>- use Borda like personal utility values => last room = 0 points, 
>one but last = 1 point etc. (also other than this kind of linear 
>scale could be used)
>- find the room allocation that gives the highest sum of utilities
>- if there is a tie one can use seniority to break it
>     - the utility values of each voters are multiplied by some 
> seniority factor and then summed up again
>     - the factors could be quite small if one just wants to break 
> the ties (e.g. 1.0001, 1.0002)
>
>This tie breaking approach is intended to work so that if there is 
>for example some room that all consider to be the best then that 
>room would be given to the most senior voter.
>
>Any chances to work?

Sure. But equal ranking must be allowed, otherwise noise is 
introduced. Borda with equal ranking (and therefore empty ranks, 
otherwise equal ranked votes are reduced in strength) is Range. Why 
not just use Range, allowing greater precision. One could use a Range 
method with N*R resolution, where the "Borda" version has N equal to 1.

The allocation problem as "highest sum of utilities" is NP-hard, 
though, I believe. I suspect that an iterative method would be 
better. Use an approval method, which will divide up voters into 
blocks. Then use more sophisticated analysis on each block. If you 
are the only one to approve a particular room, perhaps you get the 
room! So you would not over-approve at the first iteration. Standard 
approval strategy when there is iteration.