Some coordination problems are harder than others
In order to coordinate players in a game must first identify a target pattern of behaviour. In this paper we investigate the difficulty of identifying prominent outcomes in two kinds of binary action coordination problems in social networks: pure coordination games and anti-coordination games. For both environments, we determine the computational complexity of finding a strategy profile that (i) maximises welfare, (ii) maximises welfare subject to being an equilibrium, and (iii) maximises potential. We show that the complexity of these objectives can vary with the type of coordination problem. Objectives (i) and (iii) are tractable problems in pure coordination games, but for anti-coordination games are NP-hard. Objective (ii), finding the best Nash equilibrium, is NP-hard for both. Our results support the idea that environments in which actions are strategic complements (e.g., technology adoption) facilitate successful coordination more readily than those in which actions are strategic substitutes (e.g., public good provision).
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Improving a Strong Neural Parser with Conjunction-Specific Features
While dependency parsers reach very high overall accuracy, some dependency relations are much harder than others. In particular, dependency parsers perform poorly in coordination construction (i.e., correctly attaching t…
Dependency ParsingSequential Communication in Multi-Agent Reinforcement Learning
Coordination is one of the essential problems in multi-agent reinforcement learning. Communication provides an alternative for agents to obtain information about others so that better coordinated behavior can be learned.…
Decision MakingMulti-agent Reinforcement Learningreinforcement-learningReinforcement Learning+1Some Targets Are Harder to Identify than Others: Quantifying the Target-dependent Membership Leakage
In a Membership Inference (MI) game, an attacker tries to infer whether a target point was included or not in the input of an algorithm. Existing works show that some target points are easier to identify, while others ar…
Federated LearningRational Inattention and Perceptual Distance
This paper uses an axiomatic foundation to create a new measure for the cost of learning that allows for multiple perceptual distances in a single choice environment so that some events can be harder to differentiate bet…
counterfactualPerceptual DistanceCodeCRDT: Observation-Driven Coordination for Multi-Agent LLM Code Generation
Multi-agent LLM systems fail to realize parallel speedups due to costly coordination. We present CodeCRDT, an observation-driven coordination pattern where agents coordinate by monitoring a shared state with observable u…
Code Generation