Matchings are one of the most basic primitives used in the area of mechanism design. Whenever we need to assign items to agents we view it as a matching problem. Of course, plenty of variations differing in constraints and objectives can be considered, but let us look at the simplest variant possible. We need to assign students to dorms. Students have preferences over dorms. We, the administration, would like to find an allocation that would meet students' preferences as much as possible. We cannot use money in deploying the mechanism. This problem have been considered many times in the literature, but in a setting where preferences of student are given by an ordering over the set of dorms. In this setting it was shown that there exists only one truthful, non-bossy and neutral mechanism. The unique mechanism is called Serial Dictatorship and it works as follows. First, agents are sorted in a fixed order, and then the first agent chooses his favorite item, the next agent chooses his favorite item among remaining items, and so on. Moreover, its randomized variant called Random Serial Dictatorship (RSD), which scans according to a random order, possesses another nice properties of being symmetric and ex post efficient, i.e., it never outputs Pareto dominated outcomes. This mechanism is more often called Random Priority, and hence the title of this entry.

However, one can imagine a setting where the preferences of an agent are not given by an ordering of items, but rather where we are given values telling how much agent values item . In this model we can quantify social welfare of an assignment that a mechanism finds. Here, welfare of an assignment  is just the sum . Together with Piotr Sankowski and Qiang Zhang we decided to investigate the problem of comparing the social welfare obtained by RSD with the optimum offline welfare. By optimum offline welfare we mean the maximum weighted matching in the underlying graph. We assume that when the RSD proposes an agent to make a his choice, then he will pick an item he values the most. We also assume that an agent resolves ties randomly. At first sight, it might seem like obtaining any meaningful result on approximation factor of RSD is not possible. Just look at the example in the Figure.

For items each agent has value 0, that's why these edges are not in the Figure. The optimal social welfare is obviously 1. However, the first agent approached by RSD will always pick item , and therefore the social welfare of RSD is . To overcome this problem, we asked two questions. First, what if valuations of agents are always either 0 and 1? Here the hard example does not apply anymore, if assumed that ties are resolved randomly. Second, what if the optimal social welfare is big compared to ? One can see, that in an extreme case with the RSD finds welfare of value at least (an inclusion maximal matching), so it's not bad either.

0/1 preferences

In case the preferences are 0 and 1, we can look only at the 1-edges in the underlying graph. Then we are given an unweighted graph and we just want to maximize the size of constructed matching. We stress here, that the random tie-breaking rule is crucial here. That is, we require that when RSD asks an agent that has 0 value for all remaining items, then this agent picks one of the items at random. Without this assumption we can see that the hard example from the figure still works --- suppose each agents value all items 0, but each of them always chooses .

In this model, RSD is a -approximation, and below we show why. Instead of clunky ``agent has value 1 for an item'', we shall say shortly ``agent 1-values an item''. Consider step of the algorithm. Some agents and items are removed from the instance, so let be what remains from optimal solution after steps of RSD. Also, let be the partial matching constructed by RSD after steps, and be its welfare. It can happen that at time , an agent does not 1-value any of remaining items, even though he could have 1-valued some of the items initially. Thus let be the number of agents who 0-value all remaining items. Let be the agent who is at step chosen by RSD to pick an item. With probability agent 1-values at least one item. If so, then the welfare of RSD increases by 1, i.e., Hence [mathbb{E}left[
uleft(RSD^{t+1}
ight)
ight]=mathbb{E}left[
uleft(RSD^{t}
ight)
ight]+1-frac{mathbb{E}left[z^{t}
ight]}{n-t}.] What is the expected number of edges we remove from ? That is, what is the expected loss ? Again, with probability agent picks an item he values 1. Both agent and item may belong to , in which case loses two edges. Otherwise loses one edge. Now suppose that agent 0-values all remaining items, which happens with probability . If is such an agent, then he picks an item at random from all remaining items, so with probability agent picks an item that belongs to . If so, then loses 1, and otherwise, does not lose anything. We have , so , and hence the expected decrease is: [egin{eqnarray*}&&mathbb{E}left[
uleft(OPT^{t}
ight)-
uleft(OPT^{t+1}
ight)
ight] \ leq &&mathbb{E}left[ 2cdotleft(1-frac{z^{t}}{n-t}
ight)+frac{z^{t}}{n-t}cdotfrac{
uleft(OPT^{t}
ight)}{n-t}
ight] \ leq &&mathbb{E}left[ 2cdotleft(1-frac{z^{t}}{n-t}
ight)+frac{z^{t}}{n-t}cdot left(1-frac{z^{t}}{n-t}
ight)
ight] \ leq&&3cdotleft(1-frac{mathbb{E}left[z^{t}
ight]}{n-t}
ight). end{eqnarray*}] Therefore, [egin{align*}mathbb{E}left[
uleft(OPT^{t}
ight)-
uleft(OPT^{t+1}
ight)
ight] &leq 3cdotleft(1-frac{mathbb{E}left[z^{t}
ight]}{n-t}
ight) \ &=3cdotmathbb{E}left[
uleft(RSD^{t+1}
ight)-
uleft(RSD^{t}
ight)
ight],end{align*}] and by summing for from to we conclude that [egin{align*}
uleft(OPT
ight)&=mathbb{E}left[
uleft(OPT^{0}
ight)-
uleft(OPT^{n}
ight)
ight]\ &leq3cdotmathbb{E}left[
uleft(RSD^{n}
ight)-
uleft(RSD^{0}
ight)
ight]=3cdot mathbb{E}left[
uleft(RSD
ight)
ight].end{align*}]

Connection to online bipartite matching

As we can see, in the analysis the main problem for RSD are agents who have value 0 for remaining items. If we could assume, that such an agent would reveal the fact that he 0-values remaining items, then we could discard this agent, and the above analysis would give a -approximation. But in this model, we could actually implement a mechanism based on the RANKING algorithm of Karp, Vazirani, Vazirani, and this would give us approximation of . In fact, it's also possible to use the algorithm of Mahdian and Yan (2013) and this would give a factor of .

Big OPT

Now let us go back to the model with arbitrary real valuations from interval . Here we want to obtain approximation factor that depends on --- for the ratio should be around , while for it should be constant. This suggests that we should aim in approximation factor of . Let us first show an upper-bound that cannot be achieved by any mechanism. Take any integer , and copy times the instance from the Figure.  Let agents 0-value items from different chunks, so that social welfare of any mechanism is the sum of welfares in all chunks. On any chunk no mechanism can get outcome better than , hence no mechanism cannot do better than on the whole instance. Here , and the number of agents is this time. Therefore, asymptotic upper-bound on RSD's welfare is , where is the number of agents. But what is quite interesting, we can prove that RSD is only fraction away from this upper-bound. That is, we show that expected outcome of RSD is at least . However, this we shall not prove here. If you are interested from where this shapely constant of comes, then please have a look at our arXiv report.

SAGT'14

It turns out that this natural problem at the same time was also investigated independently by Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Jie Zhang. They obtained similar results for the general valuations. Both their and our papers are accepted to SAGT'14, and we will have a joint presentation of the results. So if you are going to the symposium, then please give us a pleasure of attending our talk.