Truthful Rounding for Discrete Allocations

This direction is merged into another direction: indivisible resource allocation. Its last version stays readable and citable here.

Version 1 of 14 papers19 conceptsfrozen 2026-10-04

In mechanism design, there is a recurring tension between computational efficiency and game-theoretic stability. To solve complex allocation problems—like auctioning sets of items or dividing a city budget—researchers often relax the problem. They treat discrete items as if they can be split into infinitely small fractions, solve the resulting continuous optimization problem, and then "round" the result back to a whole number.

While this works for pure optimization, it often fails in the presence of strategic actors. As Aaron Archer, Christos Papadimitriou, Kunal Talwar, and Éva Tardos demonstrate in An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents, standard rounding techniques typically destroy truthfulness. When a mechanism is truthful, the best strategy for every participant is to report their true preferences. Rounding breaks this because it decouples the optimization from the final allocation, creating "cliffs" where a bidder might receive more by reporting less.

The Monotonicity Problem

The core reason rounding fails is a lack of monotonicity. In a truthful mechanism, if you increase your bid for an item, your probability of receiving that item should never decrease.

However, standard Linear Programming (LP) relaxations don't guarantee this after rounding. Imagine a bidder increasing their bid. This change might shift the fractional solution of the LP to a different "corner" of the feasible region. Even if the bidder's fractional share increases slightly, the specific rounding algorithm used might now be less likely to select them for a whole item. As noted by Archer et al., this sensitivity allows bidders to strategically manipulate their reports to "nudge" the rounding process in their favor.

Integrating Rounding into the Mechanism

To fix this, the rounding process cannot be an afterthought; it must be baked into the mechanism's logic.

In From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions for Submodular Bidders, Tim Roughgarden, Qiqi Yan, and Shaddin Dughmi introduce a framework called Convex Rounding. Instead of solving a standard LP and then rounding, they optimize over a space of "roundable" distributions.

By ensuring the optimization step is "maximal" over a fixed distribution range, they ensure that no bidder can influence the rounding logic to their advantage by lying. This approach allowed them to match the best possible approximation ratios for submodular bidders while maintaining "truthfulness-in-expectation"—meaning that, on average, honesty remains the best policy.

The Challenge of Discrete Budgets

The problem of rounding is not limited to auctions; it also appears in collective decision-making. In Discrete Budget Aggregation: Truthfulness and Proportionality, Ulrike Schmidt-Kraepelin, Markus Utke, and Warut Suksompong examine scenarios where resources (like hiring slots or workshop hours) cannot be split.

They identify a "sobering" mathematical barrier: if voters are allowed to submit fractional preferences for a discrete outcome, any truthful mechanism for three or more alternatives is forced to be a dictatorship (where only one person's vote matters).

To circumvent this, they propose that both the inputs and the mechanism's internal logic must be discrete. Their "integral moving-phantom" mechanism avoids post-hoc rounding by building "step functions" directly into the allocation process. This ensures that voters cannot gain an advantage by misreporting their preferences to influence a rounding threshold.

Why It Works

The shared insight across these papers is that discretization must be intrinsic.

  1. Decoupling is the Enemy: When the optimization (the "brain") and the rounding (the "hand") act independently, the "brain" doesn't account for how its fractional choices will be interpreted by the "hand."
  2. Monotonicity by Design: By integrating the rounding logic into the objective function or the input constraints, researchers ensure that the final discrete outcome responds predictably to changes in bids or votes.
  3. Restricting the Domain: Sometimes, as Schmidt-Kraepelin et al. show, the only way to maintain fairness and truthfulness is to prevent the "illusion of continuity" entirely, forcing both the participants and the mechanism to operate in a discrete world from the start.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_truthful_rounding_for_discrete_allocatio_960e226b,
  title = {Truthful Rounding for Discrete Allocations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/truthful-rounding-for-discrete-allocations/rdr_960e226b721a458aa9f5cea4297c0224},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_truthful_rounding_for_discrete_allocatio_960e226b_v1,
  title = {Truthful Rounding for Discrete Allocations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/truthful-rounding-for-discrete-allocations/rdr_960e226b721a458aa9f5cea4297c0224/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}