﻿ 二手房组合交易匹配决策方法
 文章快速检索 高级检索

Decision-making method on second-hand house combination matching
LIANG Hai-ming, JIANG Yan-ping
Abstract:With respect to the second-hand house combination matching problem, a novel decision-making analysis method is proposed. Firstly, the definitions of second-hand house combination matching, individual rationality, no wasteful, fairness, pareto optimal and pareto efficient matching alternatives are given. Then, the methods for calculating matching satisfaction degrees of buyers and sellers are given by considering the evaluation provided by sellers and the aspiration level on multi-attribute and distance demand provided by buyers. Further, an extended H-R algorithm considering the stability of matching alternative is designed to determine the optimal matching alternative, and the rationality of this algorithm is proved. Finally, an example is given to illustrate the efficient and feasible of extended H-R algorithm.
Key words: second-hand house combination matching     satisfaction degree     extended H-R algorithm     matching alternative

0 引言

1) 买方只购买一套二手房,没有购买两套二手房的意愿,为方便叙述, 记此种类型的买方集合为$B^1$;

2) 买方只购买两套二手房,对于一套二手房不予考虑, 记此种类型的买方集合为$B^2$;

3) 买方或者购买两套二手房,或者购买一套二手房, 购买的数量主要取决于买方关于单套二手房或 二手房组合的满意度大小. 如果买方关于单套二手房的满意度更高,则买方购买一套二手房, 否则购买两套. 记此种类型的买方集合为$B^3$,其中$B^1\cup B^2\cup B^3=B$,$B^1\cap B^2=B^1\cap B^3=B^2\cap B^3=\emptyset$.

1) $\mu(S_i )\subseteq B\cup \{ S_i \}$,若$\mu(S_i)=S_i$, 则说明卖方$S_i$没能将二手房$H_i$出售出去;

2) $\mu(B_j)\subseteq S\cup \{ B_j\}$,若$\mu(B_j)=B_j$, 则说明买方$B_j$没能购买到二手房;

3) 若$\mu(S_i)=B_j$,$\mu(B_j)=S_i$, 此时称$(S_i,B_j)$为根据匹配$\mu$确定的一个匹配对;

4) 对于$B_j\in B$,若$\mu(S_i)=B_j$,则$\mu(S_i)\ne B_k$,$k\ne j$;

5) 对于$B_j\in B^1$,若$\mu(B_j)=S_i$,则$\mu(B_j)\ne S_l$,$i\ne l$;

6) 对于$B_j\in B^2$,若$\mu(B_j)=\{S_i,S_l\}$,则$\mu(B_j)\ne S_v$,$v\ne i\ne l$;

7) 对于$B_j\in B^3$,若$\mu(B_j)=\{S_i,S_l\}$,则$\mu(B_j)\ne S_v$,$v\ne i$,$v \ne l$;

1) 对于$\forall S_i,S_l\in S$,设$\mu(S_i)=B_j$,$\mu '(S_i)=B_k$, $B_j,B_k\in B$,$S_i$在$\mu$中的匹配对象均不劣于在$\mu '$中的匹配对象,即$\eta _{ij} \ge \eta _{ik}$; 同时至少存在一个卖方$S_l$,$\mu(S_l)=B_p$,$\mu '(S_l)=B_q$, $B_p,B_q\in B$,$S_l$在$\mu$ 中的匹配对象优于在$\mu '$中的匹配对象,即$\eta _{lp}>\eta _{lq}$;

2) 对于$\forall B_j\in B$,$\mu(B_j)=\{S_i,S_g\}$,$\mu '(B_j)=\{S_v,S_t\}$,$S_i,S_g,S_v,S_t\in S$, $B_j$在$\mu$中的匹配对象均不劣于在$\mu '$中的匹配对象, 即$a_{ig}^j\ge a_{vt}^j$; 同时至少存在一个买方$B_k$,$B_k\in B$, 设$\mu(B_k)=\{S_p,S_l\}$,$\mu '(B_k)=\{S_e,S_r\}$, $S_p,S_l,S_e,S_r\in S$,满足$B_k$在$\mu$ 中的匹配对象优于在$\mu '$中的匹配对象,即$a_{pl}^k > a_{er}^k$.

 $p_{ij}=(r_{il}+e_{jl})/2,i=1,2,\cdots,m,j=1,2,\cdots,n$ (1)

