Network Intervention by Polling Strategic Agents

This work considers multi-agent coordination with arbitrary information networks among the agents using a game-theoretic approach. A system designer aims to assign local utility functions to the agents to guide their actions toward a desired system objective. The performance of the assigned local utilities is measured by the well known pure price of anarchy (pPoA) metric that equals the ratio of the system objective at the worst pure Nash equilibrium of the corresponding game to the optimal system objective. Our aim is to derive the utility functions which optimize the pPoA-based performance guarantees for any given information network and system objective. We develop a linear program that derives the optimal pPoA for any arbitrary information network and arbitrary system objective. Our work is the first to solve optimal utility design for arbitrary networks; our techniques generalize previous approaches which considered only the full-information setting. For supermodular objective functions, we prove that counterintuitively, a fully communication-denied utility design is optimal irrespective of the original information network. For submodular system objectives, an exhaustive numerical analysis suggests that the optimal utility design is robust to communication failures even for this case. When the system objective is weighted maximum coverage, the marginal contribution utility design provably optimizes the pPoA for a wide variety of information networks of interest.

Autonomous AI agents are becoming economic actors. They compose deadline-bound services across the device-edge-cloud continuum and contend for capacity no single operator owns. This article asks when decentralised pricing can coordinate them exactly and truthfully, and what their service dependencies must satisfy. We model the pipelines as service-dependency graphs under governance constraints and identify the decisive property: laminarity of the induced leaf-block family. Where it holds, the feasible allocation space is a polymatroid and efficient incentive-compatible clearing exists per epoch; where a crossing breaks it, exactness and truthfulness can fail, while clearing prices survive on every totally unimodular family. The formal results instantiate polymatroid, gross-substitutes and Vickrey-Clarke-Groves theory; the contribution is the bridge from dependency structure to that machinery and an integrator architecture that exposes a laminar interface. The node-level evaluation (32,020 runs), at testbed-calibrated congestion, locates the boundary. One crossing costs exactness in 14.7% of high-load rounds and none on laminar instances, and truthfulness fails where exactness does, across contention. An integrator's inner exposure restores exactness at a cost in admitted volume, and before translation overhead it cuts median latency by 16 to 17 percent. Against truth-free posted prices the tuned market leads at medium load and trails a demand-responsive one in four of six high-load cells. Recorded and composed agent workloads drive the allocation. For platform designers, laminar pipelines admit exact decentralised pricing, truthful under the VCG mechanism, and a crossing needs an integrator's inner exposure.

Organizations often pool dispersed information into one ranking and then allow many agents to act on that shared view. In a discovery problem, this can improve beliefs while reducing coverage. We develop an exactly solvable benchmark with sixteen boxes, one target, eight searchers, and noisy private clues. Pooling raises the accuracy of the best single recommendation from 0.20 to 0.3835, but repeating that recommendation lowers group discovery from 0.8322 under decentralized clue-following to 0.3835. A coordinated eight-action portfolio using the same pooled reports reaches 0.8594, and seven coordinated actions recover the decentralized benchmark. The paradox is a protocol failure, not an information failure: a one-answer rule compresses a portfolio of available actions into one repeated choice. We then replace the planner with self-interested searchers who split a prize. The equal-split game is a potential game. Its anonymous symmetric equilibrium obeys a water-filling rule. In the canonical instance it achieves 0.5991: strictly above consensus, but below both private search and the planner. The exact mixed price of anarchy is 2 - 1/N. A sole-rescue reward, which pays only an agent who covers the target alone, makes every pure Nash equilibrium first-best. Finally, a latent common-cue model shows how correlated reports collapse effective discovery channels. The centralized planner gain rises strictly with copying, and in the canonical environment the symmetric market overtakes decentralized report-following at copying probability c = 0.788462. In a proportional large-market limit the five-protocol ordering survives exactly: consensus discovery vanishes while blind, market, private, and portfolio search converge to 0.500, 0.547, 0.847, and 0.874. The contribution is a compact benchmark that separates information, allocation, incentives, and dependence into exact, reusable quantities.