GenAI4ELab/papercli-papers huggingface dataset:
The Value of Recall in Extensive-Form Games
Authors: Ratip Emin Berker; Emanuel Tewolde; Ioannis Anagnostides; Tuomas Sandholm; Vincent Conitzer
Venue: AAAI 2025 (main)

Abstract: Imperfect-recall games—in which players may forget previously acquired information—have found many practical applications, ranging from game abstractions to team games and testing AI agents. In this paper, we quantify the utility gain by endowing a player with perfect recall, which we call the value of recall (VoR). While VoR can be unbounded in general, we parameterize it in terms of various game properties, namely the structure of chance nodes and the degree of absentmindedness (the number of successive times a player enters the same information set). Further, we identify several pathologies that arise with VoR, and show how to circumvent them. We also study the complexity of computing VoR, and how to optimally apportion partial recall. Finally, we connect VoR to other previously studied concepts in game theory, including the price of anarchy. We use that connection in conjunction with the celebrated smoothness framework to characterize VoR in a broad class of games.
Nearly Tight Bounds on Approximate Equilibria in Spatial Competition on the Line
Authors: Umang Bhaskar; Soumyajit Pyne
Venue: AAAI 2025 (main)

Abstract: In Hotelling's model of spatial competition, a unit mass of voters is distributed in the interval [0,1] (with their location corresponding to their political persuasion), and each of m candidates selects as a strategy their distinct position in this interval. Each voter votes for the nearest candidate, and candidates choose their strategy to maximize their votes. It is known that if there are more than two candidates, equilibria may not exist in this model. It was unknown, however, how close to an equilibrium one could get. Our work studies approximate equilibria in this model, where a strategy profile is an (additive) ϵ-equilibria if no candidate can increase their votes by ϵ, and provides tight or nearly-tight bounds on the approximation ϵ achievable.

We show that for 3 candidates, for any distribution of the voters, ϵ ≥ 1/12. Thus, somewhat surprisingly, for any distribution of the voters and any strategy profile of the candidates, at least 1/12th of the total votes is always left ``on the table.'' Extending this, we show that in the worst case, there exist voter distributions for which ϵ ≥ 1/6, and this is tight: one can always compute a 1/6-approximate equilibria in polynomial time. We then study the general case of m candidates, and show that as m grows large, we get closer to an exact equilibrium: one can always obtain a 1/(m+1)-approximate equilibria in polynomial time. We show this bound is asymptotically tight, by giving voter distributions for which ϵ ≥ 1/(m+3).
Beyond Monotonicity: On the Convergence of Learning Algorithms in Standard Auction Games
Authors: Martin Bichler; Stephan B. Lunowa; Matthias Oberlechner; Fabian R. Pieroth; Barbara Wohlmuth
Venue: AAAI 2025 (main)

Abstract: Equilibrium problems in Bayesian auction games can be described as systems of differential equations. Depending on the model assumptions, these equations might be such that we do not have a rigorous mathematical solution theory. The lack of analytical or numerical techniques with guaranteed convergence for the equilibrium problem has plagued the field and limited equilibrium analysis to rather simple auction models such as single-object auctions. 
Recent advances in equilibrium learning led to algorithms that find equilibrium under a wide variety of model assumptions. Monotonicity and the Minty condition are the known sufficient conditions for learning algorithms to converge to an equilibrium in games. 
Not much is known about convergence of learning algorithms beyond these conditions. 
We analyze first- and second-price auctions where simple learning algorithms consistently converge to an equilibrium.
The analysis is challenging, because these properties need to be shown in infinite dimensions. 
Interestingly, we show that neither monotonicity nor pseudo- or quasi-monotonicity holds for the respective variational inequalities (VIs). 
The second-price auction's equilibrium is a Minty-type solution, but the first-price auction is not. 
However, the analysis via infinite-dimensional VIs allows us to get ex-post guarantees for gradient-based algorithms. 
We show that the Bayes--Nash equilibrium is the unique solution to the VI within the class of uniformly increasing bid functions, which ensures that gradient-based algorithms attain the equilibrium in case of convergence, as also observed in numerical experiments.
Improving Cooperation in Language Games with Bayesian Inference and the Cognitive Hierarchy
Authors: Joseph Bills; Christopher Archibald; Diego Blaylock
Venue: AAAI 2025 (main)

