Research map / Learning theory and algorithms / Submodular and game algorithms
Multidimensional Bayesian Utility Maximization: Tight Approximations to Welfare
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.
Studies multidimensional Bayesian utility maximization for i.i.d. unit-demand buyers and gives simple "favorites" mechanisms achieving a (1-1/e) approximation to optimal welfare when m≥n and an O(log(n/m)) approximation when n>m, with a matching lower bound.
Problem
Approximating optimal Bayesian utility (welfare minus payments) in the multidimensional i.i.d. unit-demand setting with n buyers and m items, where payments are non-monetary ordeals that reduce utility.
Approach
Each buyer reports their favorite item (highest value), and each item is then allocated among its declared competitors via a fixed single-item mechanism (uniform random for m≥n, prior-free power-of-two lottery for n>m); under i.i.d. values this is BIC and reduces to single-item problems, giving tight bounds matched by a reduction to the identical-items setting.
Key results
- Random-Favorites achieves utility at least (1-1/e) of optimal welfare when m≥n.
- Prior-Free-Favorites achieves O(log(n/m)) approximation to optimal welfare when n>m (constant 17.8(1+log(n/m))).
- Tightness: the gap opt_welfare/opt_utility is Theta(1+log(n/m)) in the i.i.d. unit-demand setting, via reduction to identical items.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Random-Favorites when m ≥ n | i.i.d. unit-demand setting · m ≥ n | utility / optimal welfare: (1 -\frac{1}{e}) | Helped |
| Use Prior-Free-Favorites when n > m | i.i.d. unit-demand setting · n > m | utility approximation factor to optimal welfare: O(\log \frac{n}{m}) | Helped |
| Use Random-Favorites instead of the best known prior bound | i.i.d. unit-demand setting · m ≥ n | utility approximation factor to optimal welfare: O(m\log n) -> (1 -\frac{1}{e}) | Helped |
| Use Prior-Free-Favorites instead of the best known prior bound | i.i.d. unit-demand setting · n > m | utility approximation factor to optimal welfare: O(m\log n) -> O(\log \frac{n}{m}) | Helped |
| Apply the Prior-Free-Favorites mechanism in the uniform-favorites setting rather than the i.i.d. setting | Prior-Free-Favorites · uniform favorites | Bayesian incentive compatibility | Hurt |
| Split each multidimensional bidder into single-minded copies for items | utility maximization · 2 items, 2 bidders | utility | Hurt |
| Allow the mechanism to leave an item unallocated rather than restrict it to exhaustive allocations | multidimensional utility maximization · two unit-demand bidders and two items | utility: \frac{1}{2} | Helped |
Surprising findings
- The copies technique from revenue maximization fails to give an upper bound on utility, since utility can exceed the copies-setting optimum.
- The utility-optimal mechanism may need to discard (not allocate) an item to avoid payments, unlike single-dimensional settings.
Limitations
- Results require i.i.d. values across both items and buyers; Prior-Free-Favorites is not BIC under only uniform favorites.
- Upper bound analysis of Prior-Free-Favorites uses constants (e.g., 17.8) and a technical lemma.
- Does not provide a tractable upper bound on optimal utility tighter than welfare for general unit-demand settings.
Experimental setup
Metrics: approximation ratio of utility to optimal welfare
Baselines: VCG uniformly random free allocation Hartline-Roughgarden prior-free mechanism
Builds on: Hartline and Roughgarden 2008 prior-free utility maximization Myerson optimal auction VCG
Closest papers by meaning
- Knowing Who, Not How Much: Learning-Augmented Mechanisms for Consumer Utility Maximization (ICML 2026 · similarity 0.88)
- From Welfare to Utility: Generalized Objectives in Budget-Feasible Procurement (ICML 2026 · similarity 0.88)
- Fair and Welfare-Efficient Constrained Multi-Matchings under Uncertainty (NeurIPS 2024 · similarity 0.87)
- Beyond Scalar Rewards: An Axiomatic Framework for Lexicographic MDPs (NeurIPS 2025 · similarity 0.86)
- The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective (AAAI 2025 · similarity 0.86)
- Maximizing Nash Social Welfare under Two-Sided Preferences (AAAI 2024 · similarity 0.86)
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.