[EM] Professorial Office Picking

[Juho]

On Jan 25, 2010, at 8:49 PM, Abd ul-Rahman Lomax wrote:

> 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.

Range style ratings would give more accurate utilities but I used  
Borda style to get rid of strategies. Borda style utilities will  
distort the true utilities somewhat but the end result may still be  
quite fair. I didn't include equal rankings since that would not make  
any big change in the level of distortion. Forcing the voters to  
decide whether A>B or B>A is correct instead of allowing them to vote  
A=B is quite ok. Picking a random order doesn't distort the outcome  
too much even if the voter could not make up his/her mind on which one  
of the two rooms is better. The method is thus already noisy as it is  
and therefore equal rankings might not add very much. If equal  
rankings will not add any complexity to the method they are ok though.  
(DIfferent ways to count the points in case of equal rankings would  
have different impact on the method.)

>
> 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.

I didn't describe the method how to find the winner but I'm quite ok  
with method definitions that specify the ideal winner in a way that  
may lead to problems with computational complexity when implemented,  
if one can approximate the optimal result well enough. In this case  
that means that since the method already has some noise due to the  
Borda based ratings, the noise caused by imperfect algorithms seeking  
the optimal room allocation would probably add only very little extra  
noise. My first choice would therefore be to use a clear definition of  
the ideal solution and then use approximate algorithms to find the  
best result. Do you think there are some "iterative methods" that  
would achieve more accurate results (or would be necessary for  
efficiency or other reasons)?

Juho