earticle

영어

This paper researches the issue of the housing allocation problem(HAP), in which the agents assign optimal preference order housing if they give preference order to representative housing for n agents and m houses (n = m, n ≠ m). Traditional top trading cycle(TTC) algorithm shows that each agent chooses the best(first) preference order to home and selects the best preference house in cycle. For the remaining unassigned agents and houses, finds the cycle. In this case, unassigned agents have a worse order of preference(in the worst case, they have a worst preferred housing). To solve the this problem, this paper reverse delete from worst preference order to best. In this process, if only one cell is left in a row(agent) or column(house), this algorithm selects that preference order cell. Applying to 16 benchmarking data, the proposed algorithm allocating optimal housing for all data.

한국어

본 논문은 n명의 에이전트들이 m대의 주택 (n = m, n ≠ m)에 대해 선호순서를 부여할 경우 최적의 주택을 배정하 는 주택 배정 문제를 연구하였다. 기존의 최상 선호순서 거래 사이클 알고리즘은 각 에이전트가 최상의 선호순서(1순위) 주택을 선택하여 형성된 사이클에 주택을 배정하고, 남은 에이전트들과 미배정된 주택을 대상으로 다시 사이클을 형성하 는 방법을 적용하였다. 이 경우 미 배정된 에이전트들은 보다 좋지 않은 선호순서(최악의 경우 가장 선호하지 않는 주택 배정)의 주택을 배정받을 가능성이 있다. 이러한 문제점을 해결하기 위해 본 논문에서는 최악의 선호순서부터 역-삭제하 는 과정에서 행(에이전트) 또는 열(주택)에 1개만 남는 경우 해당 선호순서 셀을 선택하는 방법을 제안하였다. 제안된 알고리즘을 16개의 벤치마킹 데이터들에 적용한 결과 모든 데이터들에 대해 최적의 주택을 배정할 수 있음을 보였다.