161:: the agents are ordered in some arbitrary order (e.g. by seniority), and each agent in turn picks the best remaining house by his/her preferences. This algorithm is obviously SP. If the agents' preferences are strict, then it finds a PE allocation. However, it may be very unfair towards the agents who pick last. It can be made fairer (in expectation) by choosing the order uniformly at random; this leads to the mechanism called
306:
allocation, in which the maximum number of agents envied by a single agent is minimized. Madathil, Misra and Sethia prove that it is NP-hard even when each agent values at most 2 houses, every house is approved by a constant number of agents, and the maximum allowed envy is just 1. The proof is by
408:
allocation, in which the number of non-envious agents is maximized. Kamiyama, Manurangsi and
Suksompong. prove that, under common complexity theoretic assumption, this problem is hard to approximate. In particular, if NP cannot be solved in subexponential time, then it cannot be approximated to
354:, all houses must be assigned, so an allocation is EF iff each agent gets a house with a highest value. Therefore, it is possible to reduce the original graph to an unweighted graph, in which each agent is adjacent only to his highest-valued houses, and look for a perfect matching in this graph.
365:, the above algorithm may not work, since not all houses must be assigned: even if a single house is most-preferred by all agents, there may exist a complete EF allocation in which this specific house is not assigned. Gan, Suksompong and Voudouris
207:, the primary efficiency requirement is maximizing the sum of utilities. Finding a house allocation maximizing the sum of utilities is equivalent to finding a maximum-weight matching in a weighted bipartite graph; it is also called the
393:, and they only envy their neighbors in that network. Beynier, Chevaleyre, Gourves, Harutyunyan, Lesca, Maudet and Wilczynski study the problem of deciding whether a complete local-envy-free allocation exists for
43:, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are
283:) problem. Madathil, Misra and Sethia prove that it is NP-hard even when each agent values at most 2 houses, and W-hard when parameterized by the number of envious agents. The proof is by reduction from
191:
consider an extended setting in which some agents already own a house while some others are house-less. Their mechanism is IR, PE and SP. They present two algorithms that implement this mechanism.
172:
When each agent already owns a house, fairness considerations are less important, it is more important to guarantee to agents that they will not lose from participating (IR). The
517:
460:
491:
434:
543:
268:
allocation of maximum cardinality and minimum cost (where each edge has a pre-specified cost for society). Aigner-Horev and Segal-Halevi present a polytime algorithm.
275:
allocation, in which the number of envious agents is minimized. Kamiyama, Manurangsi and
Suksompongprove that it is NP-hard. The proof is by reduction from the
55:. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as
545:
it is trivial to approximate: just give one agent his favorite house, and allocate the other agents arbitrarily). The proof is by reduction from the
250:
allocation exists. This holds iff there exists a matching that saturates all the agents; this can be decided in polynomial time by just finding a
88:: each agent values each house at either 1 (which means that the agent likes the house), or 0 (which means that the agent dislikes the house).
1015:
Beynier, Aurélie; Chevaleyre, Yann; Gourvès, Laurent; Harutyunyan, Ararat; Lesca, Julien; Maudet, Nicolas; Wilczynski, Anaëlle (2019-09-01).
942:
152:, the primary efficiency requirement in house allocation is PE. There are various algorithms attaining a PE allocation in various settings.
817:
Segal-Halevi, Erel; Aigner-Horev, Elad (2022). "Envy-free matchings in bipartite graphs and their applications to fair division".
1073:
162:
463:
599:- each agent must get a single object. Randomization is allowed. The allocation should be fair and efficient in expectation.
1068:
251:
368:
present a polynomial-time algorithm that decides, in polynomial time, whether a complete EF allocation exists for any
593:- each agent must get a single object. The goal is to maximize the sum of valuations, or minimize the sum of costs.
81:). The agents may have different preferences over the houses. They may express their preferences in various ways:
312:
288:
178:
algorithm is the unique algorithm which guarantees IR, PE and SP. With strict preferences, TTC finds the unique
21:
937:. AAMAS '23. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 2673–2675.
605:- each agent must get a single object and pay a price; the allocation of objects+prices should be envy-free.
308:
959:
870:
764:
596:
284:
166:
91:
40:
555:
51:. When agents already own houses (and may trade them with other agents), the problem is often called a
614:
157:
17:
496:
439:
1044:
997:
971:
908:
882:
844:
826:
710:
608:
590:
569:
469:
412:
238:
209:
221:
Algorithmic problems related to fairness of the matching have been studied in several contexts.
522:
201:, that is, their predictions do not depend of the order in which the assignments are realized.
1036:
989:
938:
900:
794:
745:
702:
661:
611:- some agents may remain unallocated, as long as they do not like any of the allocated houses.
261:
allocation of maximum cardinality. Aigner-Horev and Segal-Halevi present a polytime algorithm.
174:
134:
118:
1028:
981:
935:
Proceedings of the 2023 International
Conference on Autonomous Agents and Multiagent Systems
892:
836:
784:
776:
737:
692:
651:
559:
exists. Kamiyama, Manurangsi and
Suksompong prove that it is NP-complete, by reduction from
187:
107:
32:
728:
Roth, Alvin E. (1982-01-01). "Incentive compatibility in a market with indivisible goods".
229:
680:
602:
390:
376:. Their algorithm uses, as a subroutine, an algorithm for finding an inclusion-minimal
332:
140:
Individual rationality (IR) - no agent should lose from participating in the algorithm.
137:(SP) - each agent has an incentive to report his/her true preferences to the algorithm.
57:
780:
114:
Several considerations may be important in designing algorithms for house allocation.
1062:
1001:
985:
930:
912:
848:
741:
377:
233:
128:
124:
1048:
714:
580:
allocation of maximum cardinality. The runtime complexity of this problem is open.
323:, and can be solved efficiently when agents have "extremal intervals" preferences.
299:, and can be solved efficiently when agents have "extremal intervals" preferences.
121:(PE) - no other allocation is better for some agents and not worse to all agents.
560:
179:
1032:
896:
840:
389:
allocation exists. Local envy-freeness means that the agents are located on a
1040:
1016:
993:
904:
798:
749:
706:
665:
697:
28:
656:
639:
573:
exists. Kamiyama, Manurangsi and
Suksompong present a polytime algorithm.
958:
Gan, Jiarui; Suksompong, Warut; Voudouris, Alexandros A. (2019-09-01).
789:
929:
Madathil, Jayakrishnan; Misra, Neeldhara; Sethia, Aditi (2023-05-30).
869:
Kamiyama, Naoyuki; Manurangsi, Pasin; Suksompong, Warut (2021-07-01).
242:
in this graph. The following algorithmic problems have been studied.
96:: each agent ranks the houses from best to worst. The ranking may be
127:- can be defined in various ways, for example, envy-freeness (EF) -
976:
887:
831:
110:: each agent assigns a non-negative numeric value to each house.
681:"Housing Markets with Indifferences: A Tale of Two Mechanisms"
466:
is true, then it cannot be approximated to within a factor of
685:
Proceedings of the AAAI Conference on
Artificial Intelligence
165:. The mechanism is PE ex-post, but it is not PE ex-ante; see
39:
is the problem of assigning objects to people with different
335:. The following algorithmic problems have been studied.
155:
Probably the simplest algorithm for house allocation is
931:"The Complexity of Minimizing Envy in House Allocation"
169:
for other randomized mechanisms which are ex-ante PE.
525:
499:
472:
442:
415:
638:
Abdulkadiroğlu, Atila; Sönmez, Tayfun (1999-10-01).
1017:"Local envy-freeness in house allocation problems"
537:
511:
485:
454:
428:
8:
960:"Envy-freeness in house allocation problems"
871:"On the complexity of fair house allocation"
617:- each agent may get any number of objects.
331:, the graph of agents and houses becomes a
205:In computer science and operations research
765:"Consistency in house allocation problems"
315:when parameterized by the total number of
291:when parameterized by the total number of
1021:Autonomous Agents and Multi-Agent Systems
975:
886:
830:
788:
696:
655:
524:
498:
477:
471:
441:
420:
414:
311:on cubic graphs. However, the problem is
16:For the problem of allocating seats in a
640:"House Allocation with Existing Tenants"
627:
679:Aziz, Haris; Keijzer, Bart de (2012).
812:
810:
808:
232:on the sets of agents and houses. An
7:
924:
922:
864:
862:
860:
858:
633:
631:
236:house allocation corresponds to an
14:
769:Journal of Mathematical Economics
401:, for various network structures.
986:10.1016/j.mathsocsci.2019.07.005
228:their "like" relations define a
77:), and m objects (also called:
763:Ergin, Haluk İ. (2000-08-01).
464:small set expansion hypothesis
197:considers rules that are also
1:
781:10.1016/S0304-4068(99)00038-5
964:Mathematical Social Sciences
742:10.1016/0165-1765(82)90003-9
512:{\displaystyle \gamma <1}
455:{\displaystyle \gamma >0}
385:Deciding whether a complete
252:maximum cardinality matching
875:Operations Research Letters
486:{\displaystyle n^{\gamma }}
429:{\displaystyle n^{\gamma }}
1090:
1033:10.1007/s10458-019-09417-x
644:Journal of Economic Theory
287:. However, the problem is
163:random serial dictatorship
15:
897:10.1016/j.orl.2021.06.006
841:10.1016/j.ins.2021.11.059
547:maximum balanced biclique
538:{\displaystyle \gamma =1}
313:fixed-parameter tractable
289:fixed-parameter tractable
333:weighted bipartite graph
104:(indifferences allowed).
37:house allocation problem
22:Apportionment (politics)
1074:Matching (graph theory)
698:10.1609/aaai.v26i1.8239
556:proportional allocation
309:Maximum independent set
254:in the bipartite graph.
657:10.1006/jeth.1999.2553
597:Fair random assignment
539:
513:
487:
456:
430:
285:Maximum clique problem
167:fair random assignment
100:(no indifferences) or
540:
514:
488:
457:
431:
145:Efficient allocations
73:people (also called:
1069:Fair item allocation
819:Information Sciences
615:Fair item allocation
570:equitable allocation
523:
497:
470:
440:
413:
129:no agent should envy
18:house of legislature
566:Deciding whether a
552:Deciding whether a
409:within a factor of
343:allocation exists.
339:Deciding whether a
329:cardinal valuations
281:bipartite expansion
246:Deciding whether a
186:Abdulkadiroglu and
158:serial dictatorship
609:Envy-free matching
591:Assignment problem
535:
509:
483:
452:
426:
239:envy-free matching
226:binary valuations,
210:assignment problem
93:Preference ranking
49:one-sided matching
45:assignment problem
944:978-1-4503-9432-1
730:Economics Letters
561:exact 3-set cover
327:When agents have
224:When agents have
175:top trading cycle
135:Strategyproofness
119:Pareto efficiency
86:Binary valuations
1081:
1053:
1052:
1012:
1006:
1005:
979:
955:
949:
948:
926:
917:
916:
890:
866:
853:
852:
834:
814:
803:
802:
792:
760:
754:
753:
725:
719:
718:
700:
691:(1): 1249–1255.
676:
670:
669:
659:
635:
585:Related problems
544:
542:
541:
536:
518:
516:
515:
510:
492:
490:
489:
484:
482:
481:
461:
459:
458:
453:
435:
433:
432:
427:
425:
424:
277:minimum coverage
217:Fair allocations
108:Cardinal utility
33:computer science
1089:
1088:
1084:
1083:
1082:
1080:
1079:
1078:
1059:
1058:
1057:
1056:
1014:
1013:
1009:
957:
956:
952:
945:
928:
927:
920:
868:
867:
856:
816:
815:
806:
762:
761:
757:
727:
726:
722:
678:
677:
673:
637:
636:
629:
624:
587:
521:
520:
495:
494:
473:
468:
467:
438:
437:
416:
411:
410:
387:local-envy-free
307:reduction from
230:bipartite graph
219:
147:
67:
25:
12:
11:
5:
1087:
1085:
1077:
1076:
1071:
1061:
1060:
1055:
1054:
1027:(5): 591–627.
1007:
950:
943:
918:
881:(4): 572–577.
854:
804:
755:
736:(2): 127–132.
720:
671:
650:(2): 233–260.
626:
625:
623:
620:
619:
618:
612:
606:
603:Rental harmony
600:
594:
586:
583:
582:
581:
574:
564:
550:
534:
531:
528:
508:
505:
502:
480:
476:
451:
448:
445:
423:
419:
402:
391:social network
383:
382:
381:
355:
325:
324:
300:
269:
262:
255:
218:
215:
146:
143:
142:
141:
138:
132:
131:another agent.
122:
112:
111:
105:
89:
66:
63:
58:rental harmony
53:housing market
13:
10:
9:
6:
4:
3:
2:
1086:
1075:
1072:
1070:
1067:
1066:
1064:
1050:
1046:
1042:
1038:
1034:
1030:
1026:
1022:
1018:
1011:
1008:
1003:
999:
995:
991:
987:
983:
978:
973:
969:
965:
961:
954:
951:
946:
940:
936:
932:
925:
923:
919:
914:
910:
906:
902:
898:
894:
889:
884:
880:
876:
872:
865:
863:
861:
859:
855:
850:
846:
842:
838:
833:
828:
824:
820:
813:
811:
809:
805:
800:
796:
791:
786:
782:
778:
774:
770:
766:
759:
756:
751:
747:
743:
739:
735:
731:
724:
721:
716:
712:
708:
704:
699:
694:
690:
686:
682:
675:
672:
667:
663:
658:
653:
649:
645:
641:
634:
632:
628:
621:
616:
613:
610:
607:
604:
601:
598:
595:
592:
589:
588:
584:
579:
575:
572:
571:
565:
562:
558:
557:
551:
548:
532:
529:
526:
506:
503:
500:
478:
474:
465:
449:
446:
443:
421:
417:
407:
403:
400:
396:
392:
388:
384:
379:
378:Hall violator
375:
371:
367:
364:
360:
356:
353:
349:
345:
344:
342:
338:
337:
336:
334:
330:
322:
318:
314:
310:
305:
301:
298:
294:
290:
286:
282:
278:
274:
270:
267:
263:
260:
256:
253:
249:
245:
244:
243:
241:
240:
235:
231:
227:
222:
216:
214:
212:
211:
206:
202:
200:
196:
192:
190:
189:
183:
181:
177:
176:
170:
168:
164:
160:
159:
153:
151:
144:
139:
136:
133:
130:
126:
123:
120:
117:
116:
115:
109:
106:
103:
99:
95:
94:
90:
87:
84:
83:
82:
80:
76:
72:
64:
62:
60:
59:
54:
50:
46:
42:
38:
34:
30:
23:
19:
1024:
1020:
1010:
967:
963:
953:
934:
878:
874:
822:
818:
775:(1): 77–97.
772:
768:
758:
733:
729:
723:
688:
684:
674:
647:
643:
577:
567:
553:
546:
405:
398:
394:
386:
373:
369:
366:
362:
358:
351:
347:
340:
328:
326:
320:
316:
303:
296:
292:
280:
276:
272:
265:
258:
247:
237:
225:
223:
220:
208:
204:
203:
198:
194:
193:
185:
184:
182:allocation.
173:
171:
156:
154:
150:In economics
149:
148:
113:
101:
97:
92:
85:
78:
74:
70:
68:
56:
52:
48:
44:
36:
26:
970:: 104–106.
825:: 164–187.
790:11693/18154
406:complete EF
341:complete EF
321:agent types
317:house types
304:complete EF
297:agent types
293:house types
273:complete EF
248:complete EF
180:core-stable
65:Definitions
41:preferences
1063:Categories
977:1905.00468
888:2106.06925
832:1901.09527
622:References
578:partial EF
576:Finding a
404:Finding a
302:Finding a
271:Finding a
266:partial EF
264:Finding a
259:partial EF
257:Finding a
199:consistent
69:There are
1041:1573-7454
1002:143421680
994:0165-4896
913:235422019
905:0167-6377
849:170079201
799:0304-4068
750:0165-1765
707:2374-3468
666:0022-0531
568:complete
554:complete
527:γ
501:γ
479:γ
462:; if the
444:γ
436:for some
422:γ
234:envy-free
29:economics
1049:51869987
715:15395473
549:problem.
493:for any
125:Fairness
1047:
1039:
1000:
992:
941:
911:
903:
847:
797:
748:
713:
705:
664:
188:Sönmez
98:strict
79:houses
75:agents
35:, the
20:, see
1045:S2CID
998:S2CID
972:arXiv
909:S2CID
883:arXiv
845:S2CID
827:arXiv
711:S2CID
519:(for
357:When
346:When
279:(aka
195:Ergin
1037:ISSN
990:ISSN
939:ISBN
901:ISSN
795:ISSN
746:ISSN
703:ISSN
662:ISSN
504:<
447:>
361:>
319:and
295:and
102:weak
47:and
31:and
1029:doi
982:doi
968:101
893:doi
837:doi
823:587
785:hdl
777:doi
738:doi
693:doi
652:doi
27:In
1065::
1043:.
1035:.
1025:33
1023:.
1019:.
996:.
988:.
980:.
966:.
962:.
933:.
921:^
907:.
899:.
891:.
879:49
877:.
873:.
857:^
843:.
835:.
821:.
807:^
793:.
783:.
773:34
771:.
767:.
744:.
732:.
709:.
701:.
689:26
687:.
683:.
660:.
648:88
646:.
642:.
630:^
372:≥
213:.
61:.
1051:.
1031::
1004:.
984::
974::
947:.
915:.
895::
885::
851:.
839::
829::
801:.
787::
779::
752:.
740::
734:9
717:.
695::
668:.
654::
563:.
533:1
530:=
507:1
475:n
450:0
418:n
399:n
397:=
395:m
380:.
374:n
370:m
363:n
359:m
352:n
350:=
348:m
71:n
24:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.