Research map / Multi-agent systems and games / Games and equilibria

A Unified Framework for Uniform-Price Resource Allocation Mechanisms

NeurIPS 2026 · Multi-agent systems and games › Games and equilibria · approach: Fair division and coalition formation · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces the alpha-proportional mechanism for divisible resource allocation, which uses scalar bids, proportional-style allocation x_i ∝ θ_i^{1/α}, and a uniform unit price, interpolating between the Kelly mechanism and first-price auctions with improved PoA and revenue guarantees vs VCG.

Problem

Resource allocation among strategic agents with private concave valuations: simple, scalar-bid mechanisms (like Kelly) lose efficiency (PoA 4/3), while efficient alternatives use complex allocations or non-uniform payments.

Approach

Scalar-parameterized proxy valuations θ_i f(x_i) with f(x)=x^{1-α}/(1-α); the allocation maximizing proxy welfare has a KKT dual multiplier λ that serves as a uniform unit price charged per unit of resource, giving the α-proportional mechanism with x_i ∝ θ_i^{1/α}.

Key results

• The alpha-proportional mechanism has PoA at most (1+sqrt(α))^2/(1+2sqrt(α)), recovering 4/3 for Kelly (α=1) and approaching 1 as α→0, with a matching lower-bound construction.
• Revenue at Nash equilibrium is at least 1/(1+α) of VCG revenue for linear valuations and for n=2 with general concave valuations.
• Hedge no-regret dynamics show exploitability approaching 0 in simulations with n=5 and beta in {0.5,0.75,1}; smaller α yields higher welfare when valuations are heterogeneous.

Surprising findings

• The first-price auction in this setting has PoA of n/2, despite the alpha-proportional mechanism's PoA approaching 1 as α→0 (a sharp phase transition).

Limitations

• Analysis assumes unconstrained divisible resource with simplex feasibility; budget-constrained bidders not handled (left to future work).
• Uniqueness of equilibrium requires differentiable, strictly increasing valuations.
• Revenue guarantees are only proven for linear valuations, n=2, or identical valuations in general.

Experimental setup

Metrics: price of anarchy social welfare exploitability revenue ratio vs VCG

Baselines: Kelly mechanism VCG ESPA Johari-Tsitsiklis mechanism first-price auction

Builds on: Kelly mechanism Johari and Tsitsiklis scalar-parameterized mechanism VCG ESPA mechanism

Closest papers by meaning

• Finding Fair Allocations under Budget Constraints (AAAI 2023 · similarity 0.88)
• Fair Allocation in Dynamic Mechanism Design (NeurIPS 2024 · similarity 0.87)
• On the Power of Randomization for Obviously Strategy-Proof Mechanisms (AAAI 2025 · similarity 0.87)
• Mechanism Design via the Interim Relaxation (NeurIPS 2025 · similarity 0.87)
• Plant-and-Steal: Truthful Fair Allocations via Predictions (NeurIPS 2024 · similarity 0.86)
• Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.86)