Abstract: In two-player cooperative games, agents can play together effectively when they have accurate assumptions about how their teammate will behave, but may perform poorly when these assumptions are inaccurate. 
In language games, failure may be due to disagreement in the understanding of either the semantics or pragmatics of an utterance.  
We model coarse uncertainty in semantics using a prior distribution of language models and uncertainty in pragmatics using the cognitive hierarchy, combining the two aspects into a single prior distribution over possible partner types. 
Fine-grained uncertainty in semantics is modeled using noise that is added to the embeddings of words in the language. 
To handle all forms of uncertainty we construct agents that learn the behavior of their partner using Bayesian inference and use this information to maximize the expected value of a heuristic function.  
We test this approach by constructing Bayesian agents for the game of Codenames, and show that they perform better in  experiments where semantics is uncertain.
Weak Strategyproofness in Randomized Social Choice
Authors: Felix Brandt; Patrick Lederer
Venue: AAAI 2025 (main)

Abstract: An important - but very demanding - property in collective decision-making is strategyproofness, which requires that voters cannot benefit from submitting insincere preferences. Gibbard (1977) has shown that only rather unattractive rules are strategyproof, even when allowing for randomization. However, Gibbard's theorem is based on a rather strong interpretation of strategyproofness, which deems a manipulation successful if it increases the voter's expected utility for at least one utility function consistent with his ordinal preferences. In this paper, we study weak strategyproofness, which deems a manipulation successful if it increases the voter's expected utility for all utility functions consistent with his ordinal preferences. We show how to systematically design attractive, weakly strategyproof social decision schemes (SDSs) and explore their limitations for both strict and weak preferences. In particular, for strict preferences, we show that there are weakly strategyproof SDSs that are either ex post efficient or Condorcet-consistent, while neither even-chance SDSs nor pairwise SDSs satisfy both properties and weak strategyproofness at the same time. By contrast, for the case of weak preferences, we discuss two sweeping impossibility results that preclude the existence of appealing weakly strategyproof SDSs.
Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity
Authors: Ioannis Caragiannis; Kurt Mehlhorn; Nidhi Rathi
Venue: AAAI 2025 (main)

Abstract: Serial dictatorship is a simple mechanism for coordinating agents in solving combinatorial optimization problems according to their preferences. The most representative such problem is one-sided matching, in which a set of n agents have values for a set of n items, and the objective is to compute a matching of the agents to the items of maximum total value (a.k.a., social welfare). Following the recent framework of Caragiannis and Rathi (2023), we consider a model in which the agent-item values are not available upfront but
become known by querying agent sequences. In particular, when the agents are asked to act in a sequence, they respond by picking their favorite item that has not been picked by agents who acted before and reveal their value for it. Can we compute an agent sequence that induces a social welfare-optimal matching?

We answer this question affirmatively and present an algorithm that uses polynomial number (specifically, O(n^5) of queries). This solves the main open problem stated by Caragiannis and Rathi (2023). Our analysis uses a potential function argument that measures progress towards learning the underlying edge-weight information. Furthermore, the algorithm has a truthful implementation by adapting the paradigm of VCG payments.
Asymptotic Extinction in Large Coordination Games
Authors: Desmond Chan; Bart De Keijzer; Tobias Galla; Stefanos Leonardos; Carmine Ventre
Venue: AAAI 2025 (main)

Abstract: We study the exploration-exploitation trade-off for large multiplayer coordination games where players strategise via Q-Learning, a common learning framework in multi-agent reinforcement learning. Q-Learning is known to have two shortcomings, namely  non-convergence and potential equilibrium selection problems, when there are multiple fixed points, called Quantal Response Equilibria (QRE). Furthermore, whilst QRE have full support for finite games, it is not clear how Q-Learning behaves as the game becomes large. 