1) 当买方$B_j$关于属性$C_l$提出硬约束,则$a_{ijl}$的计算公式为
 $a_{ijl} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {r_{il} \in e_{jl} } \hfill \\ { - \infty ,} \hfill & {r_{il} \notin e_{jl} } \hfill \\ \end{array}} \right.,i=1,2,\cdots,m,j=1,2,\cdots,n$ (3)

2) 当买方$B_j$关于属性$C_l$提出效益型约束,则$a_{ijl}$的计算公式为

3) 当买方$B_j$关于属性$C_l$提出成本型约束,则$a_{ijl}$的计算公式为

4) 当买方$B_j$关于属性$C_l$提出区间型约束,则$a_{ijl}$的计算公式为
 $a_{ijl} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {e_{jl}^L \le r_{il} \le e_{jl}^U } \hfill \\ { - \infty ,} \hfill & {r_{il} < e_{jl}^Lmbox{or}\ r_{il} > e_{jl}^U } \hfill \\ \end{array}} \right.,i=1,2,\cdots,m,j=1,2,\cdots,n$ (6)

 $a_{ii}^j = \sum\limits_{l = 1}^k {w_l^j a_{ijl} },i,g=1,2,\cdots,m$ (8)

 $a_{ig}^j = \omega _1^j {{(a_{ii}^j + a_{gg}^j )} / 2} + (1 - \omega _1^j )\lambda _{ig}^j,i,g=1,2,\cdots,m,i\ne g$ (1)

Step 1 迭代变量初始化. 令迭代变量$t=1$,$U_{S_i }^{(1)}=\emptyset$,$V^{(1)}=\emptyset$,$B^{(1)}=B$,$P_{B_j }^{(1)}=\emptyset$,$P_{S_i}^{(1)}=\emptyset$,$\mu ^{(1)}(S_i)=\emptyset$,$\mu ^{(1)}(B_j)=\emptyset$;

Step 2 筛选符合$S_i$和$B_j$需求的集合. 若$a_{ii}^j>0$且$B_j \in B^1 \cup B^3$,则$P_{B_j }^{(t)} = P_{B_j }^{(t)} \cup \{ (H_i ,H_i )\}$; 若$a_{ig}^j>0$,$i\ne g$且$B_j \in B^2 \cup B^3$,则$P_{B_j }^{(t)} = P_{B_j }^{(t)} \cup \{ (H_i ,H_g )\}$; 若$\eta_{ij}>0$,则$P_{S_i }^{(t)} = P_{S_i }^{(t)} \cup \{ B_j \}$;

Step 3 买方$B_j$向最满意的二手房组合提出购买意向. 对于买方$B_j \in B^{(t)}$,计算 $a_{(t)1(t)2}^j=\max \{a_{ig}^j,\\ (H_i,H_g)\in P_{B_j }^{(t)}\}$,令$U_{S_{(t)1} }^{(t)}=U_{S_{(t)1} }^{(t)} \cup \{ B_j \}$,$U_{S_{(t)2} }^{(t)}=U_{S_{(t)2} }^{(t)} \cup \{ B_j \}$. 当$\mu ^{(t)} (S_{(t)1} ) =\emptyset$且$\mu ^{(t)} (S_{(t)2} ) =\emptyset$时,则转Step 4; 当$\mu ^{(t)} (S_{(t)1} ) = B_{(t)y1}$ 且$\mu ^{(t)} (S_{(t)2} ) = B_{(t)y2}$时,$(t)y1,(t)y2 \in \{1,2,\cdots ,n\}$,则转Step 5; 当$\mu ^{(t)} (S_{(t)1} )= B_{(t)y1}$ 且$\mu ^{(t)}(S_{(t)2})=\emptyset$ 时,$(t)y1\in \{1,2,\cdots ,n\}$,则转Step 6; 当$\mu ^{(t)} (S_{(t)1} ) = \emptyset$ 且$\mu ^{(t)} (S_{(t)2} ) = B_{(t)y2}$时,$(t)y2 \in \{1,2,\cdots ,n\}$,则转Step 7;

Step 4 卖方$S_{(t)1}$和$S_{(t)2}$判断是否接受买方$B_j$. 当$B_j\in P_{S_{^{(t)1}}}^{(t)}$,$B_j\in P_{S_{^{(t)2}}}^{(t)}$,并且$\eta_{(t)1j}=\max\{\eta_{ij},B_j \in U_{S_{(t)1}}^{(t)}\}$, $\eta_{(t)2j}=\max\{\eta_{ij},B_j \in U_{S_{(t)2}}^{(t)}\}$,则$\mu ^{(t)} (B_j)=\{S_{(t)1},S_{(t)2}\}$,$V^{(t)}=V^{(t)}\cup \{ B_j\}$,$B^{(t)}=B^{(t)}-\{ B_j\}$,转Step 8;

