Optimization-friendly generic mechanisms without money

• URL: http://arxiv.org/abs/2106.07752v1
• Date: Mon, 14 Jun 2021 20:42:23 GMT
• Title: Optimization-friendly generic mechanisms without money
• Abstract summary: We develop a generic framework for converting modern optimization algorithms into mechanisms where inputs come from self-interested agents. Special cases of this setting include voting, allocation of items by lottery, and matching. Key technical contribution is a new meta-algorithm we call apex.
• Score: 8.98272353392094
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The goal of this paper is to develop a generic framework for converting modern optimization algorithms into mechanisms where inputs come from self-interested agents. We focus on aggregating preferences from $n$ players in a context without money. Special cases of this setting include voting, allocation of items by lottery, and matching. Our key technical contribution is a new meta-algorithm we call \apex (Adaptive Pricing Equalizing Externalities). The framework is sufficiently general to be combined with any optimization algorithm that is based on local search. We outline an agenda for studying the algorithm's properties and its applications. As a special case of applying the framework to the problem of one-sided assignment with lotteries, we obtain a strengthening of the 1979 result by Hylland and Zeckhauser on allocation via a competitive equilibrium from equal incomes (CEEI). The [HZ79] result posits that there is a (fractional) allocation and a set of item prices such that the allocation is a competitive equilibrium given prices. We further show that there is always a reweighing of the players' utility values such that running unit-demand VCG with reweighed utilities leads to a HZ-equilibrium prices. Interestingly, not all HZ competitive equilibria come from VCG prices. As part of our proof, we re-prove the [HZ79] result using only Brouwer's fixed point theorem (and not the more general Kakutani's theorem). This may be of independent interest.

Related papers

• Quantum Interference as a Proposal Mechanism for Combinatorial Optimization [0.0]
  Quantum Proposal Interference Search (QIPS) uses seed-conditioned quantum circuits to generate localized interference patterns.<n>QIPS is used to update an elite frontier of low-energy solutions.<n>Performance is assessed using top-$K$ coverage, hit rate, multiplicity, Hilbert-space coverage and dyadic-rank metrics.
  arXiv  Detail & Related papers  (2026-07-29T22:54:13Z)
• Instance-Optimal Estimation with Multiple LLM Judges on a Budget [84.31744861038106]
  We formalize this question as *budgeted heteroskedastic multi-judge estimation*.<n>Given $K$ prompt-response pairs, $J$ judges with known costs, and unknown query-judge variances, the goal is to estimate a bounded score vector while minimizing an $ell_p$-error.<n>We prove that EST-IVWE matches the oracle IVWE rate up to lower-order terms in the budget.
  arXiv  Detail & Related papers  (2026-05-22T08:26:08Z)
• Breaking $\ extit{Winner-Takes-All}$: Cooperative Policy Optimization Improves Diverse LLM Reasoning [53.42577591449649]
  Group Cooperative Policy Optimization shifts the training paradigm from rollout competition to team cooperation.<n>GCPO replaces independent rollout scoring with team-level credit assignment.<n>It redistributes the collective team reward to each single rollout according to its average marginal contribution to the team.
  arXiv  Detail & Related papers  (2026-05-12T03:20:24Z)
• Generalized Distributional Alignment Games for Unbiased Answer-Level Fine-Tuning [49.24876001249647]
  Distributional Alignment Game framework provides powerful variational perspective on Answer-Level Fine-Tuning (ALFT)<n>Standard algorithms for these games rely on estimating logarithmic rewards from small batches, introducing a systematic bias due to Jensen's inequality that can destabilize training.<n>We generalize the alignment game to arbitrary Bregman divergences, showing that for a family of geometries inducing rewards, we can construct provably exact and unbiased estimators.
  arXiv  Detail & Related papers  (2026-05-04T10:34:42Z)
