{"id":616,"date":"2014-08-14T14:50:01","date_gmt":"2014-08-14T14:50:01","guid":{"rendered":"http:\/\/corner.mimuw.edu.pl\/?p=616"},"modified":"2022-09-12T09:46:26","modified_gmt":"2022-09-12T09:46:26","slug":"efficiency-of-random-priority","status":"publish","type":"post","link":"https:\/\/corner.mimuw.edu.pl\/?p=616","title":{"rendered":"Efficiency of Random Priority"},"content":{"rendered":"<p>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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> students to <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> 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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_215bd341a1c138558de0e3c9577c5d55.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> are given by an ordering <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5b6f58405c9d3957f91277c2eae5d78b.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> over the set <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_dd7536794b63bf90eccfd37f9b147d7f.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> 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.<\/p>\n<p>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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b1d96050926731f52181571e9862d8c2.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> telling how much agent <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0cc175b9c0f1b6a831c399e269772661.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> values item <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_865c0c0b4ab0e063e5caa3387c1a8741.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. In this model we can quantify social welfare of an assignment that a mechanism finds. Here, welfare of an assignment\u00a0 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce0c40542f6c33a032dde6426e15197.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is just the sum <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_361e3cb23d720122e89c62831573923b.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. 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.<\/p>\n<p><a href=\"http:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/08\/hardness.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone  wp-image-648\" src=\"http:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/08\/hardness-1024x536.png\" alt=\"hardness\" width=\"546\" height=\"291\" \/><\/a><\/p>\n<p>For items <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_2d0f47c83840ea9047bac0f3e8b72e8f.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> 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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_80e7141eebd5f8442aafd551e54bc6c5.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and therefore the social welfare of RSD is <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_552123cbded49c5f703b278a4e242ed4.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. 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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>? One can see, that in an extreme case with <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8df451ca448a5abed3c0a92e6befe77b.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> the RSD finds welfare of value at least <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_a2f070a31330443ceb0dcf352fe50035.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> (an inclusion maximal matching), so it's not bad either.<\/p>\n<p><strong>0\/1 preferences<\/strong><\/p>\n<p>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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_25b7305962ce35fb963ec301937abdfb.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> value all items 0, but each of them always chooses <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_80e7141eebd5f8442aafd551e54bc6c5.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p>In this model, RSD is a <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b534c05a4b55c86c15b3ce9185c34dee.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>-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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_43c98a64bcde4857b095743482e04281.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> of the algorithm. Some agents and items are removed from the instance, so let <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_54b77460b5a9b541d5e687af4d1993e8.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> be what remains from optimal solution after <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_e358efa489f58062f10dd7316b65649e.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> steps of RSD. Also, let <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_394532dd8e0d5f1dfd0a6ddc18477f2a.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> be the partial matching constructed by RSD after <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_e358efa489f58062f10dd7316b65649e.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> steps, and <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_12629f8b8f57f6fd7c9fa456b22c4e48.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> be its welfare. It can happen that at time <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_e358efa489f58062f10dd7316b65649e.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, an agent does not 1-value any of remaining items, even though he could have 1-valued some of the items initially. Thus let <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5472a294f48e4f4fc4e405d0f28e3f05.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> be the number of agents who 0-value all remaining items. Let <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0cc175b9c0f1b6a831c399e269772661.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> be the agent who is at step <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_43c98a64bcde4857b095743482e04281.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> chosen by RSD to pick an item. With probability <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_cc1e043c1f3ec876ae395f977ab45027.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> agent <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0cc175b9c0f1b6a831c399e269772661.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> 1-values at least one item. If so, then the welfare of RSD increases by 1, i.e., <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_955998432ddb93e54eadd2b6d9c9a4bb.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> Hence [mathbb{E}left[<br \/>\nuleft(RSD^{t+1}<br \/>\night)<br \/>\night]=mathbb{E}left[<br \/>\nuleft(RSD^{t}<br \/>\night)<br \/>\night]+1-frac{mathbb{E}left[z^{t}<br \/>\night]}{n-t}.] What is the expected number of edges we remove from <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b193dfc5e432950bb33b6c4750dc17b7.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>? That is, what is the expected loss <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_6f40b05201766c29a1c5f4c7c1f07dc0.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>? Again, with probability <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_cc1e043c1f3ec876ae395f977ab45027.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> agent <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0cc175b9c0f1b6a831c399e269772661.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> picks an item <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_865c0c0b4ab0e063e5caa3387c1a8741.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> he values 1. Both agent <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0cc175b9c0f1b6a831c399e269772661.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and item <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_865c0c0b4ab0e063e5caa3387c1a8741.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> may belong to <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b193dfc5e432950bb33b6c4750dc17b7.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, in which case <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b193dfc5e432950bb33b6c4750dc17b7.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> loses two edges. Otherwise <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b193dfc5e432950bb33b6c4750dc17b7.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> loses one edge. Now suppose that agent <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0cc175b9c0f1b6a831c399e269772661.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> 0-values all remaining items, which happens with probability <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_23290d0f34fe0071448d85e8e499bafc.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. If <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0cc175b9c0f1b6a831c399e269772661.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is such an agent, then he picks an item at random from all remaining items, so with probability <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b7151ca2474f646e99f32a8cb093ca79.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> agent <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0cc175b9c0f1b6a831c399e269772661.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> picks an item that belongs to <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b193dfc5e432950bb33b6c4750dc17b7.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. If so, then <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b193dfc5e432950bb33b6c4750dc17b7.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> loses 1, and otherwise, <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b193dfc5e432950bb33b6c4750dc17b7.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> does not lose anything. We have <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_960c0a21c45c87f9f0475f9ceec9f4ed.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, so <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_d8f1580e3e19e6e81e26d68fee90d3d7.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and hence the expected decrease is: [\begin{eqnarray*}&amp;&amp;mathbb{E}left[<br \/>\nuleft(OPT^{t}<br \/>\night)-<br \/>\nuleft(OPT^{t+1}<br \/>\night)<br \/>\night] \\ leq &amp;&amp;mathbb{E}left[ 2cdotleft(1-frac{z^{t}}{n-t}<br \/>\night)+frac{z^{t}}{n-t}cdotfrac{<br \/>\nuleft(OPT^{t}<br \/>\night)}{n-t}<br \/>\night] \\ leq &amp;&amp;mathbb{E}left[ 2cdotleft(1-frac{z^{t}}{n-t}<br \/>\night)+frac{z^{t}}{n-t}cdot left(1-frac{z^{t}}{n-t}<br \/>\night)<br \/>\night] \\ leq&amp;&amp;3cdotleft(1-frac{mathbb{E}left[z^{t}<br \/>\night]}{n-t}<br \/>\night). end{eqnarray*}] Therefore, [\begin{align*}mathbb{E}left[<br \/>\nuleft(OPT^{t}<br \/>\night)-<br \/>\nuleft(OPT^{t+1}<br \/>\night)<br \/>\night] &amp;leq 3cdotleft(1-frac{mathbb{E}left[z^{t}<br \/>\night]}{n-t}<br \/>\night) \\ &amp;=3cdotmathbb{E}left[<br \/>\nuleft(RSD^{t+1}<br \/>\night)-<br \/>\nuleft(RSD^{t}<br \/>\night)<br \/>\night],end{align*}] and by summing for <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_e358efa489f58062f10dd7316b65649e.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> from <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_cfcd208495d565ef66e7dff9f98764da.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> to <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> we conclude that [\begin{align*}<br \/>\nuleft(OPT<br \/>\night)&amp;=mathbb{E}left[<br \/>\nuleft(OPT^{0}<br \/>\night)-<br \/>\nuleft(OPT^{n}<br \/>\night)<br \/>\night]\\ &amp;leq3cdotmathbb{E}left[<br \/>\nuleft(RSD^{n}<br \/>\night)-<br \/>\nuleft(RSD^{0}<br \/>\night)<br \/>\night]=3cdot mathbb{E}left[<br \/>\nuleft(RSD<br \/>\night)<br \/>\night].end{align*}]<\/p>\n<p><strong>Connection to online bipartite matching<\/strong><\/p>\n<p>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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_e734521f144304b66f49655ce184ed7d.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>-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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5c0dd6f4dca87b1ba00451e6cd26d49b.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. In fact, it's also possible to use the algorithm of Mahdian and Yan (2013) and this would give a factor of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_f543a5acd742ea9a27578dc4191ba848.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p><strong>Big OPT<\/strong><\/p>\n<p>Now let us go back to the model with arbitrary real valuations from interval <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_d55f1e45c7252980bff6f7f4bcd248dd.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. Here we want to obtain approximation factor that depends on <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_73ad33531c6ee45e4abcdddb1422983d.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> --- for <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5d85f4f314a4261d35455ba2561acf75.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> the ratio should be around <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_6281d67c88fa7a64cf4459449577acad.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, while for <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_a52cac2670727cc5fced04f5e57ff6d1.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> it should be constant. This suggests that we should aim in approximation factor of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_e5818c6b2c34c1263e103f4c5fbe4638.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. Let us first show an upper-bound that cannot be achieved by any mechanism. Take any integer <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and copy <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> times the instance from the Figure.\u00a0 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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b561f8c68c3b4d6e900adcbb4bcfcf35.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, hence no mechanism cannot do better than <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_bf641f2ae1eba07e37e2ab5c8ca1b2b7.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> on the whole instance. Here <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_cc3d0bb48ec79621c276a2a6817a0b9a.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and the number of agents is <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_452c28edf4c111cc8b23336f8ebe1e3e.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> this time. Therefore, asymptotic upper-bound on RSD's welfare is <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_1d3f4aff2a66488674d358476f6debdd.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, where <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is the number of agents. But what is quite interesting, we can prove that RSD is only <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_70398643db9389fa6a6d6beca501b325.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> fraction away from this upper-bound. That is, we show that expected outcome of RSD is at least <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_73a8a6b6001707b4737c8a14fca823b8.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. However, this we shall not prove here. If you are interested from where this shapely constant of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_70398643db9389fa6a6d6beca501b325.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> comes, then please have a look at our <a href=\"http:\/\/arxiv.org\/abs\/1407.3957\" target=\"_blank\" rel=\"noopener noreferrer\">arXiv report<\/a>.<\/p>\n<p><strong>SAGT'14<\/strong><\/p>\n<p>It turns out that this natural problem at the same time was also investigated independently by Aris Filos-Ratsikas, S\u00f8ren Kristoffer Stiil Frederiksen, Jie Zhang. They obtained similar results for the general <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_ccfcd347d0bf65dc77afe01a3306a96b.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> 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.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 &hellip; <a href=\"https:\/\/corner.mimuw.edu.pl\/?p=616\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":8,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/616"}],"collection":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/users\/8"}],"replies":[{"embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=616"}],"version-history":[{"count":47,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/616\/revisions"}],"predecessor-version":[{"id":1121,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/616\/revisions\/1121"}],"wp:attachment":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=616"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=616"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=616"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}