弱偏好序下带容量房屋匹配混合模型的机制设计

研究弱偏好序下,带容量房屋市场混合模型（CHMTeT）的机制设计问题,并针对该模型提出了一类算法机制,该机制是TTC算法机制的推广,称之为剔除筛选算法（简记为CTTC）机制.此外,证明了CHMTeT模型应用CTTC算法得到的这一类机制（即CTTC机制）满足个人理性、帕累托有效性和防策略操纵性,并得出CTTC算法的时间复杂度为O（n_1~2（n_1n_2＋n_2~2））,其中n_1为参与人数,n_2为房子数.

弱偏好序下存在租客的房屋匹配问题机制设计

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