Priority Algorithm I need to prove the theorem below in detail for the priority algorithm, which is an algorithm for the third step of the initial pairwise kidney exchange algorithm. I just need an idea for proving that an algorithm is DSIC. I tried to do it with contradiction but I couldn't figure it out, because if I assume that an agent misreports and has a better outcome, then what would be a better outcome? An agent either matches or doesn't match. Misreporting can't make a matching happen that otherwise(in the truthful case) wouldn't happen. How can I show this mathematically?
Theorem(Priority Mechanism Is DSIC): In the priority mechanism for pairwise kidney exchange, for every agent i and reports by the other agents, no false report $F_i \subset E_i$ yields a better outcome for i than the truthful report $E_i$.
In this context, a matching refers to a subset of edges within an undirected graph where no endpoints are shared. For kidney exchange, the relevant graph consists of a vertex set V representing incompatible patient-donor pairs, with each pair represented by a vertex. An undirected edge connects vertices (P1, D1) and (P2, D2) if and only if P1 and D2 are compatible, as well as P2 and D1.
It is assumed that each patient possesses a set $E_i$ of compatible donors from other patient-donor pairs and can disclose any subset $F_i \subseteq E_i$ to a mechanism. Patients have the option to decline proposed kidney exchanges for any reason, allowing for the possibility of misreporting by refusing exchanges in $E_i \setminus F_i$.
We implement the mechanism by arranging the vertices $V = \{1, 2,\dots, n\}$ of graph G in descending order of priority.
The proof I did(which doesn't satisfy me in a mathematical sense):
To prove the Theorem, we need to show that no agent can benefit from submitting a false report $F_i \subset E_i$ in the priority mechanism for pairwise kidney exchange. In other words, the outcome for each agent i is not improved by deviating from the truthful report $E_i$. Suppose there exists an agent $i$ who submits a false report $F_i$. Let agent j be the compatible agent with agent i that i misreports. Furthermore, let agent j be more prioritized than agent i, which means $j < i$ ($i < j$ analogous). Because i reports j as incompatible, the truthful report of j makes no difference and there is no edge $(i, j) \in E$. In this case there isn't any maximum matching that matches i with j in $M_0$. Let $Z_j \subseteq M_{j-1}$ denote the set of matchings that match j within the matchings that already matched agents 1 to $j-1$ if possible.
Case 1 $Z_j = \emptyset$ : There is no maximum matching that matches j and also more prioritized agents. Thus, the algorithm sets $M_j = M_{j-1}$. Let $Z_i \subseteq M_{i-1}$ denote the set of matchings that match i within the matchings that already matched agents 1 to $i-1$, including j, if possible.
Case 1.1 $Z_i = \emptyset$ : There is no maximum matching that matches i and also more prioritized agents. Thus, the algorithm sets $M_i = M_{i-1}$. And the algorithm terminates with a maximum matching that doesn't match i with any other agent. However, if agent i had reported truthfully, there would have been a kidney exchange between the agents i and j additional to already existing exchanges. Hence, the misreport of agent i affects the outcome against agent i, demonstrating that submitting a false report is disadvantageous.
Case 1.2 $Z_i \neq \emptyset$: There is at least one matching that matches i and also more prioritized agents. The algorithm sets $M_i = Z_i$ and because the following iterations can't unmatch a more prioritized agent, the misreport of agent i doesn't change the outcome in a more advantageous way for agent i.
Case 2 $Z_j \neq \emptyset$ : There is at least one matching that matches j and also more prioritized agents. Thus, the algorithm sets $M_j = Z_j$.
Case 2.1 $Z_i = \emptyset$: There is no maximum matching that matches i and also more prioritized agents. Thus, the algorithm sets $M_i = M_{i-1}$. And the algorithm terminates with a maximum matching that doesn't match i with any other agent. If agent j is matched with an agent who is less prioritized than agent i, this means that misreporting affects agent i negatively. Otherwise, agent j would match with agent i and the set $Z_i$ wouldn't be empty.
Case 2.2 $Z_i \neq \emptyset$: There is at least one matching that matches i and also more prioritized agents. Just like in case 1.2, the misreporting doesn't yield a better outcome for agent i.
Therefore, we conclude that the priority mechanism for pairwise kidney exchange is dominant strategy incentive compatible (DSIC). No agent has an incentive to submit a false report, and reporting truthfully always leads to an outcome that is at least as good as any possible outcome obtained through false reporting.