By David Eppstein & Vijay Vazirani
No, not to make theoreticians rich! Besides, who will buy your papers anyway? (Quite the opposite, you will be lucky if you can convince someone to take them for free, just for sake of publicity!) What we are proposing is a market in which no money changes hands – a matching market – for matching papers to conferences.
First, a short preamble on how the idea emerged.
Preamble (by Vijay): Soon after my recent Simons talk on Matching Markets, I sent its url to Al Roth. Obviously, I wasn’t expecting a return email. However, the perfect gentleman and ultimate scholar that Al is, he did reply, and mentioned that he did not like my “definition” of matching markets and said, “I guess I would say matching markets are markets because they aggregate information that is held by the participants, which is what markets do (even if they don’t use prices to do it..).” This hit me like lightening from the sky – suddenly it crystallized the innate intuition about markets which I had formed through work on algorithmic aspects of markets! I thanked Al profusely and added, “This definitely helps in me get the right perspective on the notion!”
About a week ago, while updating my talk for a seminar at Columbia University, I included this beautiful insight in it and then a thought occurred: Each PC meeting involves aggregation of information from a large number of agents: PC members as well as external experts. Hence, isn’t a conference a matching market? Excitedly, I sent this question to Al. He replied, “… the conference process, matching papers to conferences, is a market and a particular conference might be a marketplace … ”
When I returned home, my esteemed colleague, David Eppstein, stunned me by declaring that he had thought of a market relevant to our field in which no money changes hands. I immediately knew he was thinking of the conference process. But he got to it out of the blue … and not the long process it took me!
Back to the idea: In the past, matching markets have brought immense efficiency and order in allocation problems in which use of money is considered repugnant, the prime examples being matching medical residents to hospitals, kidney exchange, and assignment of students of a large city to its schools.
At present we are faced with massive inefficiencies in the conference process – numerous researchers are trapped in unending cycles of submit … get reject … incorporate comments … resubmit — often to the next deadline which has been conveniently arranged a couple of days down the road so the unwitting participants are conditioned into mindlessly keep coming back for more, much like Pavlov’s dog.
We are proposing a matching market approach to finally obliterate this madness. We believe such a market is feasible using the following ideas. No doubt our scheme will have some drawbacks; however, as should be obvious, the advantages far outweigh them.
First, for co-located symposia within a larger umbrella conference, such as the
conferences within ALGO or FCRC, the following process should be a no-brainer:
1). Ensure a common deadline for all symposia; denote the latter by S.
2). Let R denote the set of researchers who wish to submit one paper to a symposium in this umbrella conference – assume that researchers submitting more than one paper will have multiple names, one for each submission. Each researcher will provide a strict preference order over the subset of symposia to which they wish to submit their paper. Let G denote the bipartite graph with vertex sets (R, S) and an edge (r, s) only if researcher r chose symposium s.
3). The umbrella conference will have a large common PC with experts representing all of its symposia. The process of assigning papers to PC members will of course use G in a critical way.
Once papers are reviewed by PC members and external reviewers, each symposium will rank its submissions using its own criteria of acceptance. We believe the overhead of ranking each paper multiple times is minimal since that is just an issue of deciding how “on-topic” a paper is – an easy task once the reviews of the paper are available.
4). Finally, using all these preference lists, a researcher-proposing stable matching is computed using the Gale-Shapley algorithm. As is well-known, this mechanism will be dominant strategy incentive compatible for researchers.
With a little extra effort, a similar scheme can also be used for a group of conferences at diverse locations but similar times, such as some of the annual summer theory conferences, STOC, ICALP, ESA, STAC, WADS/SWAT, etc.
Are we not using Gale-Shapley now? The authors propose to a conference, the conference accepts or rejects, and then the authors propose to the conference that is next in their preference list.
If we’re doing Gale–Shapley now, we’re not getting the benefits of instant turnaround and reduced reviewer load (from pooling) that this suggestion would provide. But I don’t think what we’re doing now is really close enough to Gale–Shapley. Currently authors typically propose to the conference with the next deadline among the ones they find acceptable, not to the one next down among their preferences. And doing Gale-Shapley properly would involve conferences rejecting already-accepted papers to make room for latecomers, something we don’t do now.
Some conferences like ICDM already do something like this, allowing rejected papers to be automatically routed to workshops.
I am interested in a different but closely related market for serving on the PCs. On the one hand, serving on a PC bestows prestige (which can be crucial for careers). On the other hand, it is a lot of work and people who have enough prestige might decline serving. To me serving on a PC appears to be a privilege that is not easy to come by unless you are a “star” or “part of the club.” (Maybe these are misconceptions that more knowledgeable people can dispel.) Do you think this is an “efficient” market, or a “fair” market? It appears to me that there are cartels in this market (the aforementioned “clubs”). I would love to see a discussion on whether people think this is true, and if so, how to come up with mechanisms that improve the situation.
I think that the idea of applying Gale–Shapley to the allocation of accepted papers to conferences is a neat idea. However, I also suspect that it will never be applied to TCS conferences. TCS is, by far, the most conservative community in the whole CS.
There are a couple of issues:
1. Reviewers typically use different standards for different conferences and these differences are not merely a matter of topic but of quality – given the pressure of submitted papers to a conference, some levels in the reviewing scale are more important than others: The scale would have to stretch in different places depending on the conference, which makes the task of reviewing a paper in this combined scenario much more difficult, requiring much finer scales than our conference software is suited for.
(In reviewing for a top quality conference we don’t have to worry that much about how far below threshold a paper lands – crude scales there are fine – on the other hand in reviewing for a lower quality conference one would not have to worry about the distinctions among high-rated papers from the joint submission. (For example, I have been on a PC for a good conference where one of the top-rated papers was appropriately rejected from a previous, conference.)
2. There is another need for a matching algorithm like Gale-Shapley that becomes even more important in such a scenario: matching papers to PC members with appropriate expertise and judgement.
I have used conference software that tries to do this by actually running Gale-Shapley using bid values from PC members. The assignment is often awful. The last time I was PC chair, the overlap in the number of proposed paper assignments via the algorithm versus what I ended up with was remarkably small. (We find the same thing when we use G-S as a first cut at TA assignments.)
The general problem of paper assignment for PC members is a thorny one, because the judgement of PC members has to be made in a very short time with very little information and the cost of gaining more information is very high. I think that a lot of the randomness of PCs is down to noise inherent in this process. (For example, I have heard of largely overlapping papers that have had disjoint sets of reviewers.)
This is the biggest problem for someone who would normally submit to a more specialized conference, because instead of being guaranteed to be reviewed by experts, they run the risk of being reviewed by someone without the right expertise.