CS Paper Radar

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

Endre Csóka

cs.GT econ.TH ·submitted 2026-08-28 15:13 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.GT econ.THmath.COmath.PR ·2026-10-07 ·Endre Csóka, Máté Viczián
similarity 0.59
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.

0.33

Sybil-Proofness of Generalized Adaptive Clinching and Implications for Blockchain Mechanism Design

cs.GT econ.TH ·2026-10-27 ·Chengkai Zhang, Yuhao Li, Elaine Shi, Mengqian Zhang, Lirong Xia +1 more
position similarity 0.58
Abstract · Abstract shortened to comply with arXiv's character limit

The adaptive clinching auction of Dobzinski, Lavi, and Nisan (FOCS'08) is a cornerstone of mechanism design with budget-constrained bidders, and it has since inspired a broad range of extensions to substantially richer market settings. Adaptive clinching enjoys compelling guarantees: it is Pareto optimal, and truthful bidding is a dominant strategy whenever budgets cannot be overreported. In many real-world environments, however, identities are cheap to create, making resilience to Sybil attacks an additional requirement. Whether the guarantees of adaptive clinching survive when a bidder can split its budget across fake identities has remained open. We introduce a generalized framework for adaptive clinching and prove that it satisfies Sybil-robust incentive compatibility: a bidder cannot benefit from splitting into any finite number of identities with arbitrary value reports, provided their aggregate reported budget does not exceed the bidder's enforceable true budget. Sybil resilience thus joins the list of ideal properties of adaptive clinching. Our work is motivated by practical problems in decentralized finance, where automated market makers (AMMs) are among the most widely used applications. We design a new AMM mechanism that extends classical adaptive clinching in two ways: it supports a two-sided market and protects against two-sided strategies, and it allows the supply function to depend on the auction state. Its one-sided special case is captured by our generalized adaptive clinching framework, and our proof techniques show that the full two-sided mechanism simultaneously satisfies Sybil-robust incentive compatibility and a relaxed notion of Pareto optimality. We argue that these guarantees are essentially the best possible via impossibility results. More broadly, our work reveals new connections between classical algorithmic game theory and modern decentralized blockchains.

0.46

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

cs.GT ·2026-10-07 ·Mingyu Guo
similarity 0.56
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

Auction-based allocation of routes in capacity-constrained networks

cs.GT econ.THecon.GN ·2026-10-14 ·Gergely Csáji, Dávid Csercsik
similarity 0.56
Abstract

We study the route-set allocation problem between end nodes in capacity-constrained flow networks with transfer costs. We introduce an origin--destination (OD) bidding language, in which a participant bids for bounded conic combinations of inlet--outlet--quantity licences and the mechanism performs the routing through a network-flow optimising winner-determination problem. We then study payment rules for the OD mechanism. Under a restricted model with openly and uniformly priced sources and bidders who are indifferent to the source of the gas, the Vickrey--Clarke--Groves (VCG) payment is core-stable; the key structural fact is that in this regime some optimal aggregate flows never use a physical pipe in both directions, so the winner-determination problem reduces to a single-commodity network flow whose value is submodular in the set of active bidders. If source access is allowed to depend on the individual consumer -- a realistic feature, e.g. when gas deals are embedded in bilateral political bargaining -- the reduction fails and VCG payments may lie strictly outside the core. For this general model we propose a dual (nodal) pricing rule derived from the shadow prices of the flow-conservation constraints, and prove it is always core-stable, at the cost of dominant-strategy incentive compatibility. Illustrative examples accompany each result.

0.26

Decentralized LLM Workflows via Sequential Auctions

cs.GT cs.AIcs.MA ·2026-10-15 ·Ian Gemp, Shubhendu Trivedi, Adam Fisch, Fantine Huot, Michael Kaisers +5 more
similarity 0.55
Abstract · 28 pages

We present a scalable framework for solving multi-step tasks through a decentralized market of self-interested agents. Prior theoretical work demonstrated that agents organized through sequential auctions can converge to a globally optimal policy in a Markov decision process (MDP), but relied on the restrictive assumption of the existence of perfect clones as a model of perfect competition. In reality, exact clones drive agent profit to zero, violating the natural risk-reward incentives of participants. Conversely, we empirically demonstrate that the opposite extreme, absence of competition, also leads to market failure and value extraction collapse. Between these two extremes, we investigate how heterogeneous agents can survive in markets that span the critical middle ground of imperfect competition. To be profitable, agents learn to strategically shade bids to secure positive individual profit margins, while still ensuring that the marketplace functions effectively enough so that collaborative tasks posed by market consumers can still be solved. We formulate and evaluate four bidding algorithms (Mirror Descent, Thompson Sampling, Bayes-Optimal, and PPO) across three auction protocols (1st-Price, 2nd-Price, and Credit-Conserving Vickrey). Across a diverse set of domains, we demonstrate that imperfect competition successfully sustains necessary agent profit margins while maintaining high task success rates at low costs.

0.28

A 1.283 Price-of-Anarchy Bound for the Repeated Virtual First-Price Auction

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

We study the repeated allocation of a single indivisible resource among $n$ strategic players. Each player $i$ has a privately known value distribution $D_i$, and values are drawn independently across players and periods. The goal is to find fair and efficient mechanisms. We apply the repeated first-price auction with equal initial endowments of virtual money. We show that each player can asymptotically secure the same fair-floor guarantee $f(D_i)$ as in Csóka 2026; consequently, the mechanism is $1.283$-optimal. This provides a simpler and more robust alternative mechanism for this special case and may also help derive sharper upper bounds on the price of anarchy.

0.38

The Power and Limits of Money Burning in Bilateral Trade

cs.GT ·2026-11-03 ·Moshe Babaioff, Noam Nisan, Ariel Shaulker
similarity 0.55
Abstract

We study the power of money burning in bilateral trade. In this problem, a seller owns an indivisible item, a buyer would like to acquire it, and each of these two traders has a private value for the item and the values are sampled from independent distributions. We ask whether the traders can benefit from a mechanism that burns money, that is, one that charges the buyer more than it pays the seller, so that neither trader enjoys the difference (money burnt is a loss for the traders). Is it possible that the traders will ever be better off if the trade mechanism can burn money? For Bayesian incentive-compatible mechanisms and for deterministic dominant-strategy incentive-compatible (DSIC) mechanisms, it is known that money burning is always a waste and can only hurt the traders. Maybe surprisingly, we show that once a DSIC mechanism can use randomization, money burning can significantly benefit the traders, and the gain of each of them can be arbitrarily large. In contrast, we show that the power of DSIC randomized mechanisms that burn money is still very limited in the sense that they cannot guarantee any constant fraction of the first-best gains-from-trade.

0.23

Optimal Multi-Item Auctions with I.I.D. Values

cs.GT ·2026-10-08 ·Boyu Liu, Zhengyang Liu, Zihe Wang
similarity 0.54
Abstract · 51 pages, 1 table

We study revenue-maximizing multi-item auctions under dominant-strategy incentive compatibility (DSIC) and ex-post individual rationality. Buyers have additive valuations, and all item values are independent draws from a common finite distribution. For every two-point distribution and arbitrary numbers of buyers and items, we give an explicit deterministic mechanism that is optimal among all randomized mechanisms satisfying these requirements, together with a polynomial-time algorithm for computing the optimal expected revenue. For general finite-support distributions, computing the exact optimal revenue is $\#\mathrm P$-hard, both for a single buyer with an arbitrary number of items and for two items with an arbitrary number of buyers. For a single buyer, we also establish hardness of computing an optimal mechanism. Building on prior work, we also obtain exact and approximate algorithms under different parameter restrictions. Exact polynomial-time optimization is possible whenever any two of the buyer count, item count, and support size are fixed. When only the item count is fixed, a polynomial-time approximation scheme constructs a mechanism with expected revenue at least a $1-\varepsilon$ fraction of the optimum for every fixed $0<\varepsilon<1$. All these algorithms satisfy DSIC and ex-post individual rationality.

0.21