Planner efficiently sets prices by polling neighbors of strategic agents
Network Intervention by Polling Strategic Agents
Computer Science and Game TheoryMultiagent SystemsSocial and Information Networks
Summary
Setting the best prices in a network where people act strategically is tricky, especially when their preferences are private and computations are costly. The authors show that an agent's importance in the network can be understood using a concept called 'centrality,' which helps break down the problem. They propose Poll, an algorithm that asks a few agents and their neighbors for information, then updates prices accordingly. This approach greatly reduces both the amount of communication needed and the number of queries, while ensuring truthful responses and good economic outcomes.
What this means in practice
- •For network policymakers: Set welfare-maximizing prices efficiently in large social or economic networks by selectively polling small groups of agents and their neighbors.
- •For telecommunications network operators: Reduce communication and computation costs when configuring strategic user-dependent pricing by using localized polling methods informed by network centrality.
Authors
Chenyu Zhang, Rohit Parasnis, Saurabh Amin
Abstract
A planner in a network of strategic agents faces three entangled challenges: the optimum depends on agents' private information, queried agents may misreport to steer the outcome, and exact computation does not scale. We study these challenges in multi-activity network games with heterogeneous private technologies, in which the planner sets non-discriminatory prices. We show that the optimal prices admit a centrality-based decomposition of the welfare kernel: each agent's contribution scales with its squared centrality in a network reweighted by agents' preferences across activities. This decomposition motivates Poll, a polling algorithm in which the planner samples one agent per round, walks briefly through the agent's neighborhood, and updates the price from a local report. From the same decomposition flow three forms of efficiency: computationally, Poll uses significantly fewer operations than exact computation and other distributed methods, requiring up to three orders of magnitude less communication on a real-world network with over 300,000 agents; statistically, its query complexity scales with topology and preference heterogeneity rather than explicitly with population size; and economically, it converges to welfare-maximizing prices while admitting behavior-specific implementations that induce truthful reports and detect adversarial deviations.