自私用户不可拆分流网络设计的难度分析

### 自私用户不可拆分流网络设计的难度分析 #### 1. 引言 在大规模网络系统中，路由机制是关键组成部分，其目的是为流量选择从发送者到接收者的通信路径。在多数网络场景，如互联网、无线网络等，流量通常通过单一路径传输，因为拆分流量会导致接收端的数据包重组问题。同时，由于难以维持一个集中式的权威机构来为网络流量制定高效的路由策略，用户往往会独立且“自私”地行动，即每个用户根据当前网络流量情况，试图最小化自己的流量成本。 这种情况可以用经典博弈论进行数学形式化。网络用户被视为参与非合作博弈的独立个体，每个个体都希望在其他个体造成的链路拥塞情况下，选择从源到目的地的最小延迟路径。当没有个体有动机改变其从源到目的地的路径时，系统达到纳什均衡。然而，纳什均衡通常并不能优化社会福利，可能与全局最优解相差甚远。 网络性能因缺乏集中式权威机构而下降的程度，可以用最坏情况协调比率（无政府代价）来衡量，它是最坏可能的纳什均衡与社会最优解之间的比率。此外，Braess 悖论表明，从网络中移除边有时可以改善其性能，这也促使我们思考如何设计自私用户网络，以最小化纳什均衡中固有的低效率。 #### 2. 相关定义和预备知识 - **模型**：我们考虑加权网络拥塞博弈模型，其中有一个有向图 $G = (V, E)$，每条边 $e \in E$ 都有一个依赖于负载的延迟函数 $f_e : R^+ \to R^+$。有 $n$ 个用户，用户 $j$ 有一个带宽请求，由元组 $(s_j, t_j, w_j)$ 定义，其中 $s_j, t_j \in V$ 是源/目的地对，$w_j \in R^+$ 是所需带宽。我们用 $Q_j$ 表示 $s_j - t_j$ 路径的集合，请求 $j$ 可以分配到 $Q_j$ 中的任何路径 $Q$，并且需要在路径 $Q$ 上预留所需带宽 $w_j$。 - **纯策略定义**：对于纯策略系统 $S = (Q_1, \ldots, Q_n)$，我们定义 $J(e) = \{j|e \in Q_j\}$ 为分配到包含边 $e$ 的路径的请求集合，边 $e$ 上的负载为 $l_e = \sum_{j \in J(e)} w_j$。对于最优路由，我们类似地定义 $J^*(e)$ 和 $l^*_e$。用户 $j$ 将其请求分配到路径 $Q$（而不是路径 $Q_j$）的延迟定义为： \[c_{Q,j} = \sum_{(e \in Q) \land (e \in Q_j)} f_e(l_e) + \sum_{(e \in Q) \land (e \notin Q_j)} f_e(l_e + w_j)\] - **纳什均衡和协调比率**： - 纳什均衡的定义为：一个系统 $S$ 处于纯纳什均衡，当且仅当对于每个 $j \in \{1, \ldots, n\}$ 和 $Q \in Q_j$，有 $c_{Q_j,j} \leq c_{Q,j}$。 - 给定纯策略系统 $S$ 的成本 $C(S)$ 定义为 $S$ 产生的总延迟，即 $C(S) = \sum_{e \in E} f_e(l_e)l_e$。 - 协调比率 $R$ 定义为 $R = \max_S \frac{C(S)}{C(S^*)}$，其中最大值是在所有纳什均衡策略 $S$ 上取得。 - **网络设计问题形式化**： - **网络设计问题**：给定一个加权网络拥塞博弈和有向图 $G = (V, E)$，找到 $G$ 的一个子图 $H$，使得 $C(H)$ 最小。 - **选择性网络设计问题**：给定一个加权网络拥塞博弈、有向图 $G = (V, E)$ 和 $E_1 \subseteq E$，找到 $G$ 的一个包含 $E_1$ 中边的子图 $H$，使得 $C(H)$ 最小。 #### 3. 网络设计的不可近似性 ##### 3.1 线性延迟函数 当每条边的延迟与边拥塞呈线性关系时，即 $f_e(x) = a_ex + b_e$（$a_e$ 和 $b_e$ 为非负实数），我们考虑网络设计问题。 一个简单的算法是输出整个网络 $G$。可以证明，对于线性延迟函数，这个简单算