GenAI4ELab/papercli-papers huggingface dataset:
Last-iterate Convergence in Regularized Graphon Mean Field Game
Authors: Jing Dong; Baoxiang Wang; Yaoliang Yu
Venue: AAAI 2025 (main)

Abstract: To model complex real-world systems, such as traders in stock markets, or the dissemination of contagious diseases, graphon mean-field games (GMFG) have been proposed to model many agents. Despite the empirical success, our understanding of GMFG is limited. Popular algorithms such as mirror descent are deployed but remain unknown for their convergence properties. In this work, we give the first last-iterate convergence rate of mirror descent in regularized monotone GMFG. In tabular monotone GMFG with finite state and action spaces and under bandit feedback, we show a last-iterate convergence rate of O(T^{-1/4}). Moreover, when exact knowledge of costs and transitions is available, we improve this convergence rate to O(T^{-1}), matching the existing convergence rate observed in strongly convex games. In linear GMFG, our algorithm achieves a last-iterate convergence rate of O(T^{-1/5}). Finally, we verify the performance of the studied algorithms by empirically testing them against fictitious play in a variety of tasks.
Every Bit Helps: Achieving the Optimal Distortion with a Few Queries
Authors: Soroush Ebadian; Nisarg Shah
Venue: AAAI 2025 (main)

Abstract: A fundamental task in multi-agent systems is to match n agents to n alternatives (e.g., resources or tasks). This is often done by eliciting agents' ordinal rankings over the alternatives rather than their exact numerical utilities. While this simplifies elicitation, the incomplete information leads to inefficiency, captured by a worst-case measure called distortion. Recent work shows that making just a few cardinal utility queries per agent can significantly improve the distortion, with Amanatidis et al. (2024) achieving O(√n) distortion with two queries per agent. We generalize their result by achieving O(n^(1/λ)) distortion with λ queries per agent, for any constant λ, which is optimal up to a constant factor given a previous lower bound by Amanatidis et al. (2022).

We extend this finding to the general social choice problem of selecting one of m alternatives based on n agents' preferences, achieving O((min{n, m})^(1/λ)) distortion with λ queries per agent, for any constant λ, which is also optimal given prior results. Thus, our work settles open questions regarding the optimal distortion achievable with a fixed number of cardinal value queries in both settings.
Bounded Rationality Equilibrium Learning in Mean Field Games
Authors: Yannick Eich; Christian Fabian; Kai Cui; Heinz Koeppl
Venue: AAAI 2025 (main)

Abstract: Mean field games (MFGs) tractably model behavior in large agent populations. The literature on learning MFG equilibria typically focuses on finding Nash equilibria (NE), which assume perfectly rational agents and are hence implausible in many realistic situations.
To overcome these limitations, we incorporate bounded rationality into MFGs by leveraging the well-known concept of quantal response equilibria (QRE). Two novel types of MFG QRE enable the modeling of large agent populations where individuals only noisily estimate the true objective. We also introduce a second source of bounded rationality to MFGs by restricting the agents' planning horizon. The resulting novel receding horizon (RH) MFGs are combined with QRE and existing approaches to model different aspects of bounded rationality in MFGs.
We formally define MFG QRE and RH MFGs and compare them to existing equilibrium concepts such as entropy-regularized NE. Subsequently, we design generalized fixed point iteration and fictitious play algorithms to learn QRE and RH equilibria. After a theoretical analysis, we give different examples to evaluate the capabilities of our learning algorithms and outline practical differences between the equilibrium concepts.
Verifying Proportionality in Temporal Voting
Authors: Edith Elkind; Svetlana Obraztsova; Jannik Peters; Nicholas Teh
Venue: AAAI 2025 (main)