Step 5 卖方$S_{(t)1}$和$S_{(t)2}$判断是否放弃原匹配对象. 当$\eta_{(t)1j}=\max \{\eta _{ij},B_j\in U_{S_{(t)1}}^{(t)}\}$, $\eta_{(t)2j}=\max \{\eta _{ij},B_j\in U_{S_{(t)2}}^{(t)}\}$, 且满足$\eta _{(t)1j}> \eta _{(t)1(t)y1}$和$\eta _{(t)2j}> \eta _{(t)1(t)y2}$时,则$\mu ^{(t)}(B_j )=\{ S_{(t)1},S_{(t)2}\}$, $V^{(t)}=V^{(t)}\cup \{ B_j\}$,$B^{(t)}=B^{(t)}-\{ B_j\}$, $P_{B_{(t)y1}}^{(t)}=P_{B_{(t)y1}}^{(t)}-\{(H_{(t)1},H_i),i\in \{1,2,\cdots,m\}\}$,$P_{B_{(t)y2} }^{(t)}=P_{B_{(t)y2} }^{(t)}-\{(H_{(t)2},H_i),i\in \{1,2,\cdots ,m\}\}$, $B^{(t)}=B^{(t)}\cup \{B_{(t)y1},B_{(t)y2}\}$,转Step 8;

Step 6 卖方$S_{(t)1}$判断是否放弃原匹配对象, $S_{(t)2}$判断是否接受买方$B_j$. 当$\eta_{(t)1j}=\max \{\eta _{ij},B_j\in U_{S_{(t)1}}^{(t)}\}$,$\eta_{(t)2j}=\max \{\eta _{ij},B_j\in U_{S_{(t)2}}^{(t)}\}$,且满足$\eta _{(t)1j}> \eta _{(t)1(t)y1}$和$B_j\in P_{S_{^{(t)2}}}^{(t)}$时,则$\mu ^{(t)}(B_j )=\{ S_{(t)1},S_{(t)2}\}$,$V^{(t)}=V^{(t)}\cup \{ B_j\}$,$B^{(t)}=B^{(t)}-\{ B_j\}$, $P_{B_{(t)y1}}^{(t)}=P_{B_{(t)y1}}^{(t)}-\{(H_{(t)1},H_i),i\in \{1,2,\cdots,m\}\}$,$B^{(t)}=B^{(t)}\cup \{B_{(t)y1}\}$,转Step 8;

Step 7 $S_{(t)1}$判断是否接受买方$B_j$,卖方$S_{(t)2}$判断是否放弃原匹配对象. 当$\eta_{(t)1j}=\max \{\eta _{ij},B_j\in U_{S_{(t)1}}^{(t)}\}$, $\eta_{(t)2j}=\max \{\eta _{ij},B_j\in U_{S_{(t)2}}^{(t)}\}$, 且满足$\eta _{(t)2j}> \eta _{(t)2(t)y2}$和$B_j\in P_{S_{^{(t)1}}}^{(t)}$时,则$\mu ^{(t)}(B_j )=\{ S_{(t)1},S_{(t)2}\}$,$V^{(t)}=V^{(t)}\cup \{ B_j\}$, $B^{(t)}=B^{(t)}-\{ B_j\}$, $P_{B_{(t)y2}}^{(t)}=P_{B_{(t)y2}}^{(t)}-\{(H_{(t)2},H_i),i\in \{1,2,\cdots,m\}\}$,$B^{(t)}=B^{(t)}\cup \{B_{(t)y2}\}$,转Step 8;

Step 8 判定算法是否终止. 令$t=t+1$, 若$B^{(t)}\ne\emptyset$且$\forall B_j\in B^{(t)}$,$P_{B_j }^{(t)}\ne\emptyset$,转Step 3; 否则转Step 9;

Step 9 结束程序.

4个买方$B_1$,$B_2$,$B_3$和$B_4$关于二手房的多属性需求信息, 如表 3所示.

4个买方$B_1$,$B_2$, $B_3$和$B_4$给出的刚好满足其期望水平时的满意度,即$\varepsilon _1=0.4$,$\varepsilon _2=0.45$,$\varepsilon_3 =0.55$和$\varepsilon_4=0.5$. 假设中介根据买方关于属性重要程度的比较信息,采用AHP方法, 确定4个买方的权重信息,如表 5所示.

