128:
As an example, suppose there are two objects - bread and wine, and two agents - Alice and George. The preference-relation of Alice is {bread,wine} > {bread} > {wine} > {}. If the preference-relation of George is the same, then there are two agreeable subsets: {bread,wine} and {bread}. But
38:
Another use case is when the citizens in some city want to elect a committee from a given pool of candidates, such that all citizens agree that the subset of elected candidates is at least as good as the subset of non-elected ones. Subject to that, the committee size should be as small as possible.
30:
An example situation in which this problem arises is when a family goes on a trip and has to decide which items to take. Since their car is limited in size, they cannot pick all items, so they have to agree on a subset of items which are most important. If they manage to find a subset of items such
1371:
Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut (2020). "Consensus
Halving for Sets of Items". In Chen, Xujin; Gravin, Nikolai; Hoefer, Martin; Mehta, Ruta (eds.).
508:
1101:. For any fixed of additive agents, there exists a pseudopolynomial time for this problem; but if the number of agents is not fixed, then the problem is strongly NP-hard. There exists a polynomial-time O(log
844:
779:
727:
445:
920:
987:
1045:
313:
275:
1058:
For agents with general monotone preferences, there is no algorithm that computes a smallest agreeable set using a polynomial number of queries. Moreover, for every constant
663:
853:≥ 3 agents with responsive preferences, a necessarily-agreeable subset of this size might not exist. However, there always exists a necessarily-agreeable subset of size
556:
227:
satisfies (*) for all agents, then it is necessarily-agreeable. The converse implication holds if the agents' preference relations on indivisible objects are strict.
23:
is a subset of items that is considered, by all people in a certain group, to be at least as good as its complement. Finding a small agreeable subset is a problem in
137:
If the agents' preference relations on the subsets are given, it is easy to check whether a subset is agreeable. But often, only the agents' preference relations on
1078:) of the minimum, even with only one agent. This is tight: there exists a polynomial-time algorithm that finds an agreeable subset with size at most O(
669:-coloring just defined, there are two adjacent vertices with the same color. In other words, there are two disjoint subsets such that, a single agent
447:, and it is tight (for some preferences this is the smallest size of an agreeable subset). The proof for two agents is constructive. The proof for
732:
When there are any number of agents with additive utilities, or a constant number of agents with monotone utilities, an agreeable subset of size
1401:
1200:
458:
1326:
Aziz, Haris; Gaspers, Serge; MacKenzie, Simon; Walsh, Toby (2015). "Fair assignment of indivisible objects under ordinal preferences".
800:
735:
683:
401:
1133:
926:
which is a power of 3, there exist ordinal preferences of 3 agents such that every necessarily-agreeable subset has size at least
129:
if George's preference-relation is {bread,wine} > {wine} > {bread} > {}, then the only agreeable subset is {bread,wine}.
1151:- a variant of fair division in which the pieces of the resource are given to pre-determined groups rather than to individuals.
31:
that all family members agree that it is at least as good as the subset of items remaining at home, then this subset is called
673:
prefers each of them to its complement. But this contradicts the above lemma. Hence there must be an agreeable subset of size
1475:
1470:
729:
can be computed in polynomial time, using polynomially-many queries of the form "which of these two subsets is better?".
856:
1480:
990:
24:
1148:
1378:. Lecture Notes in Computer Science. Vol. 12495. Cham: Springer International Publishing. pp. 384–397.
1128:
1055:
In many cases, there may exist an agreeable subset that is much smaller than the worst-case upper bound.
929:
142:
141:
are given. In this case, it is often assumed that the agents' preferences are not only monotone but also
1138:
1003:
680:
When there are at most three agents, and their preferences are responsive, an agreeable subset of size
284:
246:
1228:
997:
74:
609:
106:
1446:
1379:
1373:
1353:
1335:
1308:
1266:
1240:
1178:
1285:
517:
1438:
1397:
1258:
1196:
1098:
1430:
1389:
1345:
1300:
1250:
1188:
1090:
243:
Consider first a single agent. In some cases, an agreeable subset should contain at least
1175:
Proceedings of the Twenty-Fifth
International Joint Conference on Artificial Intelligence
1143:
782:
1286:"The undercut procedure: An algorithm for the envy-free division of indivisible items"
169:
according to the responsive set extension of their preferences on individual objects.
1464:
1450:
1312:
1270:
1170:
1114:
The agreeable subset problem was studied with additional constraint represented by a
281:
objects are identical. Moreover, there always exists an agreeable subset containing
1357:
599:
566:
objects, and two subsets are connected iff they are disjoint. If there is a vertex
452:
922:, and such a set can be computed in polynomial time. On the other hand, for every
1393:
1349:
1254:
1192:
1434:
1304:
1442:
1262:
1418:
1171:"Assigning a small agreeable set of indivisible items to multiple players"
586:. Otherwise, we can define a color for each agent and color each vertex
1115:
68:. Each agent is characterized by a preference-relation on subsets of
78:- an agent always weakly prefers a set to all its subsets. A subset
1384:
1245:
1183:
503:{\displaystyle k:={\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }}
1340:
1066:
queries and finds an agreeable subset with expected size at most
839:{\displaystyle {\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }}
774:{\displaystyle {\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }}
722:{\displaystyle {\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }}
440:{\displaystyle {\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }}
1284:
Brams, Steven J.; Kilgour, D. Marc; Klamler, Christian (2011).
1093:, deciding whether there exists an agreeable subset of size
1097:/2 is NP-hard; the proof is by reduction from the balanced
1177:. IJCAI'16. New York, New York, USA: AAAI Press: 489–495.
793:
When there are two agents with responsive preferences, a
398:
objects, there always exists an agreeable subset of size
235:
What is the smallest agreeable subset that we can find?
558:, that is, the graph whose vertices are all subsets of
1229:"Computing a small agreeable set of indivisible items"
105:
If an agent's preference relation is represented by a
1006:
1000:
that computes a necessarily-agreeable subset of size
932:
859:
803:
738:
686:
612:
520:
461:
404:
287:
249:
1227:Manurangsi, Pasin; Suksompong, Warut (2019-03-01).
781:can be found in polynomial time using results from
16:
Concept in the field of computational social choice
1039:
981:
914:
838:
773:
721:
657:
550:
502:
439:
307:
269:
915:{\displaystyle m/2+(n+1)\lceil 4n\log {m}\rceil }
846:exists and can be computed in polynomial time.
831:
806:
766:
741:
714:
689:
495:
470:
432:
407:
315:objects. This follows from the following lemma:
216:; at least three of the five best objects in
8:
909:
889:
302:
288:
264:
250:
212:; at least two of the three best objects in
1419:"Agreeable sets with matroidal constraints"
1062:, there is no algorithm that makes at most
72:. The preference-relation is assumed to be
231:Worst-case bounds on agreeable subset size
172:A closely related property of subsets is:
1383:
1339:
1244:
1182:
1027:
1010:
1005:
971:
963:
954:
936:
931:
904:
863:
858:
830:
829:
811:
805:
804:
802:
765:
764:
746:
740:
739:
737:
713:
712:
694:
688:
687:
685:
611:
519:
494:
493:
475:
469:
468:
460:
431:
430:
412:
406:
405:
403:
294:
286:
256:
248:
1161:
64:agents who have to choose a subset of
1423:Journal of Combinatorial Optimization
1051:Computing a smallest agreeable subset
337:are disjoint, then at least one of S\
7:
1222:
1220:
1218:
1216:
1214:
1212:
982:{\displaystyle m/2+(\log _{3}{m})/4}
204:To satisfy property (*), the subset
387:and the preferences are monotone).
1040:{\displaystyle m/2+O({\sqrt {m}})}
208:should contain the best object in
14:
1134:Participatory budgeting algorithm
600:chromatic number of Kneser graphs
390:This can be generalized: For any
308:{\displaystyle \lceil m/2\rceil }
270:{\displaystyle \lceil m/2\rceil }
1169:Suksompong, Warut (2016-07-09).
277:objects. An example is when all
113:, then for any agreeable subset
1417:Gourvès, Laurent (2019-04-01).
989:. Both proofs use theorems on
582:is an agreeable subset of size
1034:
1024:
968:
947:
886:
874:
658:{\displaystyle m-2(m-k)+2=n+1}
634:
622:
570:such that all agents prefer S\
545:
527:
1:
789:Necessarily-agreeable subsets
1394:10.1007/978-3-030-64946-3_27
1350:10.1016/j.artint.2015.06.002
1255:10.1016/j.artint.2018.10.001
1193:10.1016/j.artint.2018.10.001
133:Necessarily-agreeable subset
1105:) approximation algorithm.
991:Discrepancy of permutations
598:to S\V. By the theorem on
25:computational social choice
1497:
1375:Web and Internet Economics
1149:Fair division among groups
797:-agreeable subset of size
665:; this means that, in the
602:, the chromatic number of
594:with an agent who prefers
1435:10.1007/s10878-018-0327-1
1305:10.1007/s00355-011-0599-1
1293:Social Choice and Welfare
1129:Envy-free item allocation
551:{\displaystyle KG(m,m-k)}
1328:Artificial Intelligence
1233:Artificial Intelligence
1041:
983:
916:
840:
775:
723:
659:
552:
504:
441:
309:
271:
1139:Multiwinner elections
1089:Even for agents with
1042:
984:
917:
841:
776:
724:
660:
553:
505:
442:
310:
272:
157:if all agents prefer
155:necessarily agreeable
90:if all agents prefer
1476:Social choice theory
1471:Fair item allocation
1004:
998:randomized algorithm
930:
857:
801:
736:
684:
610:
518:
514:be the Kneser graph
459:
402:
285:
247:
359:(this is because S\
107:subadditive utility
60:objects. There are
1481:Discrepancy theory
1091:additive utilities
1086:) of the minimum.
1037:
979:
912:
836:
771:
719:
655:
548:
500:
437:
305:
267:
196:objects for agent
188:contains at least
139:individual objects
1403:978-3-030-64946-3
1202:978-1-57735-770-4
1144:Consensus halving
1099:partition problem
1032:
827:
783:consensus halving
762:
710:
491:
428:
239:Agreeable subsets
1488:
1455:
1454:
1414:
1408:
1407:
1387:
1368:
1362:
1361:
1343:
1323:
1317:
1316:
1290:
1281:
1275:
1274:
1248:
1224:
1207:
1206:
1186:
1166:
1046:
1044:
1043:
1038:
1033:
1028:
1014:
988:
986:
985:
980:
975:
967:
959:
958:
940:
921:
919:
918:
913:
908:
867:
845:
843:
842:
837:
835:
834:
828:
823:
812:
810:
809:
780:
778:
777:
772:
770:
769:
763:
758:
747:
745:
744:
728:
726:
725:
720:
718:
717:
711:
706:
695:
693:
692:
664:
662:
661:
656:
557:
555:
554:
549:
509:
507:
506:
501:
499:
498:
492:
487:
476:
474:
473:
446:
444:
443:
438:
436:
435:
429:
424:
413:
411:
410:
351:is agreeable to
323:, if two subses
319:For every agent
314:
312:
311:
306:
298:
276:
274:
273:
268:
260:
48:Agreeable subset
21:agreeable subset
1496:
1495:
1491:
1490:
1489:
1487:
1486:
1485:
1461:
1460:
1459:
1458:
1416:
1415:
1411:
1404:
1370:
1369:
1365:
1325:
1324:
1320:
1288:
1283:
1282:
1278:
1226:
1225:
1210:
1203:
1168:
1167:
1163:
1158:
1125:
1111:
1053:
1002:
1001:
996:There exists a
950:
928:
927:
855:
854:
849:When there are
813:
799:
798:
791:
748:
734:
733:
696:
682:
681:
608:
607:
516:
515:
477:
457:
456:
414:
400:
399:
386:
379:
372:
365:
350:
343:
336:
329:
283:
282:
245:
244:
241:
233:
192:/2 of the best
135:
52:There is a set
50:
45:
17:
12:
11:
5:
1494:
1492:
1484:
1483:
1478:
1473:
1463:
1462:
1457:
1456:
1429:(3): 866–888.
1409:
1402:
1363:
1318:
1276:
1208:
1201:
1160:
1159:
1157:
1154:
1153:
1152:
1146:
1141:
1136:
1131:
1124:
1121:
1120:
1119:
1110:
1107:
1052:
1049:
1036:
1031:
1026:
1023:
1020:
1017:
1013:
1009:
978:
974:
970:
966:
962:
957:
953:
949:
946:
943:
939:
935:
911:
907:
903:
900:
897:
894:
891:
888:
885:
882:
879:
876:
873:
870:
866:
862:
833:
826:
822:
819:
816:
808:
790:
787:
768:
761:
757:
754:
751:
743:
716:
709:
705:
702:
699:
691:
654:
651:
648:
645:
642:
639:
636:
633:
630:
627:
624:
621:
618:
615:
547:
544:
541:
538:
535:
532:
529:
526:
523:
497:
490:
486:
483:
480:
472:
467:
464:
451:agents uses a
434:
427:
423:
420:
417:
409:
384:
377:
370:
363:
357:
356:
348:
341:
334:
327:
304:
301:
297:
293:
290:
266:
263:
259:
255:
252:
240:
237:
232:
229:
202:
201:
176:(*) For every
134:
131:
49:
46:
44:
41:
15:
13:
10:
9:
6:
4:
3:
2:
1493:
1482:
1479:
1477:
1474:
1472:
1469:
1468:
1466:
1452:
1448:
1444:
1440:
1436:
1432:
1428:
1424:
1420:
1413:
1410:
1405:
1399:
1395:
1391:
1386:
1381:
1377:
1376:
1367:
1364:
1359:
1355:
1351:
1347:
1342:
1337:
1333:
1329:
1322:
1319:
1314:
1310:
1306:
1302:
1298:
1294:
1287:
1280:
1277:
1272:
1268:
1264:
1260:
1256:
1252:
1247:
1242:
1238:
1234:
1230:
1223:
1221:
1219:
1217:
1215:
1213:
1209:
1204:
1198:
1194:
1190:
1185:
1180:
1176:
1172:
1165:
1162:
1155:
1150:
1147:
1145:
1142:
1140:
1137:
1135:
1132:
1130:
1127:
1126:
1122:
1117:
1113:
1112:
1108:
1106:
1104:
1100:
1096:
1092:
1087:
1085:
1081:
1077:
1073:
1069:
1065:
1061:
1056:
1050:
1048:
1029:
1021:
1018:
1015:
1011:
1007:
999:
994:
992:
976:
972:
964:
960:
955:
951:
944:
941:
937:
933:
925:
905:
901:
898:
895:
892:
883:
880:
877:
871:
868:
864:
860:
852:
847:
824:
820:
817:
814:
796:
788:
786:
784:
759:
755:
752:
749:
730:
707:
703:
700:
697:
678:
676:
672:
668:
652:
649:
646:
643:
640:
637:
631:
628:
625:
619:
616:
613:
605:
601:
597:
593:
589:
585:
581:
577:
573:
569:
565:
561:
542:
539:
536:
533:
530:
524:
521:
513:
488:
484:
481:
478:
465:
462:
454:
450:
425:
421:
418:
415:
397:
393:
388:
383:
376:
369:
362:
354:
347:
340:
333:
326:
322:
318:
317:
316:
299:
295:
291:
280:
261:
257:
253:
238:
236:
230:
228:
226:
221:
219:
215:
211:
207:
199:
195:
191:
187:
184:, the subset
183:
179:
175:
174:
173:
170:
168:
164:
160:
156:
152:
148:
144:
140:
132:
130:
126:
124:
120:
116:
112:
108:
103:
101:
97:
93:
89:
85:
81:
77:
76:
71:
67:
63:
59:
55:
47:
42:
40:
36:
34:
28:
26:
22:
1426:
1422:
1412:
1374:
1366:
1331:
1327:
1321:
1299:(2–3): 615.
1296:
1292:
1279:
1236:
1232:
1174:
1164:
1102:
1094:
1088:
1083:
1079:
1075:
1071:
1067:
1063:
1059:
1057:
1054:
995:
923:
850:
848:
794:
792:
731:
679:
674:
670:
666:
603:
595:
591:
587:
583:
579:
575:
571:
567:
563:
559:
511:
453:Kneser graph
448:
395:
391:
389:
381:
374:
367:
360:
358:
352:
345:
338:
331:
324:
320:
278:
242:
234:
224:
223:If a subset
222:
217:
213:
209:
205:
203:
197:
193:
189:
185:
181:
177:
171:
166:
162:
158:
154:
150:
146:
138:
136:
127:
122:
118:
114:
110:
104:
99:
95:
91:
87:
83:
79:
73:
69:
65:
61:
57:
53:
51:
37:
32:
29:
20:
18:
795:necessarily
394:agents and
180:in 1, ...,
145:. A subset
56:containing
43:Definitions
1465:Categories
1385:2007.06754
1246:1606.08077
1239:: 96–114.
1184:1606.08077
1156:References
1109:Extensions
510:, and let
153:is called
143:responsive
86:is called
1451:254654045
1443:1573-2886
1341:1312.6546
1334:: 71–92.
1313:253844146
1271:124836295
1263:0004-3702
961:
910:⌉
902:
890:⌈
629:−
617:−
578:, then S\
540:−
380:contains
366:contains
303:⌉
289:⌈
265:⌉
251:⌈
109:function
88:agreeable
33:agreeable
1123:See also
832:⌋
807:⌊
767:⌋
742:⌊
715:⌋
690:⌊
496:⌋
471:⌊
433:⌋
408:⌊
75:monotone
1358:1408197
1116:matroid
220:; etc.
1449:
1441:
1400:
1356:
1311:
1269:
1261:
1199:
1082:/ log
455:. Let
373:and S\
121:) ≥ u(
1447:S2CID
1380:arXiv
1354:S2CID
1336:arXiv
1309:S2CID
1289:(PDF)
1267:S2CID
1241:arXiv
1179:arXiv
1047:.
344:or S\
125:)/2.
1439:ISSN
1398:ISBN
1259:ISSN
1197:ISBN
1074:log
993:.
330:and
117:, u(
1431:doi
1390:doi
1346:doi
1332:227
1301:doi
1251:doi
1237:268
1189:doi
952:log
899:log
606:is
590:of
574:to
161:to
149:of
94:to
82:of
35:.
19:An
1467::
1445:.
1437:.
1427:37
1425:.
1421:.
1396:.
1388:.
1352:.
1344:.
1330:.
1307:.
1297:39
1295:.
1291:.
1265:.
1257:.
1249:.
1235:.
1231:.
1211:^
1195:.
1187:.
1173:.
1070:/(
785:.
677:.
466::=
102:.
27:.
1453:.
1433::
1406:.
1392::
1382::
1360:.
1348::
1338::
1315:.
1303::
1273:.
1253::
1243::
1205:.
1191::
1181::
1118:.
1103:n
1095:m
1084:m
1080:m
1076:m
1072:c
1068:m
1064:m
1060:c
1035:)
1030:m
1025:(
1022:O
1019:+
1016:2
1012:/
1008:m
977:4
973:/
969:)
965:m
956:3
948:(
945:+
942:2
938:/
934:m
924:m
906:m
896:n
893:4
887:)
884:1
881:+
878:n
875:(
872:+
869:2
865:/
861:m
851:n
825:2
821:n
818:+
815:m
760:2
756:n
753:+
750:m
708:2
704:n
701:+
698:m
675:k
671:i
667:n
653:1
650:+
647:n
644:=
641:2
638:+
635:)
632:k
626:m
623:(
620:2
614:m
604:G
596:V
592:G
588:V
584:k
580:V
576:V
572:V
568:V
564:k
562:-
560:m
546:)
543:k
537:m
534:,
531:m
528:(
525:G
522:K
512:G
489:2
485:n
482:+
479:m
463:k
449:n
426:2
422:n
419:+
416:m
396:m
392:n
385:1
382:V
378:2
375:V
371:2
368:V
364:1
361:V
355:.
353:i
349:2
346:V
342:1
339:V
335:2
332:V
328:1
325:V
321:i
300:2
296:/
292:m
279:m
262:2
258:/
254:m
225:T
218:S
214:S
210:S
206:T
200:.
198:i
194:k
190:k
186:T
182:m
178:k
167:T
165:\
163:S
159:T
151:S
147:T
123:S
119:T
115:T
111:u
100:T
98:\
96:S
92:T
84:S
80:T
70:S
66:S
62:n
58:m
54:S
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.