文献类型：期刊文章

作　　者：熊新生[1,2] 何琨[3] 赵勇[1]

机构地区：[1]华中科技大学自动化学院,武汉430074 [2]怀化学院数学与应用数学系,怀化418008 [3]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《中国科学：信息科学》

基　　金：国家自然科学基金(批准号:61173180;71071063;61273206)

年　　份：2014

卷　　号：44

期　　号：9

起止页码：1140-1155

语　　种：中文

收录情况：CSCD、CSCD2013_2014、JST、RCCSE、ZGKJHX、普通刊

摘　　要：已知一房屋集合和一个体集合(房屋数不小于个体数),房屋匹配问题要求根据个体对房屋的偏好,为每一个体分配一个尽可能满意的房屋,使得匹配具有互利性和稳定性.此类问题目前主要研究个体均具有初始分配或均无初始分配这两种情形,且个体对房屋具有严格的偏好序.本文研究一类一般化的房屋匹配问题,即个体对房屋有弱偏好序,且只有部分个体具有初始分配的房屋.基于Shapley和Sacrf的首位交易环算法以及相关的改进算法,设计了求解此一般化问题的扩展首位交易环算法(extended top trading cycle algorithm,ETTC),并证明了由该算法所确定的首位交易环机制满足Pareto有效性、个体理性和防策略操纵性.ETTC算法的时间复杂度为O(n3m),其中n为个体数,m为房屋数.ETTC算法复杂度低于近期已见发表的代表性算法TTAS和TCR.

关 键 词：匹配  机制设计  弱偏好序  Pareto有效  防策略操纵  

分 类 号：F293.3] TP301.6]