New auction method for allocating routes in networks

Researchers studied how to assign routes in networks with limited capacity and transfer costs.

Researchers studied how to allocate routes between end nodes in networks with limited capacity and transfer costs. They introduced an origin--destination (OD) bidding language.

Participants bid for bounded conic combinations of inlet--outlet--quantity licences. The mechanism performs routing through a winner-determination problem that optimizes network-flow.

In a restricted model with uniformly priced sources, the Vickrey--Clarke--Groves (VCG) payment is core-stable. This happens because optimal aggregate flows never use a physical pipe in both directions.

In this regime, the problem reduces to a single-commodity network flow. The value of this flow is submodular in the set of active bidders.

If source access depends on the individual consumer, the reduction fails. In this general model, VCG payments may lie strictly outside the core.

The researchers propose a dual (nodal) pricing rule from the shadow prices of flow-conservation constraints. This rule is always core-stable, but it lacks dominant-strategy incentive compatibility.

Key facts

  • The OD mechanism uses a winner-determination problem to optimize network-flow.
  • VCG payments are core-stable when sources are openly and uniformly priced.
  • A dual (nodal) pricing rule is always core-stable in the general model.
  • The dual pricing rule comes at the cost of dominant-strategy incentive compatibility.

All sections

Edition