Abstract: We study a model of temporal voting where there is a fixed time horizon, and at each round the voters report their preferences over the available candidates and a single candidate is selected. Prior work has adapted popular notions of justified representation as well as voting rules that provide strong representation guarantees from the multiwinner election setting to this model. In our work, we focus on the complexity of verifying whether a given outcome offers proportional representation. We show that in the temporal setting verification is strictly harder than in multiwinner voting, but identify natural special cases that enable efficient algorithms.
Robust Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents
Authors: Seyed A. Esmaeili; Suho Shin; Aleksandrs Slivkins
Venue: AAAI 2025 (main)

Abstract: Motivated by applications such as online labor markets we consider a variant of the stochastic multi-armed bandit problem where we have a collection of arms representing strategic agents with different performance characteristics. The platform (principal) chooses an agent in each round to complete a task. Unlike the standard setting, when an arm is pulled it can modify its reward by absorbing it or improving it at the expense of a higher cost. The principle has to solve a mechanism design problem to incentivize the arms to give their best performance. However, since even with an effective mechanism agents may still deviate from rational behavior, the principal wants a robust algorithm that also gives a non-vacuous guarantee on the total accumulated rewards under non-equilibrium behavior. In this paper, we introduce a class of bandit algorithms that meet the two objectives of performance incentivization and robustness simultaneously. We do this by identifying a collection of intuitive properties that a bandit algorithm has to satisfy to achieve these objectives. Finally, we show that settings where the principal has no information about the arms' performance characteristics can be handled by combining ideas from second price auctions with our algorithms.
Distances Between Top-Truncated Elections of Different Sizes
Authors: Piotr Faliszewski; Jitka Mertlová; Pierre Nunn; Stanisław Szufa; Tomasz Wąs
Venue: AAAI 2025 (main)

Abstract: The map of elections framework is a methodology for visualizing and analyzing election datasets. So far, the framework was restricted to elections that have equal numbers of candidates, equal numbers of voters, and where all the (ordinal) votes rank all the candidates. We extend it to the case of elections of different sizes, where the votes can be top-truncated. We use our results to present a visualization of a large fragment of the Preflib database.
Individually Stable Dynamics in Coalition Formation over Graphs
Authors: Angelo Fanelli; Laurent Gourvès; Ayumi Igarashi; Luca Moscardelli
Venue: AAAI 2025 (main)

Abstract: Coalition formation over graphs is a well studied class of games whose players are vertices and feasible coalitions must be connected subgraphs. In this setting, the existence and computation of equilibria, under various notions of stability, has attracted a lot of attention. However, the natural process by which players, starting from any feasible state, strive to reach an equilibrium after a series of unilateral improving deviations, has been less studied. We investigate the convergence of dynamics towards individually stable outcomes under the following perspective: what are the most general classes of preferences and graph topologies guaranteeing convergence? To this aim, on the one hand, we cover a hierarchy of preferences, ranging from the most general to a subcase of additively separable preferences, including individually rational and monotone cases. On the other hand, given that convergence may fail in graphs admitting a cycle even in our most restrictive preference class, we analyze acyclic graph topologies such as trees, paths, and stars.
Proportionally Fair Makespan Approximation
Authors: Michal Feldman; Jugal Garg; Vishnu V. Narayan; Tomasz Ponitka
Venue: AAAI 2025 (main)

Abstract: We study fair mechanisms for the classic job scheduling problem on unrelated machines with the objective of minimizing the makespan. This problem is equivalent to minimizing the egalitarian social cost in the fair division of chores. The two prevalent fairness notions in the fair division literature are envy-freeness and proportionality. Prior work has established that no envy-free mechanism can provide better than an Ω(log m / log log m)-approximation to the optimal makespan, where m is the number of machines, even when payments to the machines are allowed. In strong contrast to this impossibility, our main result demonstrates that there exists a proportional mechanism (with payments) that achieves a 3/2-approximation to the optimal makespan, and this ratio is tight. To prove this result, we provide a full characterization of allocation functions that can be made proportional with payments. Furthermore, we show that for instances with normalized costs, there exists a proportional mechanism that achieves the optimal makespan. We conclude with important directions for future research concerning other fairness notions, including relaxations of envy-freeness. Notably, we show that the technique leading to the impossibility result for envy-freeness does not extend to its relaxations.
Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size
Authors: Foivos Fioravantes; Harmender Gahlawat; Nikolaos Melissinos
Venue: AAAI 2025 (main)

