English

运筹学学报 >

2015 , Vol. 19 >Issue 2: 111 - 126

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2015.02.013

运筹学

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

展开
  • 1. 湖北师范学院数学与统计学院, 湖北黄石\,435002

收稿日期: 2013-05-04

  网络出版日期: 2015-06-15

基金资助

国家自然科学基金(Nos. 61304057, 11471105)

收起

Capacitated house market model with tenant under weak preferences

Expand
  • 1. College of Mathematics and Statistics, Hubei Normal University, Huangshi 435002, Hubei, China

Received date: 2013-05-04

  Online published: 2015-06-15

Fold

摘要

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

关键词： 房屋分配; 弹性; 虚拟参与人; 帕累托有效性; 防策略操纵性

本文引用格式

吴威让,陈金阳,翁亚兰 . 弱偏好序下带容量房屋匹配混合模型的机制设计[J]. 运筹学学报, 2015 , 19(2) : 111 -126 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.02.013

Abstract

In this paper, the capacitated house market model with tenant under weak preferences problem has been considered. According to this model, we propose a kind of algorithm mechanism which is the extension of TTC algorithm, known as the Remove Selection algorithm(called CTTC) mechanism. In addition, we show that this kind of mechanism by using CTTC of the model satisfies individual rationality, Pareto-efficient and strategy-proof, and the complexity of CTTC algorithm is O(n_{1}^{2}(n_{1}n_{2}+n_{2}^{2})), where n_{1} is the number of agents, n_{2} is the number of the house.

Key words： house allocation; elasticity; virtual participants; Pareto-efficient; strategy-proof

参考文献

Shapley L, Scarf H. On cores and indivisibility [J]. Journal of Mathematical Economics, 1974, 1(1): 23-28.


Ma J. Strategy-proofness and the strict core in a market with indivisibilities [J]. International Journal of Game Theory, 1994, 23(1): 75-83.

Abdulkadiroglu A, Sonmez T. House allocation with existing tenants [J]. Journal of Economic Theory, 1999,88(2): 233-260.

Alcalde-Unzu J, Molis E. Exchange of indivisible goods and indifferences: The top trading absorbing sets mechanisms [J]. Games and Economic Behavior, 2011,73(1): 1-16.

Aziz H, de Keijzer B. Housing markets with indifferences: A tale of two mechanisms [C]//AAAI-12, 2012, 57-60.

Plaxton C G. A simple family of top trading cycles mechanisms for housing markets with indifferences [EB/OL]. [2012-10-03]. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39\\2.8731.

David F M. Algorithmics of Matchings under Preferences [M]. London: World Scientific Publishing Co. Pte. Ltd, 2013.

Noam Nisa, Tim Roughgarden, Eva Tardos, et al. Algorithmic Game Theory [M]. New York: Cambridge University Press,  2007.

Jaramillo P, Manjunath V. The difference-indifference makes in strategy-proof allocation of object [J]. Journal of Economic Theory, 2012,147(5): 1913-1946.

Daniela S, Jay S.  A note on object allocation under lexicographic preferences [J]. Journal of Mathematical Economics, 2013,50: 283-289.

Zhang Y J,  Wang A D, Da Y B. Regional allocation of carbon emission quotas in China: Evidence from the Shapley value method [J]. Energy Policy, 2014,74: 454-464.
Bondy J A, Murty  U S R. Graph Theory and Its Applications [M]. New York: Academic Press, 1976.

 
Options
文章导航

/

〈 〉