算法博弈论 W45 Mechanism design without money

last lecture about mechanism design

mechanism without money? kidney exchange and stable matching

Kidney exchange

patients with a final stage kidney disease in the waiting list for kidney transplant by a deceased donor.

已故捐献者肾移植等候名单中患有末期肾病的患者。

98k in the US, 800 in Denmark

demand>>supply!

Transplantations from living donors

活体移植

e.g. transplantation from mother to child

unfortunately, such transplantations are allowed between relatives and are not always possible

Incompatibilities of blood or tissue type

denote: donor $D$, patient $P$.

$D_1$ incompatible with $P_1$.

$D_2$ incompatible with $P_2$.

如果将这两个捐献对换一下，有可能:

$D_1$ compatible with $P_2$

$D_2$ compatible with $P_1$

Modeling

we are given a graph with nodes representing donor-patient pairs

edges are directed and denote the possibility of a successful transplantation from the donor of the origin node to the patient of the destination node

goal: find an optimal kidney exchanges

Applying the TTC algorithm

kidney exchange can be though of as house allocation.

• house allocation: initially, each participant has her house and the goal is to exchange houses so that the utility of participants involved in the exchanges increases
• kidney exchange: initially, each donor-patient pair has a kidney for donation and the goal is to exchange kidneys so that all patients involved in exchanges increase their utility

Drawbacks of the TTC algorithm

• long cycles
• a cycle of length 5 requires 10 surgery operations that have to run in parallel （同时摘除 5 个器官，然后同时移植 5 个器官）
• if some of the exchanges in a cycle is canceled, no exchange can take place.

Kidney exchange in practice

• matching computation 匹配计算

• input: undirected graph

• instead of a ranking of all available donors, each edge indicates mutual compatibility between two donor-patient pairs.

  每条边都表示两个供体-患者对之间的相互兼容性，而不是对所有可用供体进行排名（如果 A 捐献中的捐献者可以捐给 B 的接收者同时 B 捐献对的捐献者可以捐给 A 捐献对的接收者，那么 A 和 B 之间有一条连线）

• matching: set of edges which do not share any node

• goal: find a matching of maximum cardinality 最大基数匹配 in the input graph

• each node (patient) has a set $E_i$ of incident nodes (compatible donors)

• the patient can deny some of the possible donors

• preferences can be modeled by a subset $F_i\subseteq E_i$

• binary preferences: any transplantation is better than no transplantation

A direct revelation mechanism

• the patients report their preferred donors $F_i$
• build the graph having the donor-patient pairs are nodes and the edges which are desirable by both sides
• compute a matching of maximum cardinality in the graph

Question: is above mechanism DSIC? i.e. reporting $F_i=E_i$ a dominant strategy for every participant?

depends on how ties are resolved.

A priority mechanism

首先将所有捐献者-接收者对按某种条件（比如等待时长）进行排序 $1,2,\cdots,n$

Let $M_0$ be the set of all matchings of maximum cardinality

for $i=1,2,\cdots,n$ do

• let $Z_i$ be the set of matchings of $M_{i-1}$ that touch node $i$
• If $Z_i$ is empty, then $M_i=M_{i-1}$
• else $M_i=Z_i$

return an arbitrary matching of set $M_n$

The priority mechanism is DSIC!

Implementation issues of kidney exchange

• each donor-patient pair registers at a particular hospital

• so the hospital aims to serve the particular donor-patient pair to maintain its reputation.

  因此，医院的目标是为特定的捐赠者和患者提供服务，以维持其声誉

• kidney exchange programs: donor-patient pairs register at a hospital, each hospital sends the data for all its donor-patient pairs to a central authority, which computes which exchanges will take place.

ISSUE: No maximum matching mechanism is DSIC!!!

some node is always unmatched

then, the hospital having this node has incentive to hide some of its pairs from the central authority.

Stable matchings

how can we assign students to universities, interns to hospital etc?

