| 弱偏好序下存在租客的房屋匹配问题机制设计 |
| |
| 引用本文： | 熊新生,何琨,赵勇.弱偏好序下存在租客的房屋匹配问题机制设计[J].中国科学:信息科学,2014(9). |
| |
| 作者姓名： | 熊新生 何琨 赵勇 |
| |
| 作者单位： | 华中科技大学自动化学院;怀化学院数学与应用数学系;华中科技大学计算机科学与技术学院; |
| |
| 基金项目： | 国家自然科学基金(批准号:61173180,71071063,61273206) |
| |
| 摘 要： | 已知一房屋集合和一个体集合(房屋数不小于个体数),房屋匹配问题要求根据个体对房屋的偏好,为每一个体分配一个尽可能满意的房屋,使得匹配具有互利性和稳定性.此类问题目前主要研究个体均具有初始分配或均无初始分配这两种情形,且个体对房屋具有严格的偏好序.本文研究一类一般化的房屋匹配问题,即个体对房屋有弱偏好序,且只有部分个体具有初始分配的房屋.基于Shapley和Sacrf的首位交易环算法以及相关的改进算法,设计了求解此一般化问题的扩展首位交易环算法(extended top trading cycle algorithm,ETTC),并证明了由该算法所确定的首位交易环机制满足Pareto有效性、个体理性和防策略操纵性.ETTC算法的时间复杂度为O(n3m),其中n为个体数,m为房屋数.ETTC算法复杂度低于近期已见发表的代表性算法TTAS和TCR.
|
| 关 键 词： | 匹配 机制设计 弱偏好序 Pareto有效 防策略操纵 |
| 本文献已被 CNKI 等数据库收录！ |
|
