arXiv preprint ·
Tight Efficiency Guarantees for Strategyproof Linear Regression
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study the trade-off between squared-error accuracy and incentive compatibility in linear regression. Agents report private labels associated with publicly known features and prefer predictions close to their true labels. Ordinary least squares (OLS) need not elicit truthful reports. For regression with $d$ parameters, we design a deterministic group-strategyproof mechanism achieving a $(d+1)$-approximation to the least-squares optimum and prove optimality even among universally strategyproof randomized mechanisms, answering an open question of Chen et al. (EC 2018). Relaxing universal strategyproofness to strategyproofness in expectation reveals a sharp separation: squared individual loss retains the factor $d+1$, while absolute individual loss admits the tight ratio $2-1/(\lceil d/2\rceil+1)$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Evolution of Market Microstructure in the Age of AI
The Double-Edged Sword of Information: Revealed versus Hidden Lotteries in School Choice
Modular Discovery of General Game-Playing Algorithms with Large Language Models
Minimax Last-Iterate Convergence in Matrix Games with Observed Actions
When Privacy Moves ML-Mediated Decisions On Device: Information and Incentive Misalignment in Auctions
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.