BabbleDay's Blog

Reference: Algorithm Design - Jon Kleinberg

问题：n个男的和n个女的，每人对异性都有一个ranking，男的会按ranking从高到低求婚，女的会在单身时接受订婚并且在有ranking更高的男的求婚的时候建立新的订婚。求一个stable marriage matching。

Gale-Shapley算法：

Initially all m∈M and w∈W are free
While there is a man m who is free and hasn’t proposed to every woman
    Choose such a man m
    Let w be the highest-ranked woman in m’s preference list to whom m has not yet proposed 
    If w is free then
        (m, w) become engaged
    Else w is currently engaged to m′
        If w prefers m′ to m then 
            m remains free
        Else w prefers m to m′ 
            (m, w) become engaged 
            m′ becomes free
        Endif 
    Endif
Endwhile
Return the set S of engaged pairs

Bonnie的概括：

只要还有单身男子，他就从高到低向喜欢的女子求婚，女子若单身，则配对，若不单身，女子选择自己更喜欢的

算法分析：

1.  while循环最多执行n²次：每次循环有一个男的向之前未求过婚的女的求婚，而最多有n²个男女配对

2.  任何G-S算法的执行返回同一个稳定集合S*：

定义在稳定集合中出现的配对叫有效伴侣，在G-S执行E得到S*的过程中，第一次出现被有效伴侣w拒绝的男的m，此时w因为已经与比m更好的男的m'订婚才会拒绝m的，所以w：m' > m。那么设在另一个稳定集合S中（m, w），（m'，w'）。回到S*，因为这是E中第一个出现的被有效伴侣的拒绝，所以m'没有被自己的有效伴侣w'拒绝，所以m'：w > w'。至此，S已经不再稳定，矛盾出现，所以不存在另一个稳定集合S。

注意，这里是说该算法返回集合一定，但是it’s possible for an instance to have more than one stable matching

[Concepts in Book]
Perfect Matching 两两完全配对    Stable Matching 不存在 两个更喜欢对方却和别人配在一起的perfect matching

3.  每个女的都和worst valid partner在一起：

假设稳定集合S中有（w, m），稳定集合S'中有（w, m'），且w：m > m'。那么设S'中还有（w', m），因为在S中best(m)=w，所以m：w > w'，所以S'不稳定，矛盾。

4. The version of the Gale-Shapely algorithm where the male proposes and the version where the female proposes both yield the exact same matching <=> There is a unique stable matching. 

拓展：

若另加一个条件F说明所有禁止的配对，G-S算法的循环条件变为“While there is a man m who is free and hasn’t proposed to every woman w for which (m,w)̸∈F ”

女的撒谎是否可以提高配偶的质量：possible
m1  m2  m3  w1  w2  w3  w3'
w3  w1  w3  m1  m1  m2  m2
w1  w3  w1  m2  m2  m1  m3
w2  w2  w2  m3  m3  m3  m2

更抽象的，这是一个二分图匹配问题

二分图：to decide whether a graph is a bipartite, run BFS to color all the nodes O(m+n), then check every edge O(n)

Proof with the following facts:

If a graph is not a bipartite, in the bfs tree has an edge connecting the same color in the same color

If a graph is a bipartite, there is no odd cycle - "If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search tree connecting its two endpoints to their lowest common ancestor forms an odd cycle."

Bipartite Matching Problem is the following: Given an arbitrary bipartite graph G, find a matching of maximum size. If |X| = |Y| = n, then there is a perfect matching if and only if the maximum matching has size n. 

Solution preview: "There is a very elegant and efficient algorithm to find a maximum matching; it inductively builds up larger and larger matchings, selectively backtracking along the way. This process is called augmentation, and it forms the central component in a large class of efficiently solvable problems called network flow problems. "

再抽象一层 Independent Set Problem: Given G, find an independent set that is as large as possible. 

In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I.

Interval Scheduling (Arrange as many requests for a resource in a period as possible) and Bipartite Matching can both be encoded as special cases of the Independent Set Problem. For Interval Scheduling, define a graph G = (V , E) in which the nodes are the intervals and there is an edge between each pair of them that overlap; the independent sets in G are then just the compatible subsets of intervals. Encoding Bipartite Matching as a special case of Independent Set is a little trickier to see. Given a bipartite graph G′ = (V′, E′), the objects being chosen are edges, and the conflicts arise between two edges that share an end. (These, indeed, are the pairs of edges that cannot belong to a common matching.) So we define a graph G = (V , E) in which the node set V is equal to the edge set E′ of G′. We define an edge between each pair of elements in V that correspond to edges of G′ with a common end. We can now check that the independent sets of G are precisely the matchings of G′. While it is not complicated to check this, it takes a little concentration to deal with this type of “edges-to-nodes, nodes-to-edges” transformation.