In this paper, we characterise the critical exploration rate that guarantees convergence to a unique fixed point, addressing the two shortcomings above. Using a generating-functional method, we show that this rate increases with the number of players and the alignment of their payoffs. For many-player coordination games with perfectly aligned payoffs, this exploration rate is roughly twice that of  p-player zero-sum games. As for large games, we provide a structural result for QRE, which suggests that as the game size increases, Q-Learning converges to a QRE near the boundary of the simplex of the action space, a phenomenon we term asymptotic extinction, where a constant fraction of the actions are played with zero probability at a rate o(1/N) for an  N -action game.
Mechanism Design for Connecting Regions Under Disruptions
Authors: Hau Chan; Jianan Lin; Zining Qin; Chenhao Wang
Venue: AAAI 2025 (main)

Abstract: Man-made and natural disruptions such as planned constructions on roads, suspensions of bridges, and blocked roads by trees/mudslides/floods can often create obstacles that separate two connected regions. As a result, the traveling and reachability of agents from their respective regions to other regions can be affected. To minimize the impact of the obstacles and maintain agent accessibility, we initiate the problem of constructing a new pathway (e.g., a detour or new bridge) connecting the regions disconnected by obstacles from the mechanism design perspective. In the problem, each agent in their region has a private location and is required to access the other region. The cost of an agent is the distance from their location to the other region via the pathway. Our goal is to design strategyproof mechanisms that elicit truthful locations from the agents and approximately optimize the social or maximum cost of agents by determining locations in the regions for building a pathway. We provide a characterization of all strategyproof and anonymous mechanisms. For the social and maximum costs, we provide upper and lower bounds on the approximation ratios of strategyproof mechanisms.
Adaptive Manipulation for Coalitions in Knockout Tournaments
Authors: Juhi Chaudhary; Hendrik Molter; Meirav Zehavi
Venue: AAAI 2025 (main)

Abstract: Knockout tournaments, also known as single-elimination or cup tournaments, are a popular form of sports competitions. In the standard probabilistic setting, for each pairing of players, one of the players wins the game with a certain (a priory known) probability. Due to their competitive nature, tournaments are prone to manipulation. We investigate the computational problem of determining whether, for a given tournament, a coalition has a manipulation strategy that increases the winning probability of a designated player above a given threshold. More precisely, in every round of the tournament, coalition players can strategically decide which games to throw based on the advancement of other players to the current round. We call this setting adaptive constructive coalition manipulation. To the best of our knowledge, while coalition manipulation has been studied in the literature, this is the first work to introduce adaptiveness to this context.

We show that the above problem is hard for every complexity class in the polynomial hierarchy. On the algorithmic side, we show that the problem is solvable in polynomial time when the coalition size is a constant. Furthermore, we show that the problem is fixed-parameter tractable when parameterized by the coalition size and the size of a minimum player set that must include at least one player from each non-deterministic game. Lastly, we investigate a generalized setting where the tournament tree can be imbalanced.
Online Learning of Coalition Structures by Selfish Agents
Authors: Saar Cohen; Noa Agmon
Venue: AAAI 2025 (main)

Abstract: Coalition formation concerns autonomous agents that strategically interact to form self-organized coalitions. When agents lack initial sufficient information to evaluate their preferences before interacting with others, they learn them online through repeated feedback while iteratively forming coalitions. In this work, we introduce online learning in coalition formation from a non-cooperative perspective, studying the impact of collective data utilization where selfish agents aim to accelerate their learning by leveraging a shared data platform. Thus, the efficiency and dynamics of the learning process are affected by each agent's local feedbacks, motivating us to explore the tension between semi-bandit and bandit feedback, which differ in the granularity of utility information observed by each agent. Under our non-cooperative viewpoint, we evaluate the system by means of Nash stability, where no agent can improve her utility by unilaterally deviating. Our main result is a sample-efficient algorithm for selfish agents that aims to minimize their Nash regret under both semi-bandit and bandit feedback, implying approximately Nash stable outcomes. Under both feedback settings, our algorithm enjoys Nash regret and sample complexity bounds that are optimal up to logarithmic factors.
Constrained Fair and Efficient Allocations
Authors: Benjamin Cookson; Soroush Ebadian; Nisarg Shah
Venue: AAAI 2025 (main)

