基于公理化弱偏好序下市场中的匹配机制及其算法研究

This project we study the resource distribution market that monetary transfers are not permitted, and research matching mechanism and algorithm design for agents with weakly preferences. The concept of matching mechanism is presented for resource distribution market with non-monetary transfers, the axiom system of fairness, rationality and efficiency is established from the different sides, and the optimal matching mechanism is formed. We give the implementation path of the optimal matching mechanism that satisfies the axiom system by constructive methods, and analyze the property of the complexity of the algorithm. For the one-sided matching market that only one sided agents have preferences, we present a mechanism that satisfies individually rationality, Pareto-efficiency and strategy-proofness, and give the condition such that the matching satisfying the axiom system is unique under the weakly preferences. For the two-sided matching market that both sided agents have preferences, we present an axiom system that satisfies individually rational, Pareto efficiency and stability, and discuss the compatibility of axiom rules under the static and dynamic state, respectively. We further give the condition such that the matching mechanism satisfying Pareto efficiency and stability, and the matching that computed by the matching mechanism is unique.

以非货币资源配置市场为研究对象，研究弱偏好序下最优匹配机制设计及其算法。提出非货币资源配置市场匹配机制的概念，建立从不同侧面刻划公平性、合理性和有效性的公理系统，形成非货币资源配置市场最优匹配机制，构造性地给出满足公理系统的最优匹配机制的实现路径与算法过程，并讨论算法计算复杂性的多项式特性。对匹配双方中只有一方参与者具有偏好序的单边市场，提出满足个体理性、Pareto有效性和防策略操纵性的公理系统的匹配机制，给出在弱偏好序下满足公理系统并使匹配唯一的条件。对匹配双方参与者都具有偏好序的双边市场，提出个体理性、Pareto有效性和稳定性构成的公理系统，分别在动态环境下和静态环境下讨论公理规则间的相容性。给出弱偏好序下匹配机制满足Pareto有效性和稳定性且使匹配唯一的条件。

以非货币资源配置市场为研究对象，研究弱偏好序下最优匹配机制设计及其算法。提出非货币资源配置市场匹配机制的概念，建立了从不同侧面刻画公平性、合理性和有效性的公理系统，给出了非货币资源配置市场最优匹配机制，构造性地给出满足公理系统的最优匹配机制的实现路径与算法过程，并讨论了算法的时间复杂性。对于单边一对一匹配市场，针对经典的TTC机制在弱偏好序下不再具有防策略操纵性和Pareto有效性，给出了一个满足个体理性、Pareto有效性和防策略操纵性的匹配机制。并且给出了一个时间复杂度复杂度为目前最低的算法。对于双边市场中多对多的匹配问题，本项目研究了匹配机制的群体稳定性。在响应扩展偏好序下分析了成对稳定匹配、Pareto有效匹配、Pareto稳定匹配和群体稳定匹配之间的关系，并证明了在响应扩展偏好序下，Pareto稳定匹配不一定存在，提出了一种时间复杂度为多项式时间的算法用来判断成对稳定匹配是否为群体稳定。证明了在极小扩展响应偏好序下，弱群体稳定匹配存在。当响应扩展偏好序满足最大极小准则时，群体稳定匹配也一定存在，且所有成对稳定匹配都是群体稳定匹配。当响应扩展偏好序满足字典排序时，群体稳定匹配不一定存在。对于多对多双边匹配问题，针对在弱偏好序下和极小响应扩展偏好序下，Gale-Shapley机制不满足Pareto有效性公理。针对市场中所有个体和市场中某一方个体分别设计了两个新的满足Pareto有效性、稳定性的匹配机制，并且给出了时间复杂度为多项式时间的相应算法。研究了三方非合作双向间接链接模型下的有效和纳什网络，以网络的有效性和均衡性为研究基础，在网络主被建者存在收益差别和间接链接存在收益衰减的情况下，着重讨论了模型下的有效网络和纳什网络拓扑结构。本项目研究可以用于现实世界中大规模的双边市场中匹配机制的设计。发表论文11篇（SCI收录3篇）。