The Matching Models And Algorithms With Diversity Constraints

Gale and Shapley introduced the stable matching model in 1962. The theory and its application in practice is awarded the 2012 Nobel Prize in Economics. This model is closely related to applied mathematics, economics and computer science, and has many important applications on market design and industry. In the pluralistic society today,many matching problems need to consider the diversity requirement, because a group with diverse backgrounds is normally more active, more creative and more robust. We study the matching problems with one-sided preference and diversity constraints in this thesis. It contains a lot of complementarities in the description of diversity, which bring essential di?culties for the classic stable matching algorithms. In order to e?ciently model the diversity, we propose to classify the agents in the matching problem and control the upper bound and lower bound of each category. Considering that we only have one-sided preference, a relaxed optimization method is proposed and a dynamic market clearing price mechanism is designed to solve this problem.In the relaxed optimization method, the objective is to maximize the sum of preference scores in the matching, under the upper bound constraint and lower bound constraint of each category. It is proved that we can still obtain the integer solution of relaxed optimization problem as long as the categories are disjoint. To further balance the fairness and the diversity, we add the diversity as a penalty term in the objective function and hence we can control the balance through the penalty coe?cients.Combining the ascending bid auction and descending bid auction, a dynamic market clearing price mechanism with two stages is proposed. In the first stage, we apply the ascending bid auction to eliminate the demand excess and make the upper bound constraints satisfied; in the second stage, we apply the descending bid auction to eliminate the supply excess and fulfill the lower bound constraints. After these two stages,one can obtain the market clearing price and the stable allocation. Similar to the idea of balancing fairness and diversity in the relaxed optimization method, we heuristically adjust the price to optimize the diversity when the upper bound constraint and lower bound constraints are satisfied.Sponsored search is the main monetization channel for the commercial search engines. It is essentially a matching problem in optimization, and the research in this area is called computational advertising. The application of matching model and algorithm in computational advertising is presented and numerical experiments are also given.