Abstract: Fairness and efficiency have become the pillars of modern fair division research, but prior work on achieving both simultaneously is largely limited to the unconstrained setting. We study fair and efficient allocations of indivisible goods under additive valuations and various types of allocation feasibility constraints, and demonstrate the unreasonable effectiveness of the maximum Nash welfare (MNW) solution in this previously uncharted territory. 

Our main result is that MNW allocations are 1/2-envy-free up to one good (EF1) and Pareto optimal under the broad family of (arbitrary) matroid constraints. We extend these guarantees to complete MNW allocations for base-orderable matroid constraints, and to a family of non-matroid constraints (which includes balancedness). We establish tightness of our results by providing counterexamples for the satisfiability of certain stronger desiderata, but show an improved result for the special case of goods with copies (Gafni et al. 2023). Finally, we also establish novel best-of-both-worlds guarantees for goods with copies and balancedness.
Temporal Fair Division
Authors: Benjamin Cookson; Soroush Ebadian; Nisarg Shah
Venue: AAAI 2025 (main)

Abstract: We study temporal fair division, whereby a set of agents are allocated a (possibly different) set of goods on each day for a period of days. We study this setting, as well as a number of its special cases formed by the restrictions to two agents, same goods on each day, identical preferences, or combinations thereof, and chart out the landscape of achieving two types of fairness guarantees simultaneously: fairness on each day (per day) and fairness over time (up to each day, or the weaker version, overall).

In the most general setting, we prove that there always exists an allocation that is stochastically-dominant envy-free up to one good (SD-EF1) per day and proportional up to one good (PROP1) overall, and when all the agents have identical preferences, we show that SD-EF1 per day and SD-EF1 overall can be guaranteed. For the case of two agents, we prove that SD-EF1 per day and EF1 up to each day can be guaranteed using an envy balancing technique. We provide counterexamples for other combinations that establish our results as among the best guarantees possible, but also leave open some tantalizing questions.
Characterising Simulation-Based Program Equilibria
Authors: Emery Cooper; Caspar Oesterheld; Vincent Conitzer
Venue: AAAI 2025 (main)

