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,1/2), 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.
论文检索
输入标题、作者或关键词，从 672 篇学术成果中精准定位
This paper presents the primary research challenges and key findings from the 15th International Automated Negotiating Agents Competition (ANAC 2025), one of the official competitions of IJCAI 2025. We focus on two critical domains: multideal negotiations and the development of agents capable of concurrent negotiation within complex supply chain management environments. Furthermore, this work analyzes the results of the competition and outlines strategic directions for future iterations.
Attributing importance to the individual components of a larger unit has become a popular method for understanding models and data in AI and machine learning. Starting with feature explanation, this method is now also used in data valuation or federated learning, just to name a few. Despite their differences, all of these applications use the same mathematical attribution mechanism: the Shapley value, which is rooted in cooperative game theory. While the Shapley value is appealing and has strong axiomatic foundations, it is computationally intractable due to the combinatorial explosion of player subsets. Therefore, there is a need for approximation algorithms, which have been studied intensively in recent years. This survey provides an overview of general-purpose approximation methods applicable to any domain. We categorize these methods into algorithmic classes, compare their properties, and highlight connections between approaches in a comprehensive taxonomy.
Liquid democracy encompasses a family of decision-making processes where votes can be cast directly or passed along proxy chains. We provide a community-maintainable and systematic survey of (computational) social choice papers on liquid democracy, organized through a searchable taxonomy of core modeling features that have appeared in the literature. Drawing on the insights from our survey, we also outline a number of research directions, which we consider of special importance for both the theory and practice of liquid democracy.
Letting AI agents interact in multi-agent settings in- troduces significant complexity in predicting and interpreting their collective behavior, with pro- found implications for trustworthy AI adoption in research and society. We present FAIRGAME (Framework for AI Agents Bias Recognition us- ing Game Theory), an open-source framework that simulates game-theoretic scenarios with LLM- based agents to systematically uncover biases aris- ing from model choice, language, agent personal- ity, and more. Applied to the Prisoner’s Dilemma and Battle of the Sexes across four LLMs and five human languages, FAIRGAME reveals inconsis- tencies across LLM models and consistent devia- tions from game-theoretic predictions; it also quan- tifies LLM-specific behavioral tendencies through a novel scoring system. Our results show that LLMs draw on prior world knowledge beyond payoff ma- trices, and that language and personality signifi- cantly shape strategic outcomes, supporting the use of reproducible and controlled simulation pipelines to predict the interacting behavior of LLM agents.
The Tournament Fixing Problem (TFP) asks whether a knockout tournament can be scheduled to guarantee that a given player v* wins. Although TFP is NP-hard in general, it is known to be fixed-parameter tractable (FPT) when parameterized by the feedback arc/vertex set number, or the in/out-degree of v*. However, it remained open whether TFP is FPT with respect to the subset FAS number of v* --- the minimum number of arcs intersecting all cycles containing v* --- a parameter that is never larger than the aforementioned ones. In this paper, we resolve this question negatively by proving that TFP stays NP-hard even when the subset FAS number of v* is constant ≥ 1 and either the subgraph induced by the in-neighbors D[N_{in}(v*)] or the out-neighbors D[N_{out}(v*)] is acyclic. Conversely, when both D[N_{in}(v*)] and D[N_{out}(v*)] are acyclic, we show that TFP becomes FPT parameterized by the subset FAS number of v*. Furthermore, we provide sufficient conditions under which v* can win even when this parameter is unbounded.
Stable matching mechanisms are fundamental to market design but face an inherent tension between stability and social welfare optimality. We study a natural relaxation of stability, termed α-stability, which models agents as willing to deviate only when the potential improvement is sufficiently large. Under α-stability, no pair of agents can deviate and improve their valuations by more than a factor of 1/α, with α ∈ (0,1]. We provide a complete characterization of the stability--efficiency tradeoff under asymmetric valuations. This tradeoff depends on the degree of asymmetry μ ∈ (0,1], which bounds the ratio between agents’ valuations for any pair. Our results show that relaxing stability can substantially improve achievable efficiency guarantees. We further present a polynomial-time algorithm that computes an α-stable matching attaining the best possible efficiency guarantee. For α ≤ μ/(μ+1), our algorithm achieves 1-efficiency; for larger α, it computes an α-stable matching achieving at least (1/α) · μ/(μ+1) of the optimal social welfare. Remarkably, our algorithm inflates the values of an optimal matching and then applies the Gale–Shapley algorithm to the modified instance. Finally, we show that computing an optimal α-stable matching is NP-hard, even under slight relaxations of stability, i.e., for α close to 1.
Envy-free (EF) allocation is a fundamental problem at the intersection of theoretical computer science and economics. When resources are indivisible, achieving an EF allocation is often impossible. A common remedy is to compensate agents with subsidies. Brustle et al. proved that a total subsidy of n-1 is both necessary and sufficient to guarantee EF in the worst case, where n is the number of agents and each agent has additive valuations with marginal values of at most 1 per item. In this paper, we consider a constrained setting, namely graph orientation, that was recently introduced by Christodoulou et al. In this model, agents correspond to vertices in a multigraph, and resources correspond to edges, with each edge allocated to one of its two incident agents. Despite extensive study of the graph orientation model, it remains unclear how much subsidy is sufficient to guarantee EF. We show that a total subsidy of n/2 is always sufficient to guarantee EF in any multigraph, halving the subsidy required in the unconstrained setting, and provide a polynomial-time algorithm to compute such an allocation. We show that this bound is tight, even for simple graphs.
Machine unlearning has become a critical capability for AI services to comply with evolving privacy regulations. A key yet underexplored challenge is how to verify whether a profit-driven AI server has faithfully performed unlearning. Existing verification approaches either incur prohibitive costs or provide insufficient deterrence, failing to balance audit cost and enforcement effectiveness. To bridge this gap, we propose UAG, a game-theoretic unlearning auditing framework that incentivizes truthful unlearning via strategic deterrence rather than exhaustive verification. We design a hierarchical auditing mechanism that combines low-cost screening with selectively triggered high-precision verification, and models the server-auditor interaction as a three-stage dynamic Bayesian game. By characterizing the equilibrium strategy, we derive optimal audit and penalty policies that incentivize honest unlearning. Theoretical analysis and experiments show that UAG maintains reliable detection while achieving a favorable cost-deterrence trade-off. Notably, UAG attains a server honesty rate of approximately 95% while screening only about 50% of unlearning requests, showing its practicality for trustworthy black-box unlearning services.
We study EFX and approximate EFX allocations of indivisible goods among agents with at most k distinct valuations (i.e., k types of agents). For exact EFX, it is known that an EFX allocation always exists when there are at most three types of agents. For approximate EFX, the best known guarantee is a 0.618-EFX allocation, and this has been improved recently to a φ-EFX allocation when the number of agents is at most seven. We settle another natural case in this landscape by showing that a φ-EFX allocation exists for any number of agents whenever there are at most four distinct valuations. We then consider a relaxation, EFX with charity, where some goods may remain unallocated and no agent envies the set of unallocated goods. It is known that, for n agents and any ε ∈ (0, 1/2], there exists an EFXε allocation with at most Õ((n/ε)^(1/2)) goods allocated to charity. We prove that when there are at most k distinct valuation types, there exists an EFXε allocation with only Õ((k/ε)^(1/2)) goods allocated to charity; in particular, the required amount of charity is sublinear in the number of distinct valuations rather than in the number of agents. We show that any EFX guarantee for k types of agents can be extended, with an additional (1 − 2ε) approximation factor, to a more general setting where the valuations can be partitioned into k clusters such that the maximum heterogeneity of valuations within each cluster is at most ε.
We study the allocation of m indivisible chores among n agents with additive disutilities under the fairness notion of envy-freeness up to one chore (EF1) and the efficiency notion of Pareto-optimality (PO). Although the existence of an allocation satisfying both EF1 and PO was recently established using a highly non-constructive fixed-point argument, an effective algorithm for computing such an allocation remains elusive, prompting the study of meaningful relaxations of these desiderata. Prior work introduced a natural relaxation through the concept of epistemic fairness: an allocation is said to be epistemic EF1 (EEF1), if for every agent i, it is possible to re-allocate the bundles of agents other than i such that i becomes EF1. In this work, we present a pseudo-polynomial time algorithm for computing an allocation of chores that is both EEF1 and PO. This gives an efficient polynomial-time algorithm for most practical settings where disutility values are integral and polynomially bounded in m and n. Our result employs the competitive equilibrium framework and relies on several technical insights that both utilize the distinct structure of epistemic EF1 and address the challenges it introduces.
Our work evolves around Fictitious Play, one of the first iterative methods that is known to converge to a Nash equilibrium in zero-sum games. In recent years, there has been a revived interest, due to applications in various machine learning problems, which has motivated a line of work on its convergence properties and on proposing new variants of the initial algorithm. Our paper is along this direction and introduces one new variant, which we refer to as Almost Greedy Fictitious Play. The proposed algorithm greedily attempts to find the optimal stepsize at each iteration but its search space is constrained and includes almost all the line between the cumulative mixed strategy and the current best response. Our main result is that the method achieves an instance dependent convergence rate of O(1/T) with respect to the duality gap. This matches the rate of Continuous Fictitious Play, and offers an alternative to discretization. We complement our theoretical findings with experiments that demonstrate the effectiveness of the method.
We consider the problem of assessing a group of nodes in a network. Our focus is on vitality indices—a natural class of centrality measures that evaluate the importance of a node by examining the impact of its removal on the network. We conduct a comprehensive analysis of group vitality indices. Specifically, we show that every vitality index admits a unique extension to groups, which can be defined using a group variant of the Shapley value recently proposed in the literature. We also provide an axiomatization of the entire class, along with two specific group vitality indices that satisfy additional normalization conditions. Furthermore, we study the computational properties of all vitality indices, as well as Group Attachment Centrality.
The communication complexity of a voting rule is the worst-case number of bits that n voters must transmit to a central authority under the most efficient elicitation protocol in an election with m candidates. We study the communication complexity of Instant-Runoff Voting (IRV). Conitzer and Sandholm [2005] established an upper bound of O(n (log m)^2), but did not provide a matching lower bound beyond Omega(n log m). We resolve this open problem by raising the lower bound to Omega(n (log m)^2) using the fooling set technique, thereby showing that the communication complexity of IRV is Theta(n (log m)^2). We further show that this complexity drops to Theta(n log m) under the single-peakedness restriction, and that both the IRV-Average variant and Single Transferable Vote (STV), the multiwinner extension of IRV, have the same asymptotic communication complexity as IRV. (Extended version with appendices: https://shs.hal.science/hal-05566718. Short video: https://youtu.be/gTXV3R2DS6o.)
We study the optimal design of a self-financing event, a problem that requires balancing the recruitment of costly, positive-value participants with revenue-generating agents who may impose negative values on the event. We introduce a novel two-sided mechanism design framework with plus agents equipped with private costs and positive impact, and minus agents with private values and negative impact upon inclusion in the event, to maximize the overall quality of the event under a budget-balanced (BB) constraint so that the designer does not run a deficit. We conduct a comprehensive study on the theory of optimal event curation on various utility functions. For additive utility, we fully characterize the optimal incentive-compatible Bayesian mechanism under both the ex-ante and ex-post BB constraints. For submodular utility, we propose an ex-ante BB mechanism that achieves a constant-factor approximation to the optimal Bayesian mechanism.
We study the limit CM rate of single-winner voting rules under Impartial Culture, defined as the probability that a preference profile is coalitionally manipulable in the limit of large electorates. For three candidates, Lepelley and Valognes [1999] derived a closed-form expression for Plurality with Runoff, or equivalently Instant-Runoff Voting (IRV), and showed that its limit CM rate is strictly below one. This is remarkable because Kim and Roush [1996] established a limit of one for several major rules, including Maximin and all positional scoring rules except Veto. In this paper, we generalize the result of Lepelley and Valognes to any number of candidates greater than or equal to four. We show that Plurality with Runoff has a limit CM rate equal to one for all such numbers of candidates, whereas IRV retains a limit CM rate strictly below one. To this end, we rely on the notion of Super Condorcet Winner, recently introduced by Durand [2025], which yields an upper bound on the CM rate of IRV. We prove that this bound is asymptotically tight and compute the probability that a Super Condorcet Winner exists, thereby obtaining the exact limit CM rate of IRV. (Extended version with appendices: https://hal.science/hal-05566713. Short video: https://youtu.be/4i2A7qUP-eo.)
An index is a function that measures the extent to which an election has a particular feature. We seek indices that capture agreement, diversity, and polarization among voters in approval elections, normalized with respect to saturation. The latter means that if two elections differ by the fraction of candidates approved by an average voter, but otherwise are of similar nature, then they should have similar index values. We propose several indices, analyze their properties, and use them to derive a new map of approval elections, and compare various real-life elections from Pabulib, Preflib and other sources.
We study the problem of allocating a set of indivisible items among agents whose preferences include externalities. Unlike the standard fair division model, agents may derive positive or negative utility not only from items allocated directly to them, but also from items allocated to other agents. Since exact envy-freeness cannot be guaranteed, prior work has focused on its relaxations. However, two central questions remained open: does there always exist an allocation that is envy-free up to one item (EF1), and if not, what is the optimal relaxation EF-k that can always be attained? We settle both questions by deriving tight asymptotic bounds on the number of items sufficient to eliminate envy. We show that for any instance with n agents, an allocation that is envy-free up to O(√n) items always exists and can be found in polynomial time. Additionally, via a reduction from fair division with externalities to discrepancy theory combined with recent discrepancy lower bounds, we prove a matching Ω(√n) lower bound showing that this result is tight even when the valuations are binary and satisfy the no-chores condition, which refutes a conjecture from previous work and resolves the main open question in the area, ruling out the existence of EF1 allocations when agents have externalities.
In this paper, we prove the existence of an envy-free up to one item (EF1) division for a discrete chore. Our approach builds upon the powerful Simmons-Su framework, which leverages Sperner’s lemma to guarantee the existence of a simplex corresponding to a sequence of similar fractional divisions, ensuring that each agent is satisfied with a different bundle. For allocations of goods, existing works have introduced rounding techniques that convert an envy-free fractional division into a connected integral EF1 division for any number of agents with monotone valuations. However, the analogous problem for chores has remained unresolved, and existing rounding techniques fail due to the asymmetric definitions of EF1 for goods and chores. To overcome this asymmetry, we refine the existing rounding techniques and show that connected EF1 divisions exist for a discrete chore.
The quantal response (QR) model is widely used in Stackelberg security games (SSGs) to capture boundedly rational adversaries. Existing work on SSGs under QR, however, almost exclusively assumes a homogeneous attacker population, ignoring heterogeneity in attacker preferences and rationality. We study SSG with mixed quantal response attackers, where the follower population consists of multiple discrete attacker types, each following a type-specific QR model. The defender allocates limited resources across targets, while an attacker drawn from this heterogeneous population observes the defender’s strategy and attacks a single target. This results in a highly non-convex equilibrium computation problem. We develop a polynomial-time approximation scheme (PTAS) for this setting when the number of attacker types is bounded, based on an exponential cone programming formulation combined with a carefully designed Branch-and-Bound procedure. Experiments demonstrate that our approach outperforms standard gradient-based methods and that explicitly modeling attacker heterogeneity yields significant gains over traditional SSG models with a single QR attacker.