Abstract: Imagine we want to split a group of agents into teams in the most efficient way, considering that each agent has their own preferences about their teammates. This scenario is modeled by the extensively studied Coalition Formation problem. Here, we study a version of this problem where each team must additionally be of bounded size. 

We conduct a systematic algorithmic study, providing several intractability results as well as multiple exact algorithms that scale well as the input grows (FPT), which could prove useful in practice. Our main contribution is an algorithm that deals efficiently with tree-like structures (bounded treewidth) for ``small'' teams. We complement this result by proving that our algorithm is asymptotically optimal. Particularly, there can be no algorithm that vastly outperforms the one we present, under reasonable theoretical assumptions, even when considering star-like structures (bounded vertex cover number).
Fair Division with Social Impact
Authors: Michele Flammini; Gianluigi Greco; Giovanna Varricchio
Venue: AAAI 2025 (main)

Abstract: In this paper, we consider the problem of fair division of indivisible goods, where the allocation of goods impacts society. Specifically, we introduce a second valuation function for each agent, which determines the social impact of allocating a good to the agent. Such impact is considered desirable for the society -- the higher, the better. Our goal is to understand how to allocate goods fairly from the agents' perspective while maintaining society as happy as possible. To this end, we measure the impact on society using the utilitarian social welfare, and provide both possibility and impossibility results.
Our findings reveal that achieving good approximations, better than linear in the number of agents, is not possible while ensuring fairness to the agents. These impossibility results can be attributed to the fact that agents are completely unconscious of their social impact. 
Consequently, we explore scenarios where agents are socially aware, by introducing related fairness notions, and demonstrate that an appropriate definition of fairness is compatible with the social objective.
On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries
Authors: Dimitris Fotakis; Laurent Gourvès; Panagiotis Patsilinakos
Venue: AAAI 2025 (main)

Abstract: We consider committee election of k >= 3 (out of m >= k + 1) candidates, where the voters and the candidates are associated with locations on the real line. Each voter’s cardinal preferences over candidates correspond to her distance to the candidate locations, and each voter’s cardinal preferences over committees is defined as her distance to the nearest candidate elected in the committee. We consider a setting where the true distances and the locations are unknown. We can nevertheless have access to degraded information which consists of an order of candidates for each voter. We investigate the best possible distortion (a worst-case performance criterion) w.r.t. the social cost achieved by deterministic committee election rules based on ordinal preferences submitted by n voters and few additional distance queries. We show that for any k >= 3, the best possible distortion of any deterministic rule that uses at most k−3 distance queries cannot be bounded by any function of n, m and k. We present deterministic rules for k-committee election with distortion of O(n) with O(k) distance queries and O(1) with O(k log(n)) distance queries.
Forecasting Competitions with Correlated Events
Authors: Rafael Frongillo; Manuel Lladser; Anish Thilagar; Bo Waggoner
Venue: AAAI 2025 (main)

Abstract: Beginning with Witkowski et al. (2023), recent work on forecasting competitions has addressed incentive problems with the common winner-take-all mechanism. Frongillo et al. (2021) propose a competition mechanism based on Multiplicative Weights, an online learning algorithm. They show that their mechanism selects an epsilon-optimal forecaster with high probability using only O(log(n)/epsilon^2) events. These works, together with all prior work on this problem thus far, assume that events are independent. We prove the first accuracy and approximate truthfulness guarantees for forecasting competitions with correlated events. To quantify correlation, we introduce a notion of block correlation, which allows each event to be strongly correlated with up to b others and weakly correlated with the rest. We show that under distributions with this correlation, the Multiplicative Weights mechanism retains its epsilon-optimal guarantee using O(b^2 log(n)/epsilon^2) events. Our proof involves a novel concentration bound for correlated random variables which may be of broader interest.
Improved Maximin Share Approximations for Chores by Bin Packing
Authors: Jugal Garg; Xin Huang; Erel Segal-Halevi
Venue: AAAI 2025 (main)

