在非原子路由策略中，针对信息设计的半定方法（CS GT）---Donuts_choco

我们研究出了一种存在于非原子代理下的路由策略。在该种情况下，处于不定网络状态中的连接延迟函数是有条件的。所有的代理针对前期状态都怀有相同的目标，但是只有固定比例的代理能够接受私有的路由推荐。这些推荐是有一个公开的“信号”产生的。该信号通过路由推荐将状态映射为概率分布。没有接收到私人推荐的代理就会通过关于前者的贝叶斯纳什流来选择路径。我们发明了一种计算方法，用于解决这种最优化信息设计问题。举个例子来说：通过所有“顺从的”信号来最小化预期的社会延迟成本。所谓“顺从的”信号就是指对于每一个代理来说，它自己推荐的路线几乎不优于后期信号诱导的路线。计算出如此独特的贝叶斯纳什流对于无推荐的代理来说是一个凸函数。鉴于流是由无推荐的代理接收产生的，我们将为有推荐的代理计算最优化信息设计问题视为对时机问题的一种泛化形式。对于仿射的延迟函数，我们研究了服从约束的结构和成本函数以求其能够考量单原子信号。这就暗示了最优信号的存在，并且最优矩量矩阵秩为1，因此信息设计问题能够恰好被半定程序解决。

我们提供数值证明存在一种交替计算的自然过程，在针对无推荐代理的贝叶斯纳什流和针对有推荐代理的最优信号之间来回切换，同时还能固定保持全局单调收敛状态。

原文题目：A Semidefinite Approach to Information Design in Non-atomic Routing Games

原文：We consider a routing game among non-atomic agents where link latency functions are conditional on an uncertain state of the network. All the agents have the same prior belief about the state, but only a fixed fraction receive private route recommendations. These recommendations are generated by a publicly known 'signal' which maps state to a probability distribution over route recommendations. The agents who do not receive recommendation choose route according to Bayes Nash flow with respect to the prior. We develop a computational approach to solve the optimal information design problem, i.e., to minimize expected social latency cost over all 'obedient' signals. A signal is obedient if, for every agent, its recommended route is weakly better than other routes with respect to the posterior induced by the signal. Computing the unique Bayes Nash flow for non-receiving agents under a given signal is known to be convex. Given flow induced by non-receiving agents, we cast the optimal information design problem for the receiving agents as an instance of the generalized problem of moments. For affine latency functions, we exploit the structure of the obedience constraint and the cost function to establish that it is sufficient to consider one-atomic signals. This implies that there exists an optimal signal whose moment matrix has rank one, and therefore the information design problem can be solved exactly by a semidefinite program. We provide numerical evidence to suggest that the natural procedure to alternate between computing Bayes Nash flow for non-receiving agents and optimal signal for receiving agents, while keeping the other fixed, is globally monotonically convergent.

原文作者：Yixian Zhu, Ketan Savla

原文地址：http://arxiv.org/abs/2005.03000