VI · Multi-AgentMature★★

Vickrey Auction Allocation

also known as Second-Price Sealed-Bid Allocation, Strategy-Proof Task Auction

Allocate a task to the lowest sealed bidder but pay them the second-lowest bid, making truthful cost reporting a dominant strategy.

This pattern helps complete certain larger patterns —

  • specialisesTool/Agent Registry★— Maintain a single queryable catalogue of both available tools and available agents, with metadata (capability, cost, latency, quality) the agent can use to pick the right one for a task.

Context

Multiple agents have heterogeneous private costs to perform a task — they know their own cost of compute, opportunity cost, or implementation cost. The allocator wants to assign the task to the cheapest agent. The agents are self-interested and will misreport if it gets them better payment.

Problem

A first-price sealed-bid auction (allocator picks the lowest bidder, pays them what they bid) gives agents an incentive to shade — bid higher than true cost. The winner makes more, but the allocator can't tell whether they paid the actual minimum cost. Worse, shading is itself uncertain, so agents waste cycles modelling each other's likely shading. The auction's clean economic property of allocating to the cheapest agent collapses under strategic behaviour.

Forces

  • Sealed-bid eliminates direct collusion during the auction.
  • First-price schemes incentivise strategic shading.
  • Truthful reporting is the right input for the allocator.
  • Payment difference (paid second-price, not own bid) is the bribe to be honest.

Example

A research-task allocator broadcasts 'analyse this 30-page filing' to five specialist agents who self-report cost (compute + opportunity). Bids come back at 50, 60, 65, 80, 100 credits. The 50-credit agent wins and is paid 60 (second-price). The next time around the agent has no incentive to bid above 50 — that risks losing the task without raising payment if it does win.

Diagram

Solution

Therefore:

The allocator broadcasts the task and a sealed bid window. Each candidate agent submits a sealed bid representing its true cost. The allocator picks the lowest bidder and pays the second-lowest bid. Vickrey's classical result: truthful bidding is the dominant strategy because bidding higher than true cost only loses opportunities while bidding lower lowers the payment without helping win. For multi-task generalisations, use Vickrey-Clarke-Groves (VCG) mechanisms. Distinct from contract-net (which doesn't specify the payment rule) and from first-price auctions (which incentivise shading).

What this pattern forbids. Task auctions among self-interested agents must not use first-price payment when strategy-proofness matters; the winner pays the second-lowest bid so truthful reporting is dominant.

And the patterns that stand alongside it, or against it —

  • complementsContract Net Protocol★★— Classical bid-based multi-agent task allocation: a manager broadcasts a task announcement, contractors submit bids, and the manager awards the contract to the best bid.
  • complementsCoalition Formation·— Agents form temporary subgroups around a task because the coalition can achieve more value than the sum of its members acting alone, with explicit rules for who joins and how payoff or credit is shared.
  • complementsTrust and Reputation Routing★— Maintain a per-agent reputation score updated from outcome quality and peer feedback, and route new tasks preferentially to high-reputation agents.

Neighbourhood

Click any neighbour to follow the language. Scroll to zoom, drag to pan.

Used in recipes

References

Provenance