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.
| X | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| #Maybes | 120 | 116 | 112 | 109 | 106 | 104 | 102 | 100 | 100 |
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.
Nice post and solution...but why are you using EasyChair to begin with? 🙂
ESA is traditionally run on EasyChair, but is there a better solution?
HotCRP (http://read.seas.harvard.edu/~kohler/hotcrp/) is a popular alternative to EasyChair. I don't know how the matching algorithm works there though.
There is a much better procedure that I used when I chaired a conference: ask each submitting author to specify 3 pc members who would be suitable reviewers, then assign each paper to one of the 3 to balance load. This avoids a whole lot of pointless work by the pc.
How did it work? Were the PC members happy about the papers they got? I would not be sure that the authors would actually know well the areas of expertise of 25 PC members.
In which language and will you publish it, say, on Gihub, under a free license?
I implemented it in C++. I will try to publish it, but this requires a longer HOWTO, as one needs to manually transfer the bids from EasyChair.
When you talked about "fairness", I am thinking about the well-known notion of "proportional fairness" in resource allocation, while we know that a market equilibrium in Fisher market with linear utilities is a proportional-fair allocation.
So I am wondering if the following algorithm can work.
1) Cast each PC member's choice into a linear utility as follows: YES for a paper means weight C_1, MAYBE means weight C_2, and NO means weight EPSILON, where C_1 > C_2 > EPSILON >=0.
2) Compute the market equilibrium using the Eisenberg-Gale program (or using a combinatorial algorithm by Devanur et al).
3) Use the market equilibrium as a probability distribution for randomly assigning papers among PC members.
I think that implementing any notion of fairness would be better that what is currently done in EasyChair. Most probably the one you propose as well. However, to check one would need to implement it and test.
Thanks for a thoughtful post. Perhaps it's a good time to agree what algorithm we should use and what should be considered fair. To me, it is not about the NUMBER (of say "no papers" that I am assigned to) but the RATIO. I usually tried to skim through all papers and give "yes" and "maybe" to as many papers as I can, sometimes to the paper that I don't really want to review. I would not be fair if I get the same number of no-papers as another PC member who just gave yes and maybe to those papers he or she was familiar with. The latter seems to require less effort on bidding and on reviewing.
On one hand, any notion of fairness would be better that the current solution that does not contain any fairness. On the other hand, my approach is probably not the best solution. It was constructed under time pressure B). Anyway, isn't your bidding strategy the result of being accustomed to the poor assignment procedure in EasyChair? You know that if you bid only on your expertise you will get a bad assignment, so you bid on more? Optimally, a PC chair would like to see truthful bids from PC members :), and current EasyChair procedure is not truthful. I do not believe that the RATIO approach is the right one. When composing a PC I was aware that some people I invited will most probably bid on less papers than the other, as there will be less papers from their area of expertise. Still I wanted to have them in the PC as otherwise we will not cover some areas. Shall they get more NO papers? Would they agree to be on PC if I told them that I will give them more NOs? Actually, some people I wanted very much to be on PC declined giving the reason that they will not be able to review all the papers assigned to them, because they knew how the assignment works. Hence, RATIO fairness would not bethe right solution for them, i.e., for people covering more exotic topics in the PC.