标题： 广义顶点着色博弈中的功利福利优化：对活动策划中场所选择的启示 显示英文标题

标题： Utilitarian Welfare Optimization in the Generalized Vertex Coloring Games: An Implication to Venue Selection in Events Planning

摘要： 我们考虑一类多智能体网络中的游戏，即广义顶点着色游戏（G-VCGs），这是受到事件策划中场所选择问题的实际应用启发的。 每个智能体在某种特定机制下会收到对当前着色分配的效用，由于只能获取局部信息，因此在选择另一种颜色时会自我组织。 我们的重点是在去中心化的方式下最大化一个关于网络中累积效用的功利主义型福利目标函数。 首先，我们研究了一类特殊的G-VCGs，即相同偏好VCGs（IP-VCGs），它恢复了\cite{chaudhuri2008network}的初步工作。 我们揭示了即使在完全贪婪策略和完全同步设置下，该模型也能收敛，并提供了收敛速率的随机界限。 其次，针对一般的G-VCGs，提出了一种保留贪婪性的Metropolis-Hasting基于的策略，使每个智能体能够从有限信息开始，并通过常规扰动马尔可夫过程的理论证明了其在异步设置下的最优性。 该策略在独立同步设置下也被实证证明是鲁棒的。 第三，在“鲁棒着色”的精神下，我们在目标函数中包含了一个期望损失项，以平衡效用和鲁棒性。 通过一个第二阶段的MH策略驱动算法，可以得到这种鲁棒福利优化的最优着色。 给出了仿真实验以展示我们所提出策略的效率。 显示英文摘要

摘要： We consider a general class of multi-agent games in networks, namely the generalized vertex coloring games (G-VCGs), inspired by real-life applications of the venue selection problem in events planning. Certain utility responding to the contemporary coloring assignment will be received by each agent under some particular mechanism, who, striving to maximize his own utility, is restricted to local information thus self-organizing when choosing another color. Our focus is on maximizing some utilitarian-looking welfare objective function concerning the cumulative utilities across the network in a decentralized fashion. Firstly, we investigate on a special class of the G-VCGs, namely Identical Preference VCGs (IP-VCGs) which recovers the rudimentary work by \cite{chaudhuri2008network}. We reveal its convergence even under a completely greedy policy and completely synchronous settings, with a stochastic bound on the converging rate provided. Secondly, regarding the general G-VCGs, a greediness-preserved Metropolis-Hasting based policy is proposed for each agent to initiate with the limited information and its optimality under asynchronous settings is proved using theories from the regular perturbed Markov processes. The policy was also empirically witnessed to be robust under independently synchronous settings. Thirdly, in the spirit of ``robust coloring'', we include an expected loss term in our objective function to balance between the utilities and robustness. An optimal coloring for this robust welfare optimization would be derived through a second-stage MH-policy driven algorithm. Simulation experiments are given to showcase the efficiency of our proposed strategy.