The introduction

In life and work, there are often times when resources need to be allocated, such as

I don’t like the gift from the company. I want to exchange it with someone else
Realization of exchange system for on-line egg twister
Job offer selection
College entrance examination filing system implementation

Among them, 1 and 2 belong to unilateral matching, which is determined by unilateral expectation, i.e., “buyer”; 3 and 4 are bilateral matching problems, and the expectation of “buyer and seller” should be considered in the matching process.

Under normal circumstances, we expect to obtain a reasonable and stable distribution result as possible, so as to maximize the overall return.

Lloyd S. Shapley and others proposed a series of stable allocation mechanisms for markets, which made great contributions to the field of game theory and economics, and eventually won the 2012 Nobel Prize in Economics, together with Alvin E. Roth.

background

I wrote earlier about encountering a decision business in a business that is really a matching problem between one set of given objects and another set of given objects:

A collection of(a, b, c, d)With the collection(A, B, C, D, E)The final result is multiple groups of one-to-one relationship
In the process of matching, many-to-one matching results may occur due to matching errors
In order to solve the matching conflict, it is necessary to adjust the matching result to “make every object as satisfied as possible”, that is, to achieve the local optimal state and reasonable resource allocation

In the process of adjusting and matching, the priority of results is considered to achieve the stability of resource allocation. At that time, it was not clear whether the optimal effect could be achieved by doing so. After accidentally learning the concept of “strong core allocation” of resource allocation, it was found that the logic of self-implemented allocation algorithm was the same as that of GS algorithm in the game. Confirm that this method can achieve stable resource allocation at the same time, but also understand the practical algorithm applicable to other allocation scenarios, here I hope to easily introduce to you.

Strong nuclear configuration

Strong core configuration satisfies both individual rationality and Pareto optimal state. The strong core configuration is not only present in the matching, but also unique, and has a defensive strategy, that is, neither a backroom deal nor a lie will make the result better than the strong core configuration.

Pareto optimal

Pareto Optimality, also known as Pareto Efficiency, refers to an ideal state of resource allocation. It is assumed that an inherent group of people and distributable resources change from one distribution state to another state without making anyone’s situation worse. Making at least one person better is pareto improvement or Pareto optimization.

Pareto optimality is that there is no more room for Pareto improvement. In other words, Pareto improvement is the path and method to achieve pareto optimality.

— Baidu Encyclopedia

Algorithm is introduced

Top Trading Cycle Algorithm

The first trading cycle algorithm, proposed in 1974, called TTC algorithm.

This applies to “assign” or “trade” scenarios, i.e. one-sided matching problems.

Problem is introduced into

Some companies give gifts of different colors to employees during the holidays. Employees are not satisfied with the colors after drawing the prizes and want to exchange them with others for a prize they prefer.

For employees, the colors they like are not the same, and perhaps they can get a more satisfactory result by exchanging them with others.

Problem definition

For simplicity’s sake, let’s simplify the problem and define some constraints:

Given employee set E= E1, E2, e3, e4
G=< E1, G1 >,

,

,
,>
,>
,>
Only when all parties involved are satisfied
You don’t have to exchange with others

TTC algorithm steps

Rank each employee’s satisfaction with each gift
The employee proposes the most satisfactory present, and establishes a line between the employee and the desired gift, and a line between the gift and its owner
Find if the established edges form loops that allow self-loops, possibly multiple loops
Employees in the loop exchange gifts and stop participating in the exchange
The rest of the staff removes the list from the loop, continues to suggest the current most satisfying gift, and iterates through the loop
The exchange is complete. End

Case presentation

Table based on satisfaction, sorted by satisfaction from high (left) to low (right), and established digraph

< E1, G3 > forms a loop with <e3, G1 > to make a trade and leave

<e2, G4 > and <e4, G2 > form a loop, make a trade and leave, all trades are completed

The core idea of the algorithm is to form an exchange cycle according to the current priority order. The employees who reach a consensus exchange gifts with the present first and leave, and the remaining employees continue to try to form an exchange cycle after removing the present which has left from the satisfaction table.

Problem solving

TTC has some characteristics:

Every iteration must have a loop, even if it’s self-loop
Multiple loops must never intersect because each node has only one outgoing edge
The gift you can exchange must be as good as the one you already have, because at worst it will create a self-fulfilling cycle

Although we usually exchange company gifts using TTC algorithm, but generally there are not enough candidate trading pool and certain rules, the final result may not be optimal.

supplement

TTC algorithm can obtain strong core configuration, strong core configuration is anti-strategy, lying or private transaction will not make the result better.

Make a simple proof that is not rigorous:

For employees who made a successful first deal, lying or making a private deal only made it worse, because they already had the best deal
Employees who succeed in the second round of trading, no matter how their satisfaction ranking is, can not change the cycle of trading success in the first round, so they are not likely to get better; Private deals also hurt the overall picture
And so on the third round