278:
choose his favorite alternative(s) among the remaining alternatives. If more than one alternative remains after taking the preferences of all agents into account, RSD uniformly randomizes over those alternatives. In the item division setting mentioned earlier, the alternatives correspond to the allocations of items to agents. Each agent has large equivalence classes in his preference, since he is indifferent between all the allocations in which he gets the same item.
171:
RSD gives a 1/3 chance of every object to each agent (because their preferences over sure objects coincide), and a profile of expected utility vector (0.6, 0.4, 0.4). But assigning item y to Alice for sure and items x,z randomly between Bob and Carl yields the expected utility vector (0.8, 0.5, 0.5).
277:
RSD can be defined for the more general setting in which the group has to select a single alternative from a set of alternatives. In this setting, RSD works as follows: First, randomly permute the agents. Starting with the set of all alternatives, ask each agent in the order of the permutation to
70:(or fewer) different items among them. Since the items are indivisible, some partners will necessarily get the less-preferred items (or no items at all). RSD attempts to insert fairness into this situation in the following way. Draw a
281:
In this general setting, if all agents have strict preferences over the alternatives, then RSD reduces to drawing a random agent and choosing the alternative that the agent likes best. This procedure is known as
86:
when the number of items is at most the number of agents, since you only have one opportunity to pick an item, and the obviously dominant strategy in this opportunity is to pick the best available item.
186:
When the rankings of the agents over the objects are drawn uniformly at random, the probability that the allocation given by RSD is ex-ante PE approaches zero as the number of agents grows.
246:
One way is to define a quota for each agent (such that the sum of quotas equals the number of objects), and let each agent in turn pick items up to his/her quota. This procedure remains
290:
when preferences are strict. When agents can have weak preferences, however, no procedure that extends RD (which includes RSD) satisfies both efficiency and strategyproofness.
253:
Another way is to let each agent pick a single object, and then do another round in which each agent picks a single object, until all objects are taken; this leads to the
74:
of the agents from the uniform distribution. Then, let them successively choose an object in that order (so the first agent in the ordering gets first pick and so on).
240:
68:
48:
373:
Abdulkadiroglu, Atila; Sonmez, Tayfun (1998). "Random Serial
Dictatorship and the Core from Random Endowments in House Allocation Problems".
94:(PE) outcome. Moreover, in an assignment problem, every deterministic PE assignment is the outcome of SD for some ordering of the agents.
506:
Brandl, Florian; Brandt, Felix; Suksompong, Warut (2016). "The impossibility of extending random dictatorship to weak preferences".
98:
562:
557:
197:(which implies ex-ante envy-freeness), but it is not truthful. It is impossible to enjoy the advantages of both mechanisms:
109:
than ex-post Pareto-efficiency). As an example, suppose there are three agents, three items and the VNM utilities are:
254:
304:
190:
311:
300:
24:
242:
objects, some agents may get more than one object. There are several ways to extend RSD to this case.
465:
533:
515:
488:
390:
83:
71:
258:
201:
With cardinal additive utility functions, no mechanism is symmetric, truthful and ex-ante PE.
525:
480:
446:
417:
382:
355:
339:
265:
173:
91:
205:
101:
over random allocations, i.e., lotteries over objects (Note that ex-ante envy-freeness is
343:
314:
describes RSD is a general rule for social choice - not necessarily for item allocation.
225:
53:
33:
408:
Manea, Mihai (2009). "Asymptotic ordinal inefficiency of random serial dictatorship".
551:
450:
287:
247:
194:
180:
537:
179:
Moreover, when agents have ordinal rankings, RSD fails even the weaker property of
529:
208:
functions, no mechanism is sd-efficient, strategyproof, and treats equals equally.
437:
Zhou, Lin (1990). "On a conjecture by gale about one-sided matching problems".
359:
303:
compares RSD to other procedures for solving the same problem, such as the
422:
492:
394:
484:
386:
520:
105:
than ex-post envy-freeness, but ex-ante Pareto-efficiency is
346:(2001). "A New Solution to the Random Assignment Problem".
286:(RD), and is the unique procedure that is efficient and
466:"Manipulation of schemes that mix voting with chance"
228:
56:
36:
193:, is sd-efficient (which implies ex-post PE) and sd-
97:
However, RSD is not ex-ante PE when the agents have
257:procedure. This procedure is fairer, but it is not
234:
62:
42:
27:- dividing indivisible items fairly among people.
8:
519:
421:
227:
55:
35:
111:
324:
264:Both procedures are special cases of a
334:
332:
330:
328:
172:So the original utility vector is not
7:
14:
99:Von Neumann-Morgenstern utilities
1:
530:10.1016/j.econlet.2016.01.028
90:RSD always yields an ex-post
451:10.1016/0022-0531(90)90070-Z
255:round-robin item allocation
579:
439:Journal of Economic Theory
348:Journal of Economic Theory
23:(RSD), is a procedure for
21:Random serial dictatorship
305:probabilistic-serial rule
222:When there are more than
191:probabilistic-serial rule
189:An alternative rule, the
250:, but it is very unfair.
218:More objects than agents
50:partners have to divide
563:Fair division protocols
464:Gibbard, Allan (1977).
273:General decision-making
360:10.1006/jeth.2000.2710
312:dictatorship mechanism
301:fair random assignment
236:
64:
44:
25:fair random assignment
558:Randomized algorithms
410:Theoretical Economics
237:
65:
45:
226:
54:
34:
284:random dictatorship
232:
84:truthful mechanism
72:random permutation
60:
40:
19:(RP), also called
508:Economics Letters
340:Bogomolnaia, Anna
235:{\displaystyle n}
169:
168:
63:{\displaystyle n}
43:{\displaystyle n}
570:
542:
541:
523:
503:
497:
496:
470:
461:
455:
454:
434:
428:
427:
425:
405:
399:
398:
370:
364:
363:
336:
266:picking sequence
241:
239:
238:
233:
174:Pareto efficient
112:
92:Pareto efficient
69:
67:
66:
61:
49:
47:
46:
41:
578:
577:
573:
572:
571:
569:
568:
567:
548:
547:
546:
545:
505:
504:
500:
485:10.2307/1911681
468:
463:
462:
458:
436:
435:
431:
407:
406:
402:
387:10.2307/2998580
372:
371:
367:
338:
337:
326:
321:
296:
275:
224:
223:
220:
215:
213:Generalizations
206:ordinal utility
80:
52:
51:
32:
31:
17:Random priority
12:
11:
5:
576:
574:
566:
565:
560:
550:
549:
544:
543:
498:
479:(3): 665–681.
456:
429:
416:(2): 165–197.
400:
365:
323:
322:
320:
317:
316:
315:
308:
295:
292:
274:
271:
270:
269:
262:
251:
231:
219:
216:
214:
211:
210:
209:
202:
167:
166:
163:
160:
157:
153:
152:
149:
146:
143:
139:
138:
135:
132:
129:
125:
124:
121:
118:
115:
79:
76:
59:
39:
13:
10:
9:
6:
4:
3:
2:
575:
564:
561:
559:
556:
555:
553:
539:
535:
531:
527:
522:
517:
513:
509:
502:
499:
494:
490:
486:
482:
478:
474:
467:
460:
457:
452:
448:
444:
440:
433:
430:
424:
419:
415:
411:
404:
401:
396:
392:
388:
384:
380:
376:
369:
366:
361:
357:
353:
349:
345:
344:Moulin, Hervé
341:
335:
333:
331:
329:
325:
318:
313:
309:
306:
302:
298:
297:
293:
291:
289:
288:strategyproof
285:
279:
272:
267:
263:
260:
259:strategyproof
256:
252:
249:
248:strategyproof
245:
244:
243:
229:
217:
212:
207:
203:
200:
199:
198:
196:
192:
187:
184:
182:
181:sd-efficiency
177:
175:
164:
161:
158:
155:
154:
150:
147:
144:
141:
140:
136:
133:
130:
127:
126:
122:
119:
116:
114:
113:
110:
108:
104:
100:
95:
93:
88:
85:
77:
75:
73:
57:
37:
28:
26:
22:
18:
511:
507:
501:
476:
473:Econometrica
472:
459:
442:
438:
432:
423:10419/150127
413:
409:
403:
378:
375:Econometrica
374:
368:
351:
347:
310:The page on
299:The page on
283:
280:
276:
221:
188:
185:
178:
170:
106:
102:
96:
89:
81:
29:
20:
16:
15:
445:: 123–135.
552:Categories
521:1510.07424
381:(3): 689.
354:(2): 295.
319:References
78:Properties
514:: 44–47.
195:envy-free
82:RSD is a
294:See also
107:stronger
30:Suppose
538:4917725
493:1911681
395:2998580
123:Item z
536:
491:
393:
120:Item y
117:Item x
103:weaker
534:S2CID
516:arXiv
489:JSTOR
469:(PDF)
391:JSTOR
204:With
128:Alice
156:Carl
526:doi
512:141
481:doi
447:doi
418:hdl
383:doi
356:doi
352:100
162:0.2
148:0.2
142:Bob
134:0.8
554::
532:.
524:.
510:.
487:.
477:45
475:.
471:.
443:52
441:.
412:.
389:.
379:66
377:.
350:.
342:;
327:^
183:.
176:.
165:0
151:0
137:0
540:.
528::
518::
495:.
483::
453:.
449::
426:.
420::
414:4
397:.
385::
362:.
358::
307:.
268:.
261:.
230:n
159:1
145:1
131:1
58:n
38:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.