A中介根据买方的需求数量,确定了买方的需求类型,即$B_3 ,B_4\in B^1$,$B_1\in B^2$,$B_2\in B^3$. 下面根据第2节中给出的匹配决策分析方法,确定最优匹配方案.

 [1] Gale D, Shapley L. College admissions and the stability of marriage[J]. American Mathematical Monthly, 1962, 69(1): 9-15. [2] Roth A E. Common and conflicting interests in two-sided matching markets[J]. European Economic Review, 1985, 27(1): 75-96. [3] Jung J J, Jo G S. Brokerage between buyer and seller agents using constraint satisfaction problem models[J]. Decision Support Systems, 2000, 28(4): 293-304. [4] 樊治平, 陈希. 电子中介中基于公理设计的多属性交易匹配研究[J]. 管理科学, 2009, 22(3): 83-88. Fan Zhiping, Chen Xi. Research on multi-attribute trade matching problem in electronic broker based on axiomatic design[J]. Journal of Management Science, 2009, 22(3): 83-88. [5] 张振华, 汪定伟. 电子中介在旧房市场中的交易模型研究[J]. 系统仿真学报, 2006, 2: 492-495. Zhang Zhenhua, Wang Dingwei. Research on trading model of electronic broker in second-hand apartment market[J]. Journal of System Simulation, 2006, 2: 492-495. [6] 蒋忠中, 樊治平, 汪定伟. 电子中介中具有模糊信息且需求不可分的多属性商品交易匹配问题[J]. 系统工程理论与实践, 2011, 31(12): 2355-2366. Jiang Zhongzhong, Fan Zhiping, Wang Dingwei. Trade matching for multi-attribute exchanges with fuzzy information and indivisible demand in E-brokerage[J]. Systems Engineering —— Theory & Practice, 2011, 31(12): 2355-2366. [7] 蒋忠中, 袁媛, 樊治平. 电子中介中具有数量折扣的多属性商品交易匹配问题研究[J]. 中国管理科学, 2010, 18(6): 122-130. Jiang Zhongzhong, Yuan Yuan, Fan Zhiping. Multi-attribute trade matching with quantity discount in electronic brokerage[J]. Chinese Journal of Management Science, 2010, 18(6): 122-130. [8] Kwang M S, Raymond C. A brokering protocol for agent-based e-commerce[J]. IEEE Transactions on Systems, Man, and Cybernetics —— Part C, 2000, 30(4): 474-484. [9] Ragone A, Straceiab U, Noiaa T D, et al. Fuzzy matchmaking in e-marketplaces of peer entities using Datalog[J]. Fuzzy Sets and Systems, 2009, 160(2): 251-268. [10] Yang J, Jiao Y B. Case-based reasoning for semi-automatic trade matching for electronic commerce broker[J]. Service Systems and Service Management, 2012: 528-532. [11] Tankuya M. Punishment-dominance condition on stable two-sided matching algorithms[J]. Kyoto Joint Global Center of Excellence Program, 2012, 18: 1-15. [12] Ohta N, Iwamoto K, Kuwabara K. Changeable two-sided matching for changing environment[C]// IEEE 11th International Conference on Cognitive Informatics & Cognitive Computing, 2012: 24-32. [13] Joshi M, Bhavsar V C, Boley H. Compromise matching in P2P e-marketplaces: Concept, algorithm and use case[M]. Multi-disciplinary Trends in Artificial Intelligence. New York: Springer Berlin Heidelberg, 2011: 384-394. [14] 魏立佳. 弱偏好序下的最优单边匹配算法设计[J]. 系统工程理论与实践, 2011, 31(9): 1687-1695. Wei Lijia. Optimal mechanism design of weak preference orders one-sided matching[J]. Systems Engineering —— Theory & Practice, 2011, 31(9): 1687-1695. [15] Balinski M, Sönmez T. A tale of two mechanisms: Student placement[J]. Journal of Economic Theory, 1999, 84(1): 73-94. [16] Roth A E. On the allocation of residents to rural hospitals: A general property of two-sided matching markets[J]. Econometrica: Journal of the Econometric Society, 1986, 54(2): 425-427.
0

#### 文章信息

LIANG Hai-ming, JIANG Yan-ping

Decision-making method on second-hand house combination matching

Systems Engineering - Theory & practice, 2015, 35(2): 358-367.