CS Paper Radar

Risk-minimizing GUE-implementations of truthful reporting in a Dynamic Social Choice Problem

Endre Csóka, Máté Viczián

cs.GT econ.THmath.COmath.PR ·submitted 2026-10-07 17:25 UTC · v1

Abstract

The Guaranteed Utility Mechanism (GUM) was introduced to implement efficiency in Guaranteed Utility Equilibrium (GUE) in dynamic social choice problems. We show that this mechanism also has a previously unknown connection to risk minimization. Fixing an efficient decision policy, we study variance-minimizing budget-balanced transfer rules in the class of GUE-implementations of truthful reporting. A symmetrized version of GUM (sym-GUM) minimizes the sum of the agents' utility variances under truthful reporting when there is no public state. When a public state is present, a slight modification of this rule yields the minimizer for the same objective. Sym-GUM, however, does not minimize transfer risk. The minimizer for that problem is instead the symmetrized version of a closely related GUM-like transfer rule. In both problems, the minimizing truthful total transfers are unique up to agent-specific constants summing to zero and events of probability zero.

Closest papers

Nearest neighbours by meaning across the whole index.

From the Social Choice Problem to a Collusion-Proof Tendering Mechanism for Dynamic Stochastic Projects

cs.GT econ.TH ·2026-08-28 ·Endre Csóka
similarity 0.59
Abstract

The VCG family and the AGV mechanism are two classical approaches to efficient implementation in the static social choice problem. In 2024, Csóka et al. showed that AGV has critical weaknesses. In contrast, the transferable-utility Guaranteed Utility Mechanism (TU-GUM) retains all the standard desirable properties of AGV while adding further ones, including collusion-proofness, because it implements efficiency in Guaranteed Utility Equilibrium. TU-GUM also applies to a more general dynamic setting with multiple extensions. Moreover, TU-GUM is a special case of an even more general and robust mechanism that combines contingent first-price tendering with the coordinated execution of dynamic stochastic multi-agent projects through a surprisingly simple rule. This paper summarizes and connects existing results from a different perspective, with some minor new observations.

0.34

Anchoring for Truthfulness: The Random-Anchor Volume Mechanism for Multi-Facility Location

cs.GT ·2026-08-17 ·Haris Aziz, Simon Mackenzie, Mashbat Suzuki
theory similarity 0.58
Abstract

We study the strategyproof placement of \(k\) facilities on the real line for \(n\) agents who privately report their locations, without monetary transfers. For two facilities, the Proportional Mechanism of Lu, Sun, Wang, and Zhu (2010) is strategyproof in expectation and achieves a constant-factor approximation to the optimal social cost. Whether such a guarantee is possible for three facilities in the standard model, where each agent is served by her nearest open facility, has remained open. We resolve this question affirmatively by introducing the \emph{Random-Anchor Volume} mechanism. The mechanism first opens a facility at the report of a uniformly random agent, called the \emph{anchor}, and then jointly selects two additional reports, assigning each pair probability proportional to the product of the two consecutive gaps formed by the pair and the anchor. We prove that the mechanism is strategyproof in expectation and has expected social cost at most \(8 OPT_3\), where \(OPT_k\) denotes the minimum social cost achievable using at most \(k\) facilities. The mechanism naturally extends to every \(k\geq 2\) by selecting \(k-1\) additional reports with probability proportional to the product of the consecutive gaps among them and the anchor. Under truthful reporting, this generalization has expected social cost at most \(4(k-1)OPT_k\). Its incentive guarantee, however, has a sharp boundary: the mechanism is strategyproof in expectation for \(k\in\{1,2,3\}\), but is manipulable for every \(k\geq 4\).

0.44

Auction Design with ROI-Constrained Bidders: Truthfulness and Revenue Maximization

cs.GT econ.TH ·2026-09-15 ·Zhiqiang Zhuang, Quan Yu, Yisong Wang, Kewen Wang, Zhe Wang
theory similarity 0.58
Abstract

The return-on-investment (ROI) constraint is central to many auctions, particularly in online advertising, where a bidder is unwilling to pay more than a fixed fraction of the value obtained. We study truthful and revenue-maximizing auctions for ROI-constrained bidders. We first characterize truthful auctions when both valuations and ROI constraints are private, showing that the allocation rule uniquely determines the payment rule. Building on this characterization, for multiple bidders we introduce $σ$-increment mechanisms that resemble Myerson's optimal mechanism~\cite{journals/mor/Myerson81}; as $σ$ vanishes, these mechanisms become asymptotically optimal among deterministic truthful mechanisms, and their revenue approaches at least a $1/\bar r$ fraction of the optimal expected revenue over all truthful mechanisms, where $\bar r$ is the largest possible ROI constraint. In the single-bidder setting, we prove that every truthful auction can be replaced by a convex pricing function with weakly higher payments for every type, and we derive the optimal pricing functions when either the valuation or the ROI constraint is public.

0.21

Sender-Receiver Games with Payment Commitments

cs.GT ·2026-10-04 ·Ivan Geffner
similarity 0.58
Abstract

