12、匹配理论：从基础到物联网 - 雾 - 云系统的应用

匹配理论：从基础到物联网 - 雾 - 云系统的应用

1. 匹配理论基础

1.1 匹配模型分类

匹配理论中的匹配模型主要分为以下几类：
-一对一（OTO）匹配：在 OTO 匹配中，每个代理只能与另一个代理匹配。假设集合 $X$ 中的任意代理 $x$ 的偏好列表（PL）为 $P(x) = {y_2, y_4, x, y_1, y_3, \ldots}$，这意味着 $x$ 更喜欢 $y_2$ 胜过 $y_4$，并且比起与 $y_1$ 或 $y_3$ 匹配，$x$ 更愿意保持单身。OTO 匹配模型的结果是一个匹配函数 $M : X \cup Y \to X \cup Y$，需满足以下三个约束条件：
- 对于任意 $x \in X$，$M(x) \in Y \cup {x}$；
- 对于任意 $y \in Y$，$M(y) \in X \cup {y}$；
- 对于任意 $x \in X$ 和 $y \in Y$，$x = M(y)$ 当且仅当 $y = M(x)$。
匹配的目标是使所有配对达到稳定状态。如果不存在阻塞对 $(x, y)$，则匹配 $M$ 是成对稳定的。而 $(x, y)$ 是匹配 $M$ 的阻塞对需满足三个条件：$M(x) \neq y$，$y >_x M(x)$，$x >_y M(y)$。
-多对一（MTO）匹配：在 MTO 匹配模式中，一侧的每个代理可以与另一侧的多个代理匹配，但反之则不行。每个代理 $y$ 有一个正配额 $q_y$，表示它可以匹配的集合 $X$ 中代理的最大数量。例如，$P(y) = {x_1, x_2, y,