Abstract: We study fair division of indivisible chores among n agents with additive cost functions using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist for more than two agents, the goal has been to improve its approximations and identify interesting special cases where MMS allocations exist. We show the existence of

· 1-out-of-9n/11 MMS allocations, which improves the state-of-the-art factor of 1-out-of-3n/4.
· MMS allocations for factored instances, which resolves an open question posed by Ebadian et al. (2021).
· 15/13-MMS allocations for personalized bivalued instances, improving the state-of-the-art factor of 13/11.

We achieve these results by leveraging the HFFD algorithm of Huang and Lu (2021). Our approach also provides polynomial-time algorithms for computing an MMS allocation for factored instances and a 15/13-MMS allocation for personalized bivalued instances.
(Almost Full) EFX for Three (and More) Types of Agents
Authors: Pratik Ghosal; Vishwa Prakash  HV; Prajakta Nimbhorkar; Nithin Varma
Venue: AAAI 2025 (main)

Abstract: We study the problem of determining an envy-free allocation of indivisible goods among multiple agents with additive valuations. EFX, which stands for envy-freeness up to any good, is a well-studied relaxation of the envy-free allocation problem and has been shown to exist for specific scenarios. EFX is known to exist for three agents, and for any number of agents when there are only two types of valuations. EFX allocations are also known to exist for four agents with at most one good unallocated. 
    
    In this paper, we show that EFX exists with at most k-2 goods unallocated for any number of agents having k distinct valuations. Additionally, we show that complete EFX allocations exist when all but two agents have identical valuations.
Federated Assemblies
Authors: Daniel Halpern; Ariel D. Procaccia; Ehud Shapiro; Nimrod Talmon
Venue: AAAI 2025 (main)

Abstract: A *citizens' assembly* is a group of people who are randomly selected to represent a larger population in a deliberation. While this approach has successfully strengthened democracy, it has certain limitations that suggest the need for assemblies to form and associate more organically. In response, we propose *federated assemblies*, where assemblies are interconnected, and each parent assembly is selected from members of its child assemblies. The main technical challenge is to develop random selection algorithms that meet new representation constraints inherent in this hierarchical structure. We design and analyze several algorithms that provide different representation guarantees under various assumptions on the structure of the underlying graph.
Reducing Leximin Fairness to Utilitarian Optimization
Authors: Eden Hartman; Yonatan Aumann; Avinatan Hassidim; Erel Segal-Halevi
Venue: AAAI 2025 (main)

Abstract: Two prominent objectives in social choice are utilitarian - maximizing the sum of agents' utilities, and leximin - maximizing the smallest agent's utility, then the second-smallest, etc. Utilitarianism is typically computationally easier to attain but is generally viewed as less fair.  This paper presents a general reduction scheme that, given a utilitarian solver, produces a distribution over states (deterministic outcomes) that is leximin in expectation. 
Importantly, the scheme is robust in the sense that, given an approximate utilitarian solver, it produces a lottery that is approximately-leximin (in expectation) - with the same approximation factor.  We apply our scheme to several social choice problems: stochastic allocations of indivisible goods, giveaway lotteries, and fair lotteries for participatory budgeting.
Learning to Manipulate Under Limited Information
Authors: Wesley H. Holliday; Alexander Kristoffersen; Eric Pacuit
Venue: AAAI 2025 (main)

