정규성 기반 단순화를 통한 계산적으로 효율적인 협업 통신

Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening

저희의 연구 결과는 짧고 효과적인 프로토콜만으로도 효율적인 통신이 가능하다는 것을 보여줍니다. 특히, $n$개의 가능한 관측값과 $m$개의 행동을 가진 게임에서: (1) 임의의 달성 가능한 목표 효용 값 $α$에 대해, 저희는 $ ext{poly}(n, m, 1/ε)$ 시간 내에 실행 시간을 가지는 알고리즘을 제시합니다. 이 알고리즘은 $2^{ ext{O}(CC_α(G))}/ ext{ε}^2$ 비트의 통신만을 사용하여 효용이 적어도 $α-ε$인 프로토콜을 설계합니다. 여기서 $CC_α(G)$는 목표 효용 값 $α$를 달성하는 데 사용되는 최소 비트 수이며, 계산적으로 비효율적인 프로토콜도 포함합니다. (2) 저희는 이 지수적 의존성이 $CC_α(G)$에 대해 상수 범위 내에서 최적이 아님을 증명했습니다. 즉, $ ext{P} = ext{NP}$가 아닌 경우, 일반적으로 다항 시간 알고리즘은 $2^{CC_α(G) - 2}$ 비트 미만의 프로토콜을 찾아낼 수 없습니다. 저희의 결과는 멀티 에이전트 정보 집계 분야의 기존 연구에서 요구되는 가정보다 훨씬 더 엄격한 조건을 완화하며, 상수 값의 $CC_α(G)$를 가지는 게임에서도 해결되지 않았던 부분을 채웁니다. 특히, 합의 기반 정보 집계를 위한 기존 보장은 정보 대체 또는 약한 학습 가능성과 같은 구조적 가정을 전제로 합니다. 저희는 이러한 가정들이 이미 $CC_α(G) = O(1)$을 의미하며, 따라서 저희 프로토콜이 성공하기 위해 필요한 조건보다 더 제한적인 조건을 나타낸다는 것을 보여줍니다. 기술적으로, 저희의 결과는 Frieze-Kannan의 약한 정규성 레마를 새롭게 강화하고 다음과 같은 강력한 다항 시간 변환 도구를 제공합니다. 모든 통신 게임 $G$에 대해, 이 도구는 에이전트의 관측 공간을 상수 크기의 파티션으로 단순화하는 게임 $ ext{G}$를 생성합니다. 이때, $G$와 $ ext{G}$는 모든 짧은 통신 프로토콜에 대해 구별할 수 없습니다. 이 단순화 정리는 저희 알고리즘의 핵심이며, 독립적인 연구 주제로도 가치가 있을 수 있습니다.

Our results show that the existence of a short high-utility protocol already suffices for efficient communication. In particular, in a game with $n$ possible observations and $m$ actions: (1) For any achievable target utility $α$, we give an algorithm with $\mathrm{poly}(n, m, 1/ε)$ runtime that designs a protocol achieving utility at least $α-ε$ using only $2^{\mathcal O(CC_α(G))}/ε^2$ bits of communication. Here, $CC_α(G)$ is the minimum number of bits used by any protocol, even a computationally inefficient one, to achieve utility $α$. (2) We prove that this exponential dependence on $CC_α(G)$ is tight up to a constant. That is, unless $\mathrm P=\mathrm{NP}$, no polynomial-time algorithm can in general find optimal protocols using fewer than $2^{CC_α(G) -2}$ bits. We note that our results strictly weaken the assumptions required by prior work in the multi-agent information aggregation literature, filling a gap that had remained elusive even for games with constant $CC_α(G)$. In particular, prior guarantees for agreement-based information aggregation rely on structural assumptions such as informational substitutes or weak learnability. We show that these assumptions already imply $CC_α(G) = O(1)$ and are therefore more restrictive conditions than required by our protocol to succeed. On a technical level, our results involve a novel strengthening of the Frieze-Kannan weak regularity lemma and yield the following powerful polynomial-time transformation tool: for every communication game $G$, it constructs a game $\hat G$ that is a coarsening of the agents' observation spaces into constant-size partitions, such that $G$ and $\hat G$ are indistinguishable with respect to every short communication protocol. This coarsening theorem is the engine behind our algorithm and may be of independent interest.