• A Game Theoretic Approach for Optimizing Quantum Error Budget Distribution [0.14323566945483496]
  Current fault-tolerant quantum compilers allocate error budgets uniformly during resource estimation, causing suboptimal physical resource overhead.<n>We optimize this allocation using a potential game formulation, where Nash Equilibrium yields a Pareto-optimal distribution across logical operations, T-state distillation, and rotation synthesis.<n> Evaluation across 433 MQT benchmarks demonstrates an average reduction of 30.22% in physical resource requirements relative to uniform baselines, with peak improvements of 97.81% for specific circuit instances.
  arXiv  Detail & Related papers  (2026-04-17T00:59:06Z)
• Additive Distributionally Robust Ranking and Selection [0.8283940114367679]
  We propose a simple additive allocation (AA) procedure that aims to exclusively sample the $k + m - 1$ previously hypothesized critical scenarios.<n>We prove that AA is consistent and, surprisingly, achieves additivity in the strongest sense.<n>Results offer new and counterintuitive insights into the additive structure of DRR&S.
  arXiv  Detail & Related papers  (2025-09-07T17:36:29Z)
• A New Benchmark for Online Learning with Budget-Balancing Constraints [14.818946657685267]
  We present a new benchmark to compare against, motivated both by real-world applications such as autobidding and by its underlying mathematical structure. We show that sublinear regret is attainable against any strategy whose spending pattern is within $o(T2)$ of any sub-linear spending pattern.
  arXiv  Detail & Related papers  (2025-03-19T00:14:20Z)
• Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
  We consider a problem where an auctioneer sells an indivisible good to groups of buyers in every round, for a total of $T$ rounds. The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group.
  arXiv  Detail & Related papers  (2024-05-31T19:26:05Z)
• Benefits of Permutation-Equivariance in Auction Mechanisms [90.42990121652956]
  An auction mechanism that maximizes the auctioneer's revenue while minimizes bidders' ex-post regret is an important yet intricate problem in economics. Remarkable progress has been achieved through learning the optimal auction mechanism by neural networks.
  arXiv  Detail & Related papers  (2022-10-11T16:13:25Z)
• On Scheduling Mechanisms Beyond the Worst Case [17.281501828240877]
  We find that mechanism K achieves a smaller social cost than mechanism P on every input. We also find that the average-case approximation ratio of mechanism P converges to the same constant.
  arXiv  Detail & Related papers  (2022-04-14T20:57:50Z)
• Fair Algorithm Design: Fair and Efficacious Machine Scheduling [0.0]
  There is often a dichotomy between fairness and efficacy: fair algorithms may proffer low social welfare solutions whereas welfare optimizing algorithms may be very unfair. In this paper, we prove that this dichotomy can be overcome if we allow for a negligible amount of bias.
  arXiv  Detail & Related papers  (2022-04-13T14:56:22Z)
• Inducing Equilibria via Incentives: Simultaneous Design-and-Play Finds Global Optima [114.31577038081026]
  We propose an efficient method that tackles the designer's and agents' problems simultaneously in a single loop. Although the designer does not solve the equilibrium problem repeatedly, it can anticipate the overall influence of the incentives on the agents. We prove that the algorithm converges to the global optima at a sublinear rate for a broad class of games.
  arXiv  Detail & Related papers  (2021-10-04T06:53:59Z)
• Online Learning of Competitive Equilibria in Exchange Economies [94.24357018178867]
  In economics, the sharing of scarce resources among multiple rational agents is a classical problem. We propose an online learning mechanism to learn agent preferences. We demonstrate the effectiveness of this mechanism through numerical simulations.
  arXiv  Detail & Related papers  (2021-06-11T21:32:17Z)
• Automated Mechanism Design for Classification with Partial Verification [64.69418921224529]
  We study the problem of automated mechanism design with partial verification. We focus on truthful mechanisms in the setting where all types share the same preference over outcomes.
  arXiv  Detail & Related papers  (2021-04-12T03:29:31Z)
• Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
  We introduce the emphregularized online allocation problem, a variant that includes a non-linear regularizer acting on the total resource consumption. In this problem, requests repeatedly arrive over time and, for each request, a decision maker needs to take an action that generates a reward and consumes resources. The objective is to simultaneously maximize additively separable rewards and the value of a non-separable regularizer subject to the resource constraints.
  arXiv  Detail & Related papers  (2020-07-01T14:24:58Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.