# Pay for The Second-Best Service: A Game-Theoretic Approach Against Dishonest LLM Providers

arXiv: https://arxiv.org/abs/2511.00847 · HTML: https://mlsanity.com/paper/2511.00847/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 39 references that are in the map.
- First posted on arXiv 2 Nov 2025.

## Builds on (most cited first, 12 of 12)

- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [How is ChatGPT's behavior changing over time?](https://mlsanity.com/paper/2307.09009/) (2023)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [OverThink: Slowdown Attacks on Reasoning LLMs](https://mlsanity.com/paper/2502.02542/) (2025)
- [Model Equality Testing: Which Model Is This API Serving?](https://mlsanity.com/paper/2410.20247/) (2024)
- [Are You Getting What You Pay For? Auditing Model Substitution in LLM APIs](https://mlsanity.com/paper/2504.04715/) (2025)
- [Mechanism Design for LLM Fine-tuning with Multiple Reward Models](https://mlsanity.com/paper/2405.16276/) (2024)
- [Fine-Tuning Games: Bargaining and Adaptation for General-Purpose Models](https://mlsanity.com/paper/2308.04399/) (2023)
- [Multi-armed Bandit Problems with Strategic Arms](https://mlsanity.com/paper/1706.09060/) (2017)
- [Is Your LLM Overcharging You? Tokenization, Transparency, and Incentives](https://mlsanity.com/paper/2505.21627/) (2025)
- [Incentivizing Quality Text Generation via Statistical Contracts](https://mlsanity.com/paper/2406.11118/) (2024)
- [Algorithmic Contract Theory: A Survey](https://mlsanity.com/paper/2412.16384/) (2024)

## Built on by (most cited first, 6 of 6)

- [Test-Time Compute Games](https://mlsanity.com/paper/2601.21839/) (2026)
- [Your "Pro" LLM Subscription May Actually Be "Free": Exposing Fingerprint Spoofing Risks in LLM Inference Services](https://mlsanity.com/paper/2606.16100/) (2026)
- [Deep Incentive Design with Differentiable Equilibrium Blocks](https://mlsanity.com/paper/2603.07705/) (2026)
- [Computational Arbitrage in AI Model Markets](https://mlsanity.com/paper/2603.22404/) (2026)
- [Post-Training at the Edge of Detectability: A Game-Theoretic Approach to Fine-Tuning](https://mlsanity.com/paper/2607.26358/) (2026)
- [Price of Anarchy of First-Price Auctions in Agentic Markets](https://mlsanity.com/paper/2610.20587/) (2026)

## Abstract (arXiv)

The widespread adoption of Large Language Models (LLMs) through Application Programming Interfaces (APIs) induces a critical vulnerability: the potential for dishonest manipulation by service providers. This manipulation can manifest in various forms, such as secretly substituting a proclaimed high-performance model with a low-cost alternative, or inflating responses with meaningless tokens to increase billing. This work tackles the issue through the lens of algorithmic game theory and mechanism design. We are the first to propose a formal economic model for a realistic user-provider ecosystem, where a user can iteratively delegate T queries to multiple model providers, and providers can engage in a range of strategic behaviors. As our central contribution, we prove that for a continuous strategy space and any ε∈(0,frac12), there exists an approximate incentive-compatible mechanism with an additive approximation ratio of O(T1-εlog T), and a guaranteed quasi-linear second-best user utility. We also prove an impossibility result, stating that no mechanism can guarantee an expected user utility that is asymptotically better than our mechanism. Furthermore, we demonstrate the effectiveness of our mechanism in simulation experiments with real-world API settings.