Exact resource assignment speeds coordination among competing agents
Scaling Chance-Constrained Correlated Equilibrium Computation for Exclusive Resource-Assignment Games
Computer Science and Game Theory
Summary
Coordinating decisions among many agents competing for shared resources is hard because the number of possible combinations grows quickly. The authors propose a way to make coordination easier by insisting that each resource can only be assigned to one agent at a time. This reduces the number of possibilities that need to be considered without losing important fairness or incentive guarantees. They prove their method keeps the best stable outcomes and tested it in a scenario controlling departures from vertiports, speeding computation by over 99% while keeping good coordination.
What this means in practice
- •For air traffic coordinators: Optimize scheduling of aircraft at vertiport departure corridors with fast, robust coordination to safely assign exclusive use of shared airspace.
- •For cloud resource managers: Speed up assignment of exclusive cloud resources to competing agents for safer, more efficient coordination under uncertainty.
Authors
Jaehan Im, Ufuk Topcu, David Fridovich-Keil
Abstract
The chance-constrained correlated equilibrium concept provides a robust coordination technique for self-interested agents whose costs are uncertain to a central coordinator, but the number of joint actions considered in its computation grows exponentially with the number of agents. We propose an exact-one resource-assignment restriction for games in which agents compete for shared resources and simultaneous use of a resource is undesirable or unsafe. The restriction allows each resource to be assigned to exactly one agent, reducing the number of joint actions considered from O(2^(nr)) to O(n^r) for n agents and r resources. The resulting problem is solved over the restricted joint action set while retaining all incentive constraints associated with unilateral deviations. We show that the feasible set of the restricted problem is exactly the convex hull of the chance-constrained pure Nash equilibria contained in the exact-one assignment set, yielding a necessary and sufficient condition for nonemptiness. We further derive a sufficient condition under which all chance-constrained pure Nash equilibria of the unrestricted game are retained by the restriction. Numerical experiments in a vertiport departure-corridor coordination scenario demonstrate a 99.81% reduction in median computation time relative to the unrestricted formulation while achieving equivalent coordination performance.