Bipartite graph with node sets corresponding to $n$ men $(U)$ and $n$ women $(V)$

• each man has a preference ranking of the women
• each woman has a preference ranking of men
• goal: to match everyone in “marriages”
• in other words, to find a perfect matching

Let $M$ be a perfect matching between the nodes of sets $U$ and $V$.

we say that 2 nodes $u\in U$ and $v\in V$ is a blocking pair if node $u$ prefers $v$ and node $v$ prefers $u$.

a perfect matching is called stable if there is no blocking pair

Deferred acceptance algorithm

aka Gale-Shapley algorithm, abbr. DAA

while there is a man $u\in U$ without a match, do:

• man $u$ proposes to woman $v\in V$ that prefers the most if she hasn’t rejected him yet.

• if $v$ is unmatched, then they match temporarily.

• otherwise, if she is matched with man $u'$, then she selects to match temporarily with her most preferred man among $u$ and $u'$ and reject the other.

all temporary matches become permanent

Properties

theorem: algorithm DAA computes a stable matching after at most $n^2$ rounds

corollary 推论: a stable matching always exists.

for every man $u\in U$ let $h(u)\in V$ his most preferred woman among those he matched to in any stable matching:

theorem: the stable matching that algorithm DAA computes matches every man $u\in U$ to the woman $h(u)$ (man-optimal)

theorem: algorithm DAA is DSIC for men but not for women

关于延迟接受算法的一些证明

1. the algorithm computes a perfect matching

   all man will be matched.

2. stability

   between nodes $u,u'$ and $v,v'$.

   assume that algorithm yields a blocking pair: $u\lrarr v',u'\lrarr v$

   by definition of algorithm, since $u$ is matched to $v'$, and $u$ prefer $v$ to $v'$, he must have proposed to $v$ in some step. since $u$ is matched to some other woman at the end of algorithm, at some point, $v$ rejected $u$ for the better proposal. eventually, she declined this proposal for the worse one. This contradicts our definition.

   Hence, the pair is not a blocking pair.

   consider an execution of DAA

   Let $R$ be the set of man-woman pair $u,v$ s.t. $v$ rejected $u$’s proposal at some step.

   we will prove that no stable matching can contain any edge of $R$.

   induction on the iteration of algorithm:

   by defining $R_i=$ the set of $u,v$ pairs, s.t. $v$ rejected $u$ in some of the first $i$ iterations of the algorithm.

   for each $i=1,2,\cdots,n^2$, no stable matching contains any edge of $R_i$.

   when $i=0$, nothing to prove

   we assume that the statement holds for $i$: the $i$-th iteration and let $u,v$ be a pair of $R_{i}$. This means that at iteration $i$, women $v$ rejected the proposed of $u$ for a better proposal by $u'$. ($v$ prefers $u'$ to $u$) easy case 课本上没有 easy case 的证明

   difficult case: $v$ is not top in the list of $u'$: $u'$ prefers $v'$ to $v$, $v$ prefers $u'$ to $u$. now assume that some execution of the DAA matches $u$ and $v$. by induction of hypothesis, no pair of $R_{i-1}$ is included in any stable matching. Observe that $u',v'$ must belong to $R_{i-1}$, by induction hypothesis, this doesn’t appear in any stable matching. so $u'$ is matched to some $v''$ which is worse than $v$. thus $u',v$ is a blocking pair, contradicting stability.

3. at most $n^2$ steps

4. for accepter (woman), the mechanism is not DSIC

   we give a example here.

   man:

   A: X>Y>Z

   B: X>Z>Y

   C: Y>X>Z

   woman:

   X: C>A>B

   Y: A>C>B

   Z: ? 不用管，因为不会有人抢 Z

   匹配的结果应该是: AX, CY, BZ

   假如 X 谎报: C>B>A

   then the outcome will be: AY, BZ, CX

   这样，X 通过谎报偏好列表导致匹配到更好的选择。