Decentralized decision-making in a large team with local information. (Q1399517)

This paper is devoted to a problem involving a team of agents each associated with a node in a chain of indirected graph representing the relation of proximity between agents. Each agent makes a decision that influences only his cost and those of adjacent agents. Prior to making his decision, agent observes only the cost structure associated with nodes that can be reached by traversing no more than \(r\) arcs. Decentralized decisions are selected without any coordination in order to minimize average cost among agents. Cost is centralized if a single decision-maker has access to all information and dictates all decisions. The authors show that, to maintain a certain level of performance relative to optimal centralized strategies, deterministic strategies require \(r\) to be proportional to the number of agents. This means that the amount of information accessible to any agent should be proportional to the total number of agents, whereas these amounts are independent when stochastic strategies are used.