We study sender-receiver games in which players commit, before the state is drawn, to payments contingent on the subsequently verified state and the receiver's action. Payments may be transferred or burned, serving as contractual guarantees or promised tips. We analyze equilibrium guarantees, welfare, and computational complexity. For arbitrary finite action sets, we characterize pessimistic utility guarantees under unilateral commitments. Sender-only and sender-first commitments have worst-equilibrium welfare equal to the best constant-action welfare. Simultaneous commitments can instead reduce welfare below every equilibrium of the original game. Neither simultaneous nor sender-first commitments always admit an efficient equilibrium. Receiver-first commitments always admit an efficiently computable welfare-maximizing equilibrium, but can also reduce worst-equilibrium welfare. For binary actions, we characterize their entire equilibrium payoff region. With binary actions, optimal receiver commitments are computable in linear time, whereas optimizing deterministic sender commitments is NP-hard. Privately randomized sender commitments admit an exact $O(n\log n)$ algorithm, with an optimal lottery over at most two schemes differing at only one state. This yields an additive approximation by deterministic commitments. For arbitrary finite action sets, optimal privately randomized sender payoffs equal Bayesian persuasion values: ordinary persuasion with burning alone, and persuasion with nonnegative compliance payments when transfers are allowed. These equivalences yield polynomial-time algorithms with polynomial-size commitment lotteries.

0.16

Asymptotically Optimal Public Project Redistribution without Bounded Precision: A Complex-Analytic Proof

cs.GT ·2026-10-07 ·Mingyu Guo
similarity 0.57
Abstract

We study worst-case VCG redistribution mechanism design for the public project problem, where n agents decide whether to build a non-excludable public project and the designer chooses a Groves term that returns as much of the VCG payment as possible without running a deficit. The objective is the worst-case efficiency ratio, the worst-case ratio between the agents' total utility and the first-best total utility. Prior work showed that this ratio can approach 1 as n grows only under a bounded precision assumption, that all types are rational numbers with a common bounded denominator. The assumption is stronger than it looks: it confines the difficult profiles to those in which all but a bounded number of agents report zero, and an agent who reports zero knows the total exactly. Without it, the best known guarantee tends to 1/2. We remove the assumption. We construct a deterministic, anonymous, strategy-proof, and non-deficit mechanism for arbitrary real types in [0,1] whose worst-case efficiency ratio is 1-O(1/log log n). The construction estimates the shortfall of the reported total below the project cost by filling in each agent's missing report with a resampled one, then estimates the error of that estimate, then the error of the error, and so on. After m rounds the aggregate error is at most 1/Hm mean reports, where Hm is the mth harmonic number. The proof of this bound is the heart of the paper and, unusually for a result about payments, uses complex analysis: a trigonometric representation of the shortfall function together with the Poisson-Jensen inequality for bounded analytic functions in the upper half plane.

0.29

Scaling Chance-Constrained Correlated Equilibrium Computation for Exclusive Resource-Assignment Games

cs.GT ·2026-09-11 ·Jaehan Im, Ufuk Topcu, David Fridovich-Keil
similarity 0.57
Abstract

The chance-constrained correlated equilibrium concept provides a robust coordination technique for self-interested agents whose costs are uncertain to a central coordinator, but the number of joint actions considered in its computation grows exponentially with the number of agents. We propose an exact-one resource-assignment restriction for games in which agents compete for shared resources and simultaneous use of a resource is undesirable or unsafe. The restriction allows each resource to be assigned to exactly one agent, reducing the number of joint actions considered from O(2^(nr)) to O(n^r) for n agents and r resources. The resulting problem is solved over the restricted joint action set while retaining all incentive constraints associated with unilateral deviations. We show that the feasible set of the restricted problem is exactly the convex hull of the chance-constrained pure Nash equilibria contained in the exact-one assignment set, yielding a necessary and sufficient condition for nonemptiness. We further derive a sufficient condition under which all chance-constrained pure Nash equilibria of the unrestricted game are retained by the restriction. Numerical experiments in a vertiport departure-corridor coordination scenario demonstrate a 99.81% reduction in median computation time relative to the unrestricted formulation while achieving equivalent coordination performance.

0.31

Rewarding Informed Voting in PoS Governance

cs.GT econ.TH ·2026-10-06 ·Juan Beccuti, Manvir Schneider
similarity 0.57
Abstract

We study reward design for delegated representatives who acquire costly information and vote on a binary governance proposal. Effort improves both private information and delegated voting weight. We show that no payment rule can make sincere voting strictly optimal at every positive effort profile under a non-neutral prior, while fixed budgets limit accuracy in large symmetric committees. We then compare proportional sharing with a conditional rule that rewards only members of a sufficiently large winning coalition. Unlike proportional sharing, which supports sincere voting only through indifference, the conditional rule makes sincere voting strictly optimal at symmetric positive effort profiles. It supports sincere equilibria with the same effort as proportional sharing and, under suitable reward-cost conditions, with strictly higher effort and decision accuracy. Insincere equilibria may nevertheless coexist.

0.21

Falsification-proof non-market allocation mechanisms

cs.AI econ.THcs.GT ·2026-10-13 ·Eduardo Perez-Richet, Vasiliki Skreta
highly cited similarity 0.57
Abstract

Relying on manipulable characteristics to target the allocation of resources is fraught with difficulties. Naively optimal rules lead to falsification and allocative inefficiency. Optimizing the rule for allocative efficiency while accounting for falsification typically induces falsification, at a heavy cost to the agents. Moreover, falsification generates negative externalities. We characterize optimal falsification-proof rules under a broad range of falsification technologies. We also provide an honesty condition under which they solve the unconstrained problem of a planner who maximizes a weighted sum of allocative surplus and agents' welfare.

0.48