190:
Brams and Kaplan study the problem of allocating cabinet ministries among parties. There is a coalition of parties; each party has a different number of seats in the parliament; larger parties should be allocated more ministries or more prestigious ministries. This is a special case of
239:
in the following sense: an agent is always better-off if one or more of his positions in the sequence are improved (e.g, Alice is better-off in the sequence ABBA than in BABA). Both properties are still true with three or more agents, as long as they make truthful
195:
with different entitlements. A possible solution to this problem is to determine a picking sequence, based on the different entitlements, and let each party pick a ministry in turn. Such a solution is used in
Northern Ireland, Denmark and the European parliament.
211:) if, at each point, he picks his best item. If agents have complete information on each other's preferences (as is common among parties), it may not be rational for them to choose truthfully; it may be better for them to make
49:
ABBA - Alice picks one item, then Bob picks two items, then Alice receives the remaining item. This is intuitively even more "fair" than ABAB, since, in ABAB, Bob is always behind of Alice, while ABBA is more
297:- the fractional number of items each agent is entitled to. This is the entitlement divided by the divisor (e.g, for an agent with an entitlement of 10 out of 201, the quota is 10*15/201 ~ 0.75 items).
513:
O'Leary, Brendan; Grofman, Bernard; Elklit, Jorgen (2005). "Divisor
Methods for Sequential Portfolio Allocation in Multi-Party Executive Bodies: Evidence from Northern Ireland and Denmark".
243:
With three or more agents who make strategic choices, a picking-sequence might lead to inefficient allocations (i.e, the subgame-perfect equilibrium might not be Pareto-efficient).
119:
66:
Privacy: the agents do not have to reveal their entire valuation function or even their entire ranking. They only have to reveal what item is the best for them in each step.
32:
agents. One way to allocate the items is to let one agent select a single item, then let another agent select a single item, and so on. A picking-sequence is a sequence of
203:
on bundles of items. This means that, at each point in the picking sequence, there is a single remaining item which is the "best item" for the agent. An agent is called
46:
ABAB - Alice picks one item, then Bob picks one item, then Alice again, then Bob again. This is more "fair" than AABB since it lets Bob more chance to get a better item.
290:- the sum of the entitlements divided by the number of items (e.g, if the sum of all entitlements is 201, and there are 15 items to share, then the divisor is 201/15).
333:
Schoolyard games often need to select "teams". When using the "ABBA" selection, the "A" team will declare "first pick" and the B team will declare "Second-Two":
149:
that maps the rankings to monetary values (e.g, for each agent, his best item is worth for him x dollars, his second-best item is worth for him y dollars, etc).
257:- picking items truthfully is a dominant strategy. Therefore, there exists a subgame-perfect equilibrium which is Pareto optimal, and the game is monotonic.
334:
63:
Simplicity: it is very easy for the agents to understand how the protocol works and what they should do in each step - just pick the best item.
182:
scoring function, and each ranking is equally probable, the "round robin" sequence (ABABAB...) attains the maximal expected sum-of-utilities.
459:
383:
611:
319:
224:
152:
The allocator does not know the rankings of the agents, but he knows that all rankings are random draws from a given
130:
How should the picking sequence be selected? Bouveret and Lang study this question under the following assumptions:
306:
Picking sequences can be used to find allocations that satisfy a strong fairness and efficiency condition called
370:
Sylvain
Bouveret and Yann Chevaleyre and Nicolas Maudet, "Fair Allocation of Indivisible Goods". Chapter 12 in:
271:
153:
70:
39:
As an example, suppose 4 items have to be divided between Alice and Bob. Some possible picking sequences are:
307:
164:
200:
84:
175:
welfare (sum of utilities) or the expected egalitarian welfare (minimum utility) in various settings.
192:
21:
587:
561:
530:
495:
266:
Given the agents' different rights, what would be a fair picking sequence? Brams suggests to use
254:
579:
455:
379:
139:
322:
protocol is a special case of a picking sequence in which the sequence is cyclic: 1, 2, ...,
571:
522:
485:
477:
414:
410:
279:
232:
135:
372:
Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016).
220:
275:
160:
253:
For two agents, there exists a simple modification of the picking-sequence which is a
605:
591:
526:
499:
534:
373:
391:
179:
172:
36:
agent-names, where each name determines what agent is the next to pick an item.
575:
452:
Mathematics and
Democracy: Designing Better Voting and Fair-Division Procedures
583:
549:
481:
428:
404:
145:
The agents may have different rankings on the items, but there is a common
199:
Brams assumes that each agent has a strict ordering on the items, and has
550:"Competitive equilibrium for almost all incomes: existence and fairness"
246:
With three or more agents who make strategic choices, the game might be
490:
468:
Brams, Steven J.; Kaplan, Todd R. (2004). "Dividing the
Indivisible".
43:
AABB - Alice picks two items, then Bob picks the two remaining items.
406:
A general elicitation-free protocol for allocating indivisible goods
566:
59:
A picking-sequence has several merits as a fair division protocol:
250:, i.e, an agent might do worse by picking earlier in the sequence.
274:. The two most commonly used methods are the ones proposed by
355:' The Win-Win Solution: Guaranteeing Fair Shares to Everybody
231:
With two agents, both truthful and strategic choices lead to
178:
Kalinowski et al show that, when there are two agents with a
430:
A social welfare optimal sequential allocation procedure
171:
They show picking-sequences that maximize the expected
77:
reports, each of which includes a number between 1 and
87:
113:
219:) choices. Thus, the picking sequence induces a
454:. Princeton, NJ: Princeton University Press.
353:Steven Brams and Alan D. Taylor (1999–2000).
159:The goal of the allocator is to maximize the
8:
272:apportionment of congress seats among states
366:
364:
138:function (this implies that the items are
565:
554:Autonomous Agents and Multi-Agent Systems
489:
103:
86:
375:Handbook of Computational Social Choice
345:
282:. Both methods start in the same way:
515:American Journal of Political Science
444:
442:
440:
415:10.5591/978-1-57735-516-8/ijcai11-024
223:and it is interesting to analyze its
7:
335:List of traditional children's games
186:Fairness with different entitlements
235:allocations. Moreover, the game is
114:{\displaystyle \Theta (m\log {m})}
88:
81:, so that the total complexity is
14:
548:Segal-Halevi, Erel (2020-02-20).
527:10.1111/j.0092-5853.2005.00118.x
262:Determining the picking-sequence
470:Journal of Theoretical Politics
270:, similar to the ones used for
28:items have to be divided among
378:. Cambridge University Press.
227:. Several results are proved:
108:
91:
1:
320:round-robin item allocation
225:subgame-perfect equilibrium
628:
576:10.1007/s10458-020-09444-z
357:. New York: W. W. Norton.
482:10.1177/0951629804041118
450:Steven J. Brams (2008).
154:probability distribution
71:communication complexity
612:Fair division protocols
308:competitive equilibrium
302:Competitive equilibrium
165:social welfare function
201:responsive preferences
115:
116:
193:fair item assignment
126:Welfare maximization
85:
22:fair item assignment
392:free online version
73:: it requires only
255:truthful mechanism
134:Each agent has an
111:
20:is a protocol for
140:independent goods
619:
596:
595:
569:
545:
539:
538:
510:
504:
503:
493:
465:
446:
435:
434:
433:. AAAI-13. 2013.
425:
419:
418:
401:
395:
389:
368:
359:
358:
350:
280:Thomas Jefferson
233:Pareto efficient
147:scoring function
136:additive utility
120:
118:
117:
112:
107:
18:picking sequence
627:
626:
622:
621:
620:
618:
617:
616:
602:
601:
600:
599:
547:
546:
542:
512:
511:
507:
467:
466:. Adapted from
462:
449:
447:
438:
427:
426:
422:
403:
402:
398:
386:
371:
369:
362:
352:
351:
347:
342:
316:
304:
268:divisor methods
264:
221:sequential game
188:
128:
83:
82:
57:
12:
11:
5:
625:
623:
615:
614:
604:
603:
598:
597:
540:
505:
460:
436:
420:
396:
384:
360:
344:
343:
341:
338:
315:
312:
303:
300:
299:
298:
293:Calculate the
291:
286:Calculate the
276:Daniel Webster
263:
260:
259:
258:
251:
244:
241:
187:
184:
169:
168:
161:expected value
157:
150:
143:
127:
124:
123:
122:
110:
106:
102:
99:
96:
93:
90:
67:
64:
56:
53:
52:
51:
47:
44:
13:
10:
9:
6:
4:
3:
2:
624:
613:
610:
609:
607:
593:
589:
585:
581:
577:
573:
568:
563:
559:
555:
551:
544:
541:
536:
532:
528:
524:
520:
516:
509:
506:
501:
497:
492:
487:
483:
479:
475:
471:
463:
461:9780691133218
457:
453:
448:Chapter 9 in
445:
443:
441:
437:
432:
431:
424:
421:
416:
412:
408:
407:
400:
397:
393:
387:
385:9781107060432
381:
377:
376:
367:
365:
361:
356:
349:
346:
339:
337:
336:
331:
329:
326:, 1, 2, ...,
325:
321:
313:
311:
309:
301:
296:
292:
289:
285:
284:
283:
281:
277:
273:
269:
261:
256:
252:
249:
248:non-monotonic
245:
242:
238:
234:
230:
229:
228:
226:
222:
218:
214:
213:sophisticated
210:
206:
202:
197:
194:
185:
183:
181:
176:
174:
166:
162:
158:
155:
151:
148:
144:
141:
137:
133:
132:
131:
125:
104:
100:
97:
94:
80:
76:
72:
68:
65:
62:
61:
60:
54:
48:
45:
42:
41:
40:
37:
35:
31:
27:
23:
19:
557:
553:
543:
518:
514:
508:
473:
469:
451:
429:
423:
405:
399:
374:
354:
348:
332:
327:
323:
317:
305:
294:
287:
267:
265:
247:
236:
216:
212:
208:
204:
198:
189:
177:
170:
146:
129:
78:
74:
58:
38:
33:
29:
25:
17:
15:
521:: 198–211.
491:10036/26974
173:utilitarian
567:1705.04212
476:(2): 143.
340:References
55:Advantages
24:. Suppose
592:254232282
584:1573-7454
560:(1): 26.
500:154854134
237:monotonic
217:strategic
101:
89:Θ
50:balanced.
606:Category
314:See also
240:choices.
209:truthful
163:of some
288:divisor
205:sincere
590:
582:
535:547519
533:
498:
458:
382:
330:, ...
588:S2CID
562:arXiv
531:S2CID
496:S2CID
295:quota
180:Borda
580:ISSN
456:ISBN
380:ISBN
318:The
278:and
69:Low
572:doi
523:doi
486:hdl
478:doi
411:doi
98:log
608::
586:.
578:.
570:.
558:34
556:.
552:.
529:.
519:49
517:.
494:.
484:.
474:16
472:.
439:^
409:.
363:^
310:.
142:).
16:A
594:.
574::
564::
537:.
525::
502:.
488::
480::
464:.
417:.
413::
394:)
390:(
388:.
328:n
324:n
215:(
207:(
167:.
156:.
121:.
109:)
105:m
95:m
92:(
79:m
75:m
34:m
30:n
26:m
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.