Abstract: In Tennenholtz’s program equilibrium, players of a game submit programs to play on their behalf. Each program receives the other programs’ source code and outputs an action. This can model interactions involving AI agents, mutually transparent institutions, or commitments. Tennenholtz 2004 (https://doi.org/10.1016/j.geb.2004.02.002) proves a folk theorem for program games, but the equilibria constructed are very brittle. We therefore consider simulation-based programs – i.e., programs that work by running opponents’ programs. These are relatively robust (in particular, two programs that act the same are treated the same) and are more practical than proof-based approaches. Oesterheld’s (2019, https://doi.org/10.1007/s11238-018-9679-3) epsilon-Grounded-pi-Bot is such an approach. Unfortunately, it is not generally applicable to games of three or more players, and only allows for a limited range of equilibria in two player games. In this paper, we propose a generalisation to Oesterheld’s (2019) epsilon-Grounded-pi-Bot. We prove a folk theorem for our programs in a setting with access to a shared source of randomness. We then characterise their equilibria in a setting without shared randomness. Both with and without shared randomness, we achieve a much wider range of equilibria than Oesterheld’s (2019) epsilon-Grounded-pi-Bot. Finally, we explore the limits of simulation-based program equilibrium, showing that the Tennenholtz folk theorem cannot be attained by simulation-based programs without access to shared randomness.
The Complexity of Extending Fair Allocations of Indivisible Goods
Authors: Argyrios Deligkas; Eduard Eiben; Robert Ganian; Tiger-Lily Goldsmith; Stavros D. Ioannidis
Venue: AAAI 2025 (main)

Abstract: We initiate the study of computing envy-free allocations of indivisible items in the extension setting, i.e., when some part of the allocation is fixed and the task is to allocate the remaining items. In view of the NP-hardness of the problem, we investigate whether - and under which conditions - one can obtain fixed-parameter algorithms for computing a solution in settings where most of the allocation is already fixed. Our results provide a broad complexity-theoretic classification of the problem which includes: (a) fixed-parameter algorithms tailored to settings with few distinct types of agents or items; (b) lower bounds which exclude the generalization of these positive results to more general settings. We conclude by showing that - unlike when computing allocations from scratch - the non-algorithmic question of whether more relaxed EF1 or EFX allocations exist can be completely resolved in the extension setting.
Balanced and Fair Partitioning of Friends
Authors: Argyrios Deligkas; Eduard Eiben; Stavros D. Ioannidis; Dušan Knop; Šimon Schierreich
Venue: AAAI 2025 (main)

Abstract: In the recently introduced model of fair partitioning of friends, there is a set of agents located on the vertices of an underlying graph that indicates the friendships between the agents. The task is to partition the graph into k balanced-sized groups, keeping in mind that the value of an agent for a group is equal to the number of edges they have in that group. The goal is to construct partitions that are "fair", i.e., no agent would like to replace an agent in a different group. We generalize the standard model by considering utilities for the agents that are beyond binary and additive. Having this as our foundation, our contribution is threefold:
    (a) we adapt several fairness notions that have been developed in the fair division literature to our setting;
    (b) we give several existence guarantees supported by polynomial-time algorithms;
    (c) we initiate the study of the computational (and parameterized) complexity of the model and provide an almost complete landscape of the (in)tractability frontier for our fairness concepts.
Eliminating Majority Illusion Is Easy
Authors: Jack Dippel; Max Dupré la Tour; April Niu; Sanjukta Roy; Adrian Vetta
Venue: AAAI 2025 (main)

Abstract: Majority illusion is a phenomenon in social networks wherein the decision by the majority of the network is not the same as one's personal social circle's majority, leading to an incorrect perception of the majority in a large network. We present polynomial-time algorithms which completely eliminate majority illusion by altering as few connections in the network as possible. Eliminating majority illusion ensures each neighbourhood in the network has at least a 1/2-fraction of the majority winner. This result is surprising as partially eliminating majority illusion is NP-hard. We generalize the majority illusion problem to an arbitrary fraction p and show that the problem of ensuring all neighbourhoods in the network contain at least a p-fraction of nodes consistent with a given preference is NP-hard, for nearly all values of p.
Private Blotto: Viewpoint Competition with Polarized Agents
Authors: Kate Donahue; Jon Kleinberg
Venue: AAAI 2025 (main)

Abstract: Social media platforms are responsible for collecting and disseminating vast quantities of content. Recently, however, they have also begun enlisting users in helping annotate this content - for example, to provide context or label disinformation. However, users may act strategically, sometimes reflecting biases (e.g. political) about the "right" label.  How can social media platforms design their systems to use human time most efficiently? Historically, competition over multiple items has been explored in the Colonel Blotto game setting. However, they were originally designed to model two centrally-controlled armies competing over zero-sum "items", a specific scenario with limited modern-day application. In this work, we propose and study Private Blotto game, a variant with the key difference that individual agents act independently, without being coordinated by a central "Colonel". We completely characterize the Nash stability of this game and how this impacts the amount of "misallocated effort" of users on unimportant items. We show that the outcome function (aggregating multiple labels on a single item) has a critical impact, and specifically contrast a majority rule outcome (the median) as compared to a smoother outcome function (mean). In general, for median outcomes we show that instances without stable arrangements only occur for relatively few numbers of agents, but stable arrangements may have very high levels of misallocated effort. For mean outcome functions, we show that unstable arrangements can occur even for arbitrarily large numbers of agents, but when stable arrangements exist, they always have low misallocated effort. We conclude by discussing implications our results have for motivating examples in social media platforms and political competition.