博弈论(研究生课程)期末作业 (4)
https://ieeexplore.ieee.org/abstract/document/8598984
3. 系统模型和问题定义（SYSTEM MODEL AND PROBLEM DEFINITION）
3.1. 系统模型（System Model）
在“系统模型与问题定义”这一节的“系统模型”小节中，作者首先介绍了已经被深入研究的流式划分模型。在流式顶点划分问题中，顶点与其邻居集合一起到达；在流式边划分问题中，每条边与其两个端点一起到达。在这两种变体中，启发式决定将当前顶点或边放置在某个分割上，这个决定是基于所有先前顶点或边的划分选择，这是通过维护一个全局表来实现的，该表记录了所有先前顶点或边的划分选择。
然后，作者提到了一些存在的问题，例如基于度的启发式（如DBH和HDRF）在边划分问题中，需要维护一个额外的度表来记录每个顶点的度信息。在实际的流式场景中，流可能非常大甚至无限大，因此这些解决方案在巨大表的内存使用和在这样一个巨大表上的低效查找方面可能是低效的。此外，由于全局表的读取和写入强度大，很难并行进行划分。
为了解决这些问题，作者提出了准流式模型，目标是实现更多的并行性和更少的内存使用。他们定义了准流式划分模型，全图由一个边流表示，每条边与其端点一起到达。整个流被划分为一系列批次，批次大小作为一个输入参数，它是分割数量的常数倍。分割数量k也是一个输入参数。在每个批次中，划分问题被建模为一个博弈过程。当找到一个纳什均衡时，这个批次的划分就完成了。
在准流式模型中，当前边可以通过迭代的方式充分利用同一批次内其他边的划分选择，这可以比基于流式的解决方案实现更好的局部最优。无需维护一个巨大的全局表来记录所有先前边的选择，我们只使用一个本地表来记录同一批次内其他边的选择，这比全局表小得多。此外，当当前批次完成其划分后，可以重用本地表的内存。
在后续的章节中，作者将给出更多的细节，包括找到纳什均衡的方法，以及如何基于最佳响应动态的算法。
3.2. 策略博弈理论（Strategic Game Theory）
作者将边分割问题在每一批次（batch）中建模为一种博弈的方法。在博弈论中，博弈的每个参与者（在这篇论文中，参与者是边）被假设为自私且理性的，每个参与者都试图优化自己的目标函数（或者说最小化自己的成本函数）。
作者在这里进一步解释，每个参与者（即每条边）在选择一种策略（即选择被分到哪个分割）来最小化自己的成本时，并不考虑自己的选择对其他参与者的目标函数的影响。这是博弈论中所说的”自私”和”理性”的含义：每个参与者都关心的是自己的利益，而不是整个系统的利益。
“Formally, a strategic game is defined as:…”这句话似乎是在为接下来的定义做铺垫，可能会提到博弈的参与者、策略空间和目标（或成本）函数等元素。然而，由于这句话后面的内容并没有给出，所以无法给出更具体的解释。
- 玩家列表 $\mathbb{N}=\{1,2,\dots,N\}$；
- 策略空间 $\mathbb{S}=S_1\times S_2\times\cdots\times S_N$，其中$S_i$是第$i$个玩家的策略；
- 策略实例 $S=(S_1,S_2,\dots,S_N) \in\mathbb{S}$ ，也有$S=(S_i,S_{-i})$；
- 代价函数 $C_i(S): \mathbb{S}\rightarrow\mathbb{R}$，策略实例对于第$i$个玩家的策略的代价；
- 策略博弈 $\mathbb{G}=\{\mathbb{N},\mathbb{S},\{C_1,C_2,\dots,C_N\}\}$ 唯一表示；
- 社会福利 $\sum_{i\in\mathbb{N}}C_i(S)$，目标是最小化所有玩家的总代价。
定义1、2：
- A pure strategy provides a complete definition of how a player will play a game for any situation.
- The pure strategy profile $S^*\in\mathbb{S}$ is pure strategy Nash Equilibrium iff for each $i\in\mathbb{N}$:
\begin{equation} C_i(S^*_i,S^*_{-i})\leq C_i(S’_i,S^*_{-i}) \end{equation}
where $S’\neq S^*,S’\in S_i$ is another strategy。
3.3. 问题定义（Problem Definition）
定义：整个图流（Graph Stream）⁍中的每批（Batch）表示为子图⁍
$$ \begin{equation} \min{1\over|V|}\sum_{v\in V}|Rep(v)|,\space\text{s.t.}\max_{p_i\in P}L(p_i)<\lambda{|E|\over k} \end{equation} $$
其中$Rep(v)\subseteq P$为顶点$v$的所有副本（replicas including master replica and mirror replicas） $\lambda\geq1$是一个很小的常数，$P=\{p_1,p_2,…,p_k\}$是分割集合，$L(p_i)$表示$p_i$所有批的边数和；也就是说，$\sum_{i=1}^kL(p_i)=|E|$。边分割时一个NP-hard问题。
本文中的图分割质量是通过以下两个指标来衡量的：
- $\sigma$(Standard deviation of edge load)：每个分割中承载的边数的标准差；
- $rep$(Replication factor)：每个顶点的平均复制次数，定义为${1\over|V|}\sum_{v\in V}|Rep(v)|$。
我们的负载均衡指标$\sigma$不同于相对标准偏差（Relative Standard deviation）指标，后者被定义为$\sigma$与平均负载的比率。$\sigma$度量也不同于最大负载与平均负载之比的度量。请注意，我们的偏差标准$\sigma$是比这两个衡量负载平衡状态的指标更严格的指标，这可能会在负载平衡方面进一步区分分割策略。