1绪论匹配问题[1]是计算机领域、运筹学和经济学中的一个典型问题,许多的经济学问题都可以表述为两组没有交集的成员之间的匹配问题[2][3]。稳定匹配问题是匹配问题最重要的分支之一,在社会生活以及经济建设方面有着极为广泛的应用,引起了越来越多国内外相关学者的关注和重视。Alvin Roth和Lloyd Shapley从抽象理论对市场制度实际设计中的稳定匹配进行了研究[4],改善了多种经济市场的表现从而获得了 2012年诺贝尔经济学奖。随着移动通信技术、集成电路技术的发展以及信息时代所带来的信息多元化变革,应运而生的智能终端不仅会以电子计算机的形式出现,也会以可连接互联网的移动电话[5]、车载系统、安防系统等智能系统的形式出现。第三代宽带无线网络[6]的广泛应用使得智能终端与移动互联网服务[7]和分布式对象服务[8]相结合成为信息交互的必然趋势,因此智能终端与服务之间需要进行快速高效的匹配。服务提供商要在保证成本的基础上向用户提供可靠的服务,用户则需要获得快速稳定的互联网服务以满足信息交互的需求,为了更好的解决智能终端与服务的匹配问题,达到用户和服务提供商利益的最大化,我们需要对智能终端与服务之间的稳定匹配进行研究。1. 1课题研究背景匹配问题在计算机领域有着广泛的应用场景,如无线网络调度中分配信道给用户和流以及视频点播系统中对视频片段与服务器进行映射[9]等。稳定匹配问题在计算机领域有着独特的应用价值和适用性,在计算机网络中进行稳定匹配时可以将匹配的对象可以细化到比特,而在其他领域进行匹配的对象必须是独立的个体或者事件,因此稳定匹配在计算机领域的匹配场景中有着巨大的研究价值。信息时代互联网的飞速发展让生活中充满了各式各样的信息,智能终端的发展与互联网服务的兴起使得终端与服务之同的关系日趋紧密,不断地改变着用户接触信息的习惯。智能终端的硬件性能大幅提升同时成本的大幅下降,推动了智能终端的普及;多元化的终端操作系统如Symbian_、Android[u]、108[12]以及Windows Mobile[i3]等逐渐成熟极大提高了终端用户对互联网服务的需求。与此同时,互联网服务已经成为现代信息产业的发展新趋势[14],智能终端可以通过移动联网folemtn)随时随地的获取各种服务,因此创新的服务如移动阅读[16]、移动搜索[17]、移动支付[18]、移动社交[19] (Social Network Site, SNS)以及移动即时通信[2o]等也对智能终端的发展起到关键的促进作用。