Auction method allocates routes in networks with limited capacity
Auction-based allocation of routes in capacity-constrained networks
Computer Science and Game Theory
Summary
When networks have limited capacity and transfer costs, deciding who gets to use routes can be tricky. The authors study how to allocate these routes using auctions where participants bid for route licenses combined with amounts of flow. They show that under some conditions, a known payment system ensures stable and fair outcomes, but in more realistic cases where sources vary per user, they propose a different pricing method that guarantees stability but sacrifices some incentives. Examples illustrate their findings.
What this means in practice
- •For energy market operators: Design auction systems that allocate pipeline routes for gas considering capacity limits and transfer costs with guaranteed payment stability.
- •For telecommunications network planners: Deploy auction-based routing allocation that accounts for network capacity and link costs to optimize multi-user data flows.
Authors
Gergely Csáji, Dávid Csercsik
Abstract
We study the route-set allocation problem between end nodes in capacity-constrained flow networks with transfer costs. We introduce an origin--destination (OD) bidding language, in which a participant bids for bounded conic combinations of inlet--outlet--quantity licences and the mechanism performs the routing through a network-flow optimising winner-determination problem. We then study payment rules for the OD mechanism. Under a restricted model with openly and uniformly priced sources and bidders who are indifferent to the source of the gas, the Vickrey--Clarke--Groves (VCG) payment is core-stable; the key structural fact is that in this regime some optimal aggregate flows never use a physical pipe in both directions, so the winner-determination problem reduces to a single-commodity network flow whose value is submodular in the set of active bidders. If source access is allowed to depend on the individual consumer -- a realistic feature, e.g. when gas deals are embedded in bilateral political bargaining -- the reduction fails and VCG payments may lie strictly outside the core. For this general model we propose a dual (nodal) pricing rule derived from the shadow prices of the flow-conservation constraints, and prove it is always core-stable, at the cost of dominant-strategy incentive compatibility. Illustrative examples accompany each result.