Abstract: By classic results in social choice theory, any reasonable preferential voting method sometimes gives individuals an incentive to report an insincere preference. The extent to which different voting methods are more or less resistant to such strategic manipulation has become a key consideration for comparing voting methods. Here we measure resistance to manipulation by whether neural networks of varying sizes can learn to profitably manipulate a given voting method in expectation, given different types of limited information about how other voters will vote. We trained over 100,000 neural networks of 26 sizes to manipulate against 8 different voting methods, under 6 types of limited information, in committee-sized elections with 5-21 voters and 3-6 candidates. We find that some voting methods, such as Borda, are highly manipulable by networks with limited information, while others, such as Instant Runoff, are not, despite being quite profitably manipulated by an ideal manipulator with full information. For the three probability models for elections that we use, the overall least manipulable of the 8 methods we study are Condorcet methods, namely Minimax and Split Cycle.
Strategyproof Matching of Roommates and Rooms
Authors: Hadi Hosseini; Shivika Narang; Sanjukta Roy
Venue: AAAI 2025 (main)

Abstract: We initiate the study of matching roommates and rooms wherein the preferences of agents over other agents and rooms are complementary and represented by Leontief utilities. In this setting, 2n agents must be paired up and assigned to n rooms. Each agent has cardinal valuations over the rooms as well as compatibility values over all other agents. Under Leontief preferences, an agent’s utility for a matching is the minimum of the two values. We focus on the tradeoff between maximizing utilitarian social welfare and strategyproofness. Our main result shows that—in a stark contrast to the additive case— under binary Leontief utilities, there exist strategyproof mechanisms that maximize the social welfare. We further devise a strategyproof mechanism that implements such a welfare maximizing algorithm and is parameterized by the number of agents. Along the way, we highlight several possibility and impossibility results, and give upper bounds and lower bounds for welfare with or without strategyproofness.
TRAIL: Trust-Aware Client Scheduling for Semi-Decentralized Federated Learning
Authors: Gangqiang Hu; Jianfeng Lu; Jianmin Han; Shuqin Cao; Jing Liu; Hao Fu
Venue: AAAI 2025 (main)

Abstract: Due to the sensitivity of data, Federated Learning (FL) is employed to enable distributed machine learning while safeguarding data privacy and accommodating the requirements of various devices. However, in the context of semidecentralized FL, clients’ communication and training states are dynamic. This variability arises from local training fluctuations, heterogeneous data distributions, and intermittent client participation. Most existing studies primarily focus on stable client states, neglecting the dynamic challenges inherent in real-world scenarios. To tackle this issue, we propose a TRust-Aware clIent scheduLing mechanism called TRAIL, which assesses client states and contributions, enhancing model training efficiency through selective client participation. We focus on a semi-decentralized FL framework where edge servers and clients train a shared global model using unreliable intra-cluster model aggregation and inter-cluster model consensus. First, we propose an adaptive hidden semi-Markov model to estimate clients’ communication states and contributions. Next, we address a client-server association optimization problem to minimize global training loss. Using convergence analysis, we propose a greedy client scheduling algorithm. Finally, our experiments conducted on real-world datasets demonstrate that TRAIL outperforms state-of-the-art baselines, achieving an improvement of 8.7% in test accuracy and a reduction of 15.3% in training loss.
Learning Optimal Auctions with Correlated Value Distributions
Authors: Da Huo; Zhenzhe Zheng; Fan Wu
Venue: AAAI 2025 (main)

Abstract: The correlation of values commonly exists in auctions, which can be further exploited to improve revenue. However, the complex correlation structure makes it hard to manually design the optimal auction mechanism. Data-driven auction mechanisms, powered by machine learning, enable to design auctions directly from historical auction data, without relying on specific value distributions. In this work, we synthesize the learning-based auction and the characteristics of strategy-proofness in the correlated value setting, and propose a new auction mechanism, namely Conditional Auction Net (CAN). The CAN can encode the correlation of values into the rank score of each bidder, and further adjust the allocation rule to approach the optimal revenue. The property of strategy-proofness is guaranteed by encoding the game theoretical condition into the neural network structure. Furthermore, all operations in the designed auctions are differentiable to enable an end-to-end training paradigm. We also present CAN can provide a large solution space to adequately encode the correlation of values. Experimental results demonstrate that the proposed auction mechanism can represent almost any strategy-proof auction mechanism, and outperforms the auction mechanisms wildly used in the correlated value settings.