# Chapter 10. Matching Markets

[TOC]

## 10.1 Bipartite Graphs and Perfect Matchings

### Bipartite Graph
Let $G=(V,E)$ be an undirected graph, then $G$ is **bipartite** if $\exists\,A,B\subseteq V$ satisfy
- $A\cap B=\emptyset$
- $A\cup B=V$
- $\forall\,uv\in E$, $(u\in A\wedge v\in B)\vee(u\in B\wedge v\in A)$

### Matching
Let $G=(V,E)$ be a gragh, $M\subseteq E$ is a **matching** if
$$
\forall\,e_1\neq e_2\in M,e_1,e_2\text{ don't share the same endpoint}
$$

### Perfect Matching
A matching $M$ is **perfect matching** on graph $G$ if
$$
|M|=\frac{|V|}{2}
$$

### Neighbor
Let $G=(V,E)$, $S\subseteq V$, then the neighbor of $S$ is
$$
N(S):=\{v\in V\mid\exists\,u\in S,uv\in E\}
$$

### Constricted Set
Let $G=(A\cup B,E)$ be a bipartite graph, then $S\subseteq A$ is **constricted set** if
$$
|N(S)|<|S|
$$

:::info
**Theorem. Hall's Marriage Theorem**
Let $G=(A\cup B,E)$ with $|A|=|B|$, then
$$
G\text{ has a perfect matching}\Leftrightarrow|S|\leq |N(S)|\,\forall\,S\subseteq A
$$
in other words, if $G$ has no perfect matching, then $G$ contains a constricted set.
:::

## 10.2 Valuations and Optimal Assignments
Optimal Assignments

bipartite matching problem

## 10.3 Prices and the Market-Clearing Prices
Replace the role of the administrator by a scheme for pricing items

- Example
- There is a collection of sellers, each with a house for sale, and an equal-sized collection of buyers, each of whom wants a house.
- $v_{ij}$ means the valuation that a buyer $j$ has for the house held by seller $i$. (0 or positive integer)
### Prices and Payoffs.
- Suppose each seller $i$ sells it for a price $p_i ≥ 0$.
- If a buyer $j$ buys the house from seller $i$ at this price, the buyer’s ***payoff*** is $v_{ij} − p_i$.
- We call the seller(s) that maximize the payoff for buyer $j$ the ***preferred sellers*** of buyer j (payoff from sellers $\ge0$)

### Market-Clearing Prices.
- For a set of prices, define the ***preferred-seller graph*** by constructing an edge between each buyer and her preferred seller(s).
- A set of prices is ***market clearing*** if the resulting preferred-seller graph has a perfect matching.


$(b)$: market clearing
$(c)$: no
$(d)$: yes, tie-breaking is required
### Properties of Market-Clearing Prices.
:::warning
***TODO***
:::

:::info
**Optimality of Market-Clearing Prices:**
For any set of market-clearing prices, a
perfect matching in the resulting preferred-seller graph has the maximum total
valuation of any assignment of sellers to buyers.
:::

:::success
**Argument**
Consider a set of market-clearing prices, and let $M$ be a perfect matching in the preferred-seller graph.
Each buyer buys the house that maximizes her payoff
$\Rightarrow \space M$ has the maximum total payoff of any assignment of houses to buyers
If buyer $j$ chooses house $i$, payoff $v_{ij} − p_i$.
$\Rightarrow \space$Total Payoff of $M$ = Total Valuation of $M$ − Sum of all prices.
So a matching $M$ that maximizes the total payoff is also
one that maximizes the total valuation.
:::

:::info
**Optimality of Market-Clearing Prices (equivalent version):**
A set of market-clearing prices, and a perfect matching in the resulting preferred-seller graph, produces the maximum possible sum of payoffs to all sellers and buyers.
:::

## 10.4 Constructing a Set of Market-Clearing Auctions?
:::info
**Existence of Market-Clearing Prices:**
For any set of buyer valuations, there
exists a set of market-clearing prices.
:::

All sellers set their prices to 0
while True:
    // There is a current set of prices, with the smallest one equal to 0.
    
    Construct the preferred-seller graph 
    if there is a perfect matching:
        done //the current prices are market-clearing.
    else:
        find a constricted set of buyers S and N(S).
        // The buyers in S only prefer the sellers in N(S)
        // but #(sellers in N(S)) < #(buyers in S)
        for each seller s in N(S):
            s.price ++
        
        // Let the smallest price becomes zero.
        min_price = the smallest price
        if min_price != 0:
            for each seller s:
                s.price -= min_price


**Showing That the Auction Must Come to an End.**
Use “potential energy”
- Suppose
- ***potential of a buyer*** := max payoff she can get
- ***potential of a seller*** := current price he is charging.
- ***potential energy of the auction*** := sum of the potential of all participants
- Initial
- potential of each seller = 0
- potential of each buyer = her maximum valuation for any house
- potential energy of the auction $= P_0 \ge 0$
- Each round
- potential energy of the auction $\ge 0$
- potential only changes when the prices change
- reduction
- if we subtract $p$ from each price, then the potential of each seller drops by $p$, but the potential of each buyer goes up by $p$
- raise their prices by one unit
- potentials of each seller in $N(S)$goes up by 1.
- potential of each buyer in $S$ goes down by 1
- $S$ has strictly more nodes than $N(S)$ does $\Rightarrow$ potential of the auction goes down by at least 1
- Must done in $P_0$ rounds

## 10.5 How Does This Relate to Single-Item Auctions?
We have a set of $n$ buyers and a single seller auctioning an item.
Let buyer $j$ have valuation $v_j$ for the item.

Mapping:
- Create $n − 1$ “fake” additional sellers
- Lable real seller be 1. And $v_{1j} = v_j$
- $v_{ij} = 0$ for $i\gt1$ and each buyer $j$.


## 10.6 Advanced Material: A Proof of the Matching Theorem

:::info
**Definition.**
***Matching Theorem:*** If a ***bipartite graph*** (with equal numbers of node on the left and right)
has no ***perfect matching***, then it ==must== contain a ***constricted set***.
:::

### Alternating and Augmenting Paths

:::info
**Definitions.**
* ***Simple path***: A path does not repeat any nodes.
* ***Alternating path***: A simple path that alternates between non-matching and matching edges.
* ***Augmenting path***: A alternating path with unmatched endpoints is an augmenting path.
>
:::

* If there's a ***augmenting path*** in ***bipartite graph*** with a matching,
then the matching can be enlarged.

### Searching for an Augmenting Path

***Alternating BFS***

BFS(G)
    let Q be a queue
    parent[1..n] = {NIL}
    
    s = a unmatched node on right
    Q.enqueue(s)
    mark s as visited
    
    while(Q is not empty)
        u = Q.dequeue()
        
        for all neighbors v of u
            if v is visited 
                continue
                
            //Right nodes    
            if u is on right and (u,v) is a non-matching edge
                Q.enqueue(v)
                parent[v] = u
                mark v as visited
                
            //Left nodes    
            if u is on left  and (u,v) is a matching edge
                Q.enqueue(v)
                parent[v] = u
                mark v as visited


---

### Augmenting Paths and Constricted Sets

:::info
**Question.**
If we can't find an ***augmenting path***, can we conclude that there is a ***constricted set*** ?
:::

* We now show if there's no augmenting path, we can find constricted sets.

:::success
**Consider a failed search for alternating BFS**

Observe that
1. Even-numbered layers consist of nodes from right-hand side,
odd-numbered layers consist of nodes from left-hand side.
2. Layers $2n$ has exactly the same number of nodes as layers $2n-1$
3. There are ==strictly== more nodes in even layers overall than there are in odd layers
4. Neighbors of nodes in Layers $2n$ present in layer $2n-1$, layer $2n+1$ </br>and odd layer $k < 2n$

So, by observation 3 and 4, we can conclude that
**In a failed alternating BFS, the set of nodes in all even layers forms a constricted set.**
:::

Example.


---

### The Matching Theorem.

:::info
**Definition.**
***Matching Theorem:*** If a ***bipartite graph*** (with equal numbers of node on the left and right)
has no ***perfect matching***, then it ==must== contain a ***constricted set***.
:::

:::success
**Proof.**
Suppose that there's a ***bipartite*** graph with an equal number of nodes on the left and right, </br> and it has **no** perfect matching.
1. Considering its maximum matching, since this matching is not perfect, there's a unmatched node $W$ on right-hand side.
2. We know that there is no any ***augmenting path*** beginning at any node, since then we would be able to enlarge the matching.
3. Since there is no ***augmenting path*** beginning at $W$, we will have a **failed alternating BFS** search, and by conclusion above, there must be a ***constricted set*** containing $W$
:::

## Additional

### Determine a graph is bipartite or not

* Simply use a BFS

Bipartite(G,s)
    let Q be a queue
    mark[1..n] = {-1} // not visited -1, right node 0, left node 1
    
    mark[s] = 1
    Q.enqueue(s)
    
    while(Q is not empty)
        u = Q.dequeue()
        
        for neighbors v of u
            if mark[v] == mark[u]
                return NO
            if mark[v] == -1
                mark[v] = mark[u] ^ 1
    
    return YES

### Find a perfect matching in a bipartite graph

* Reduce to Maximum Flow