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

• URL: http://arxiv.org/abs/2511.00847v3
• Date: Thu, 06 Nov 2025 02:40:22 GMT
• Title: Pay for The Second-Best Service: A Game-Theoretic Approach Against Dishonest LLM Providers
• Authors: Yuhan Cao, Yu Wang, Sitong Liu, Miao Li, Yixin Tao, Tianxing He,
• Abstract summary: This work tackles the issue through the lens of game theory and mechanism design.<n>We are the first to propose a formal economic model for a realistic user-provider ecosystem.
• Score: 18.350214149130267
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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 $\epsilon\in(0,\frac12)$, there exists an approximate incentive-compatible mechanism with an additive approximation ratio of $O(T^{1-\epsilon}\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.

Related papers

• CREDIT: Certified Ownership Verification of Deep Neural Networks Against Model Extraction Attacks [54.04030169323115]
  We introduce CREDIT, a certified ownership verification against Model Extraction Attacks (MEAs)<n>We quantify the similarity between DNN models, propose a practical verification threshold, and provide rigorous theoretical guarantees for ownership verification based on this threshold.<n>We extensively evaluate our approach on several mainstream datasets across different domains and tasks, achieving state-of-the-art performance.
  arXiv  Detail & Related papers  (2026-02-23T23:36:25Z)
• AI-NativeBench: An Open-Source White-Box Agentic Benchmark Suite for AI-Native Systems [52.65695508605237]
  We introduce AI-NativeBench, the first application-centric and white-box AI-Native benchmark suite grounded in Model Context Protocol (MCP) and Agent-to-Agent (A2A) standards.<n>By treating agentic spans as first-class citizens within distributed traces, our methodology enables granular analysis of engineering characteristics beyond simple capabilities.<n>This work provides the first systematic evidence to guide the transition from measuring model capability to engineering reliable AI-Native systems.
  arXiv  Detail & Related papers  (2026-01-14T11:32:07Z)
• Is Your LLM Overcharging You? Tokenization, Transparency, and Incentives [13.91198481393699]
  We develop an efficient algorithm that allows providers to significantly overcharge users without raising suspicion.<n>We show that to eliminate the financial incentive to strategize, a pricing mechanism must price tokens linearly on their character count.
  arXiv  Detail & Related papers  (2025-05-27T18:02:12Z)
• FLARE: Robot Learning with Implicit World Modeling [87.81846091038676]
  $textbfFLARE$ integrates predictive latent world modeling into robot policy learning.<n>$textbfFLARE$ achieves state-of-the-art performance, outperforming prior policy learning baselines by up to 26%.<n>Our results establish $textbfFLARE$ as a general and scalable approach for combining implicit world modeling with high-frequency robotic control.
  arXiv  Detail & Related papers  (2025-05-21T15:33:27Z)
• Why Ask One When You Can Ask $k$? Learning-to-Defer to the Top-$k$ Experts [6.792743621449621]
  We introduce the first framework for Top-$k$ Learning-to-Defer.<n>It allocates queries to the $k$ most cost-effective entities.<n>We also propose Top-$k(x)$ Learning-to-Defer, an adaptive variant that learns the optimal number of experts per query.
  arXiv  Detail & Related papers  (2025-04-17T14:50:40Z)
• Supervised Optimism Correction: Be Confident When LLMs Are Sure [91.7459076316849]
  We establish a novel theoretical connection between supervised fine-tuning and offline reinforcement learning.<n>We show that the widely used beam search method suffers from unacceptable over-optimism.<n>We propose Supervised Optimism Correction, which introduces a simple yet effective auxiliary loss for token-level $Q$-value estimations.
  arXiv  Detail & Related papers  (2025-04-10T07:50:03Z)
• Are You Getting What You Pay For? Auditing Model Substitution in LLM APIs [71.7892165868749]
  Commercial Large Language Model (LLM) APIs create a fundamental trust problem.<n>Users pay for specific models but have no guarantee that providers deliver them faithfully.<n>We formalize this model substitution problem and evaluate detection methods under realistic adversarial conditions.<n>We propose and evaluate the use of Trusted Execution Environments (TEEs) as one practical and robust solution.
  arXiv  Detail & Related papers  (2025-04-07T03:57:41Z)
• Strategic Prompt Pricing for AIGC Services: A User-Centric Approach [21.554792002413798]
  Current approaches overlook users' strategic two-step decision-making process in selecting and utilizing generative AI models.<n>We introduce prompt ambiguity, a theoretical framework that captures users' varying abilities in prompt engineering.<n>Our OPP algorithm achieves up to 31.72% improvement in platform payoff compared to existing pricing mechanisms.
  arXiv  Detail & Related papers  (2025-03-23T18:41:06Z)
• Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits [8.013444110633223]
  We analytically derive a class of optimal solutions to a linear program (LP) for automated mechanism design.<n>These solutions can be expressed using a set of essential variables whose cardinality is exponentially smaller than the total number of variables in the original formulation.<n>We address this by translating the evaluation of this term into a multi-armed bandit (MAB) problem.
  arXiv  Detail & Related papers  (2024-11-30T03:59:36Z)
• UniMatch: A Unified User-Item Matching Framework for the Multi-purpose Merchant Marketing [27.459774494479227]
  We present a unified user-item matching framework to simultaneously conduct item recommendation and user targeting with just one model. Our framework results in significant performance gains in comparison with the state-of-the-art methods, with greatly reduced cost on computing resources and daily maintenance.
  arXiv  Detail & Related papers  (2023-07-19T13:49:35Z)
• Probabilistically Robust Recourse: Navigating the Trade-offs between Costs and Robustness in Algorithmic Recourse [34.39887495671287]
  We propose an objective function which simultaneously minimizes the gap between the achieved (resulting) and desired recourse invalidation rates. We develop novel theoretical results to characterize the recourse invalidation rates corresponding to any given instance. Experimental evaluation with multiple real world datasets demonstrates the efficacy of the proposed framework.
  arXiv  Detail & Related papers  (2022-03-13T21:39:24Z)
• Low-Cost Algorithmic Recourse for Users With Uncertain Cost Functions [74.00030431081751]
  We formalize the notion of user-specific cost functions and introduce a new method for identifying actionable recourses for users. Our method satisfies up to 25.89 percentage points more users compared to strong baseline methods.
  arXiv  Detail & Related papers  (2021-11-01T19:49:35Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.