CS Paper Radar

Falsification-proof non-market allocation mechanisms

Eduardo Perez-Richet, Vasiliki Skreta

cs.AI econ.THcs.GT ·submitted 2026-10-13 16:03 UTC · v2
highly cited

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Truthful Two-Facility Location with Candidate Locations in Metric Spaces

cs.GT ·2026-10-13 ·Panagiotis Kanellopoulos, Alexandros A. Voudouris
theory similarity 0.60
Abstract

We study a truthful facility location problem in which agents have private positions in a metric space and known approval preferences over two distinct facilities. Each agent incurs a cost equal to her total distance from the facilities she approves. The goal is to locate the facilities at a given set of candidate locations so as to approximately minimize either the social cost or the max cost, while incentivizing the agents to report their positions truthfully. This problem was previously studied for line metrics and deterministic mechanisms. We first settle the approximation ratio of deterministic mechanisms for the social cost on the line by establishing a lower bound of $7$, matching the upper bound from previous work, and show that randomization leads to a strict improvement. For the max cost, we show that the previously known optimal deterministic guarantee of $3$ remains tight even for universally strategyproof mechanisms. We then turn to general metric spaces. For deterministic strategyproof mechanisms, we obtain tight approximation ratios of $2n-1$ for the social cost and $5$ for the max cost. We also show that randomization yields substantial improvements for both objectives: for the social cost, we obtain a tight characterization, while for the max cost we establish nearly matching upper and lower

0.04

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.60
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

EFX Allocations for Three Agents and Seven or Eight Chores

cs.GT ·2026-09-06 ·Xinkai Zhang
theory similarity 0.59
Abstract · 14 pages, including appendices

We show that every additive chore instance with three agents and seven or eight indivisible chores has an EFX allocation. Costs may be arbitrary nonnegative reals. Together with the theorem of Kobayashi, Mahara, and Sakamoto for at most $2n$ chores, this settles the existence of EFX allocations for three agents and at most eight chores; for four or more agents, He and Tao have shown that EFX allocations of additive chores need not exist. Both proofs are computer-assisted. For seven chores, we normalize each agent's costs and sort the chores, and then express the nonexistence of an EFX allocation as a formula of quantifier-free linear real arithmetic with one clause per allocation; the SMT solvers Z3 and cvc5 show that this formula is unsatisfiable. For eight chores, if two agents share a cheapest chore, we remove that chore, apply the seven-chore result, and put the chore back using an insertion lemma of Kobayashi, Mahara, and Sakamoto. The remaining instances, in which the agents' sets of cheapest chores are pairwise disjoint, are handled by a second formula of the same kind.

0.46

Improving the Bounds on Approximating Weighted Maximin Share for Chores

cs.GT cs.AI ·2026-10-11 ·Trung Thanh Nguyen, Khaled Elbassioni, Jörg Rothe
similarity 0.59
Abstract

We investigate the problem of allocating indivisible chores among agents with arbitrary positive weights and additive nonnegative cost functions. An allocation is said to be $α$-weighted-maximin-share (WMMS) fair if the cost incurred by each agent is at most $α$ times her weighted maximin share. We establish that every instance admits a $4.124234528$-WMMS allocation. Moreover, for instances in which all weights and costs are rational numbers represented in binary, we give an algorithm that computes a $4.12424$-WMMS allocation in time polynomial in the number of agents, the number of chores, and the total binary encoding length of the input. Complementing these upper bounds, we construct a family of instances with strictly positive, identically ordered costs for which the optimal WMMS approximation factors converge to $e$. Together, our results substantially narrow the previously best-known gap of $[2,12]$ established by Li et al.~\cite{LWX26} to $[e,4.12424]$.

0.15

Pairwise Maximin Share Allocations Need Not Exist

cs.GT ·2026-09-05 ·Haris Aziz
similarity 0.59
Abstract

We study the fair allocation of indivisible goods among agents with strictly positive additive valuations. Pairwise maximin share fairness (PMMS) asks that, for every ordered pair of agents, the first agent value her own bundle at least as highly as the best worst-case share she could secure by repartitioning the two agents' combined bundles into two parts. Whether a PMMS allocation always exists for positive additive valuations has remained open since the notion was introduced. We resolve this question in the negative. We construct an instance with four agents and strictly positive additive valuations that admits no complete PMMS allocation.

0.43

Exact Hill Shares Are Simultaneous Guarantees

cs.GT ·2026-09-18 ·Bo Li, Hanyu Li, Chenghua Liu
benchmarktheory similarity 0.59
Abstract

Fair division of indivisible bads seeks allocations that guarantee every agent a bundle whose cost is no larger than a meaningful fairness benchmark. The canonical minimax share has widely been used; unfortunately, it is not a simultaneous guarantee. Hill (Ann. Probab., 1987) initiated a complementary approach in which the share depends only on the number of agents and the largest possible single-item value. Li et al. (ACM Trans. Econ. Comput., 2024) gave the exact Hill formula and proved that its monotone closure is a simultaneous guarantee. The closure treats the largest-item cost only as an upper bound and can be strictly larger than the share conditioned on the \emph{actual} largest item. They asked whether this smaller exact share is itself simultaneously guaranteed for three or more agents. We resolve this open question affirmatively. For any number of agents and arbitrary heterogeneous largest-item costs, there is one allocation that satisfies every agent's exact Hill's share. We further provide a polynomial-time algorithm computes such an allocation. Our algorithm combines an ordered moving knife with a tail-domination invariant, and a one-sided trimmed subset-sum routine for the two-agent endpoint without computing an exact minimax partition.

0.16

Revisiting EFX and fPO Allocations for Binary Chores

cs.GT ·2026-09-12 ·Zehan Lin, Xiaowei Wu, Shengwei Zhou
similarity 0.59
Abstract · 28 pages, no figure

We study fair and efficient allocations of indivisible chores under binary additive costs, with a focus on unequal entitlements and best-of-both-worlds guarantees. While binary valuations have been extensively studied for goods, their chore counterpart remains much less understood. A notable exception is due to Tao et al. (TCS 2025), who established that EFX and fPO are compatible for binary chores with equal entitlements. We revisit binary chores under unequal entitlements and establish the computation of allocations that satisfy WEFX and fPO. Our key technical contribution is a new lexicographic potential function tailored to chores: any allocation minimizing this potential ensures both WEFX and fPO. This potential further guides a polynomial-time local-search algorithm for computing allocations with such fairness and efficiency guarantees. For best-of-both-worlds guarantees, we show that unequal entitlements create a sharp obstruction: even with two agents and identical binary additive costs, no lottery can simultaneously satisfy ex-ante WEF and ex-post WEF1. In contrast, for equal entitlements, we construct in polynomial time a lottery that is ex-ante EF and fPO, while every realization is both EFX and fPO.

0.41

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