Achieving budget-balance with Vickrey-based payment schemes in exchanges

TLDR

Generalized Vickrey mechanisms are efficient and strategy‑proof, yet it is impossible for an exchange with multiple buyers and sellers to be both efficient and budget‑balanced, because a market‑maker must pay more than it collects. The study enforces budget‑balance as a hard constraint and investigates payment rules that distribute surplus after an exchange clears to minimize the distance to Vickrey payments. The authors enforce budget‑balance as a hard constraint and explore payment rules that allocate surplus after clearing to minimize deviation from Vickrey payments. Different rules yield varying truth‑revelation and efficiency, and analysis shows a simple Threshold scheme that gives surplus to agents whose payments differ from their Vickrey payments by more than a threshold reduces manipulation and boosts allocative efficiency compared to other simple rules.

Abstract

Generalized Vickrey mechanisms have received wide attention in the literature because they are efficient and strategy-proof, i.e. truthful bidding is optimal whatever the bids of other agents. However it is well-known that it is impossible for an exchange, with multiple buyers and sellers, to be efficient and budget-balanced, even putting strategy-proofness to one side. A market-maker in an efficient exchange must make more payments than it collects. We enforce budget-balance as a hard constraint, and explore payment rules to distribute surplus after an exchange clears to minimize distance to Vickrey payments. Different rules lead to different levels of truth-revelation and efficiency. Experimental and theoretical analysis suggest a simple Threshold scheme, which gives surplus to agents with payments further than a certain threshold value from their Vickrey payments. The scheme appears able to exploit agent uncertainty about bids from other agents to reduce manipulation and boost allocative efficiency in comparison with other simple rules.