Research map / Multi-agent systems and games / Games and equilibria
Automated Design of Affine Maximizer Mechanisms in Dynamic Settings
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.
Extends affine maximizer mechanisms to MDPs with untruthful reward reports and optimizes weights and boosts via bilevel optimization (grid search, zeroth-order, and regularized-LP gradients), beating dynamic VCG on auctions, task scheduling, and gridworld.
Problem
Designing strategyproof dynamic mechanisms on MDPs that optimize goals beyond welfare (e.g., revenue, makespan) without restrictive assumptions on agent valuations.
Approach
Define dynamic affine maximizer mechanisms on MDPs (weights plus state-action boosts over affinely transformed welfare) that are strategyproof by construction, and search their parameters via a bilevel formulation solved with grid search, zeroth-order gradient estimates, or gradients through an entropy-regularized LP; proves revenue is differentiable almost everywhere in expectation.
Key results
- In sequential sales, optimized AMAs improve revenue over VCG by up to 35.56% (symmetric, 3 agents, 2 sales) and up to 108.77% in asymmetric gridworld-like settings.
- In dynamic task scheduling, the zeroth-order method reduces makespan relative to VCG by up to 11.65% to 16.81% in the tested configurations (negative values indicate improvement).
- Gradient-based methods (zeroth-order and regularized LP) match or beat grid search while running in far less time (under 0.2 hours vs. up to 31 hours in sequential sales).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Optimize affine-maximizer weights and boosts instead of using VCG | Sequential sales, symmetric types (n=3, m=2) · Sequential sales, symmetric types (n=3, m=2) | revenue: 0.4999 -> 0.6777 | Helped |
| Optimize affine-maximizer weights and boosts instead of using VCG | Sequential sales, asymmetric types (n=3, m=2) · Sequential sales, asymmetric types (n=3, m=2) | revenue: 0.2348 -> 0.4123 | Helped |
| Optimize affine-maximizer parameters instead of using VCG | Task scheduling, symmetric types (n=2, m=4) · Task scheduling, symmetric types (n=2, m=4) | makespan: 1.0336 -> 0.9132 | Helped |
| Optimize affine-maximizer parameters instead of using VCG | Task scheduling, asymmetric types (n=2, m=4) · Task scheduling, asymmetric types (n=2, m=4) | makespan: 1.8312 -> 1.5978 | Helped |
| Optimize affine-maximizer parameters instead of using VCG | Gridworld (n=2, m=3) · Gridworld (n=2, m=3) | revenue: 0.7547 -> 1.5464 | Helped |
| Use zeroth-order optimization rather than random grid search | Sequential sales, symmetric types (n=3, m=2) · Sequential sales, symmetric types (n=3, m=2) | revenue: 0.6079 -> 0.6777 | Helped |
| Use regularized LP optimization rather than random grid search | Task scheduling, symmetric types (n=2, m=4) · Task scheduling, symmetric types (n=2, m=4) | makespan: 1.0326 -> 0.9288 | Helped |
| Use zeroth-order optimization rather than regularized LP optimization | Sequential sales, symmetric types (n=2, m=2) · Sequential sales, symmetric types (n=2, m=2) | revenue: 0.4893 -> 0.4939 | Helped |
| Use regularized LP optimization rather than zeroth-order optimization | Sequential sales, symmetric types (n=3, m=3) · Sequential sales, symmetric types (n=3, m=3) | revenue: 0.6446 -> 0.7240 | Helped |
| Use zeroth-order optimization rather than regularized LP optimization | Gridworld (n=2, m=3) · Gridworld (n=2, m=3) | revenue: 1.5464 -> 1.3486 | Hurt |
Surprising findings
- Grid search sometimes performs worse than VCG in larger settings (e.g., sequential sales with 5 agents and 3 items in the asymmetric setting), showing naive search scales poorly.
Limitations
- Experiments only on small tabular MDPs; deep RL scaling not explored.
- Gradient methods reach local optima only; global optimality not guaranteed.
- Regularization introduces approximation; zeroth-order and regularized LP each work better in different settings.
Experimental setup
Datasets: synthetic type profiles sampled from uniform distributions
Benchmarks: sequential sales auctions dynamic truthful task scheduling gridworld multi-task navigation
Metrics: expected revenue makespan
Baselines: VCG random grid search
Builds on: Affine maximizer mechanisms (static AMAs) Automated mechanism design Dynamic VCG mechanism Entropy-regularized LP for MDPs
Closest papers by meaning
- Safely Learning Optimal Auctions: A Testable Learning Framework for Mechanism Design (ICML 2025 · similarity 0.85)
- Mechanism design augmented with output advice (NeurIPS 2024 · similarity 0.85)
- On the Power of Randomization for Obviously Strategy-Proof Mechanisms (AAAI 2025 · similarity 0.85)
- Mechanism Design via the Interim Relaxation (NeurIPS 2025 · similarity 0.85)
- A Unified Framework for Uniform-Price Resource Allocation Mechanisms (NeurIPS 2026 · similarity 0.85)
- Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.