最优轮次拜占庭协议与多方博弈公平硬币抛掷的研究

# 最优轮次拜占庭协议与多方博弈公平硬币抛掷的研究 ## 一、最优轮次拜占庭协议 ### 1. 数值边界推导 在最优轮次拜占庭协议的研究中，有一个关键的数值边界推导。对于 $\frac{\ell}{M} (\max UL - \min UL)$ 有如下推导： $\frac{\ell}{M} (\max UL - \min UL) \leq \ell \cdot \frac{1}{LL} \left(\frac{t}{n - 2t}\right)^L + \frac{\ell}{M} \cdot L$ $\leq \ell \cdot \frac{1}{LL} \left(\frac{t}{n - 2t}\right)^L + \frac{\ell}{\binom{n - 2t}{t}} L \cdot LL + 1 \cdot L$ $\leq \ell \cdot \frac{1}{LL} \left(\frac{t}{n - 2t}\right)^L + \ell \cdot \frac{1}{LL} \cdot \left(\frac{t}{n - 2t}\right)^L$ $= 2\ell \cdot \frac{1}{LL} \left(\frac{t}{n - 2t}\right)^L$ $\leq \ell \cdot \frac{\ell - 1}{1} = 1$ 这里最后一个不等式使用了 $\ell \geq 1$，这是由 $t = (1 - \epsilon) \cdot \frac{n}{2}$ 和 $L \geq \frac{1 - \epsilon}{\epsilon}$ 推导得出的。 ### 2. 技术组合引理 #### 2.1 问题设定 考虑一个按升序排序的包含 $k$ 个值的数组 $A$，以及一个数 $s < \frac{k}{2}$。再考虑按如下方式创建的数组 $T_1$：$T_1$ 在一个固定集合 $I_1$ 的索引处缺失一些值，然后移除最低和最高的 $s - |I_1|$ 个值。类似地，考虑以相同方式创建但使用索引集合 $I_2$ 的数组 $T_2$。 设 $b$ 是数组 $T_1$ 或 $T_2$ 中剩余值的最大值，$a$ 是最小值。则有如下组合引理：$T_1$ 和 $T_2$ 中剩余值的平均值之差至多为 $\frac{\max(|I_1|, |I_2|)}{k - 2s + \max(|I_1|, |I_2|)}$ 乘以 $(b - a)$。 #### 2.2 引理内容 **引理 8**：设 $A = [A_0, A_1, \cdots, A_{k - 1}]$ 是一个数组，其中 $A_0 \leq A_1 \leq \cdots \leq A_{k - 1}$。设 $s < \frac{k}{2}$，$I_1, I_2 \subseteq \{0, 1, \cdots, k - 1\}$ 是两个索引集合，使得 $|I_1 \cup I_2| \leq s$。考虑按如下方式构造的数组 $T_1 = [T_{10}, T_{11}, \cdots, T_{1(k - 1)}]$ 和 $T_2 = [T_{20}, T_{21}, \cdots, T_{2(k - 1)}]$：对于 $j \in \{1, 2\}$，首先如果 $i \notin I_j$，则 $T_{ji} = A_i$，否则 $T_{ji} = \perp$，然后将 $T_j$ 中最低和最高的非 $\perp$ 的 $s - |I_j|$ 个值替换为 $\perp$。则有： $|\text{avg} \{T_{1i} \neq \perp\}_{i \in [0, k - 1]} - \text{avg} \{T_{2i} \neq \perp\}_{i \in [0, k - 1]}| \leq \frac{\max (|I_1|, |I_2|)}{k - 2s + \max (|I_1|, |I_2|)} (b - a)$ 其中 $b = \max\{T_{ji} \neq \perp\}_{j \in \{1, 2\}, i \in [0, k - 1]}$，$a = \min\{T_{ji} \neq \perp\}_{j \in \{1, 2\}, i \in [0, k - 1]}$。 #### 2.3 引理证明 设 $m_1 := |I_1|$，$m_2 := |I_2|$。不失一般性，假设 $m_1 \geq m_2$，这意味着 $T_1$ 包含的非 $\perp$ 值至少和 $T_2$ 一样多。 设 $v_1 := \text{avg} \{T_{1i} \neq \perp\}_{i \in [0, k - 1]} = \frac{1}{|\{T_{1i} \neq \perp\}|} \sum_{\{i:T_{1i} \neq \perp\}} T_{1i}$，$v_2 := \text{avg} \{T_{2i} \neq \perp\}_{i \in [0, k - 1]} = \frac{1}{|\{T_{2i} \neq \perp\}|} \sum_{\{i:T_{2i} \neq \perp\}} T_{2i}$。 首先，$T_1$ 中非 $\perp$ 值的数量为：$|\{T_{1i} \neq \perp\}| = k - 2(s - m_1) - m_1 = k - 2s + m_1$。 类似地，$|\{T_{2i} \neq \perp\}| = k - 2s + m_2$。 然后得到： $v_1 - v_2 = \frac{\sum_{\{i:T_{1i} \neq \perp\}} T_{1i}}{k - 2s + m_1} - v_2 = \frac{\sum_{\{i:T_{1