Correlated vs. Uncorrelated Randomness in Adversarial Congestion Team Games
arxiv(2023)
摘要
We consider team zero-sum network congestion games with n agents playing
against k interceptors over a graph G. The agents aim to minimize their
collective cost of sending traffic over paths in G, which is an aggregation
of edge costs, while the interceptors aim to maximize the collective cost by
increasing some of these edge costs. To evade the interceptors, the agents will
usually use randomized strategies. We consider two cases, the correlated case
when agents have access to a shared source of randomness, and the uncorrelated
case, when each agent has access to only its own source of randomness. We study
the additional cost that uncorrelated agents have to bear, specifically by
comparing the costs incurred by agents in cost-minimal Nash equilibria when
agents can and cannot share randomness.
We consider two natural cost functions on the agents, which measure the
invested energy and time, respectively. We prove that for both of these cost
functions, the ratio of uncorrelated cost to correlated cost at equilibrium is
O(min(m_c(G),n)), where m_c(G) is the mincut size of G. This bound is
much smaller than the most general case, where a tight, exponential bound of
Θ((m_c(G))^n-1) on the ratio is known. We also introduce a set of
simple agent strategies which are approximately optimal agent strategies. We
then establish conditions for when these strategies are optimal agent
strategies for each cost function, showing an inherent difference between the
two cost functions we study.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要