Some days ago I have assigned papers to my PC in ESA Track A. I tried to use automatic assignment in EasyChair and this was a rather disappointing experience. Just by running it I understood why some assignments I got as a PC member in previous conferences were so bad - they bad without any good reason. Let me explain what happened this time.
I clicked the automatic assignment button and I got a very unfair assignment. EasyChair wanted to punish 3 of my PC members by giving them 11, 12 and 15 papers from their No list. In EasyChair one can bid Yes, Maybe and No on papers. I found this rather absurd as 15 paper was more than half of the total review load. The question is: Does this poor guy need to get so many Nos in optimal assignment? The short intuitive answer is: most probably no, as there is a lot of freedom in each maximal size matching (by Gallai-Edmonds decomposition).
Hence, in 2 hours I coded my own assignment procedure. I assumed that in the assignment:
- first, I want to maximize the number of papers assigned to Maybes and Yeses,
- second, under the first assumption, I want to maximize the number of papers assigned Yeses.
This can be formalized as a maximum-cost maximum-flow problem:
- connect the source vertex with each PC member with a zero cost edge of capacity equal to review load,
- connect each PC member with each paper with edges of capacity 1 and cost 0 for No, 10000 for Maybe and 10001 for Yes.
- connect each paper with the sink with edge of cost 0 and capacity 3.
I executed it and I got assignment with the same number of Nos - 80 and Maybes -100 as EasyChair. And of course, it was not much more fair than the one given by EasyChair. If you always wondered how EasyChair computes the assignment this is the way. Essentially, there is no reason for this to be fair in any sense. One is optimizing global cost, so it should be clear that locally it can be bad, e.g., some PC members will get bad assignments without any good reason. It can be even worse as one can be getting many Nos due to the execution order of procedure, as there is always a lot of freedom in the optimal matching. It can happen that even if you bid on almost everything you will get all the Nos if all people bid No on the same papers.
There is a solution here - I added third assumption to my procedure:
- zero, no PC member can get more than X Nos, where X is a parameter.
This can be easily incorporated into the max-flow problem. One just needs to split a vertex representing each PC member into three vertices: PC_0, PC_No and PC_NotNo. The maximum-cost maximum-flow problem becomes:
- connect the source vertex with all PC_0 vertices with a zero cost edge of capacity equal to review load,
- connect PC_0 to PC_No with zero cost edge of capacity X,
- connect PC_0 to PC_NotNo with zero cost edge of capacity equal to review load,
- connect PC_No with edges of cost 0 to all papers with No,
- connect PC_NotNo with each paper with edges of capacity 1 and cost 10001 for Maybe and 10001 for Yes.
- connect each paper with sink with edge of cost 0 and capacity 3.
I executed it - the table below shows the number of Maybes in the assignment in dependence on the parameter X.
One striking thing is that there exists an optimal assignment where the poor guy that was getting 15 Nos is getting only 11 Nos. Essentially, there was no reason for giving 15 Nos to this PC member! This probably already happened to many of you ;). I the final assignment I went for X=4 as this actually meant that almost everyone gets 3 Nos and only 2 PC members get 4 Nos. This much fairer assignment costed only 20 Maybes in the quality, what I found a fair cost of being fairer.