Presentation Information
[2Yin-A-33]Rent Division with Extra Rooms
〇Mizuki Tsujimoto1, Katsuhide Fujita1 (1. Tokyo University of Agriculture and Technology)
Keywords:
Rent Division,Envy-Freeness,Combinatorial optimization
共同アパートにおいて部屋と家賃をルームメイトに割り振る際，全員が納得するように割り当てる問題をrent division問題という．しかし，従来のrent division問題では，一人に一部屋割り当てる設定を前提として研究されてきた．そこで本研究では，余剰部屋を伴うRent Division問題（extra-room rent division problem，以下ERD問題）に対し，公平な解を求めるアルゴリズムを設計する．まず，余剰部屋の扱い方を，「個人部屋割当」「共同部屋割当」「自由割当」の3パターンに分類し，各パターンに対して社会的厚生が最大になるよう部屋を割り当てる最適アルゴリズムや，多項式時間で解ける近似アルゴリズムを提案する．
さらに，公平性基準に関しても，従来のenvy-freeを拡張した「player envy-free」，およびその緩和概念である「ε-player envy-free」の二種類を導入する．これらの公平性概念について，解の存在性やERD問題における理論的特性について数学的に示すとともに，提案アルゴリズムの有効性をシミュレーション実験によって評価する．
さらに，公平性基準に関しても，従来のenvy-freeを拡張した「player envy-free」，およびその緩和概念である「ε-player envy-free」の二種類を導入する．これらの公平性概念について，解の存在性やERD問題における理論的特性について数学的に示すとともに，提案アルゴリズムの有効性をシミュレーション実験によって評価する．