GenAI4ELab/papercli-papers huggingface dataset:
Α Descent-based Method on the Duality Gap for Solving Zero-sum Games
Authors: Michail Fasoulakis; Evangelos Markakis; Georgios Roussakis; Christodoulos Santorinaios
Venue: IJCAI 2025 (main)

Abstract: We focus on the design of algorithms for finding equilibria in 2-player zero-sum games. Although it is well known that such problems can be solved by a single linear program, there has been a surge of interest in recent years for simpler algorithms, motivated in part by applications in machine learning. Our work proposes such a method, inspired by the observation that the duality gap (a standard metric for evaluating convergence in min-max optimization problems) is a convex function for bilinear zero-sum games. To this end, we analyze a descent-based approach, variants of which have also been used as a subroutine in a series of algorithms for approximating Nash equilibria in general non-zero-sum games. In particular, we study a steepest descent approach, by finding the direction that minimises the directional derivative of the duality gap function. Our main theoretical result is that the derived algorithms achieve a geometric decrease in the duality gap until we reach an approximate equilibrium. Finally, we complement this with an experimental evaluation, which provides promising findings. Our algorithm is comparable with (and in some cases outperforms) some of the standard approaches for solving 0-sum games, such as OGDA (Optimistic Gradient Descent/Ascent), even with thousands of available strategies per player.
Non-Obvious Manipulability in Additively Separable and Fractional Hedonic Games
Authors: Diodato Ferraioli; Giovanna Varricchio
Venue: IJCAI 2025 (main)

Abstract: In this work, we consider the design of Non-Obviously Manipulable (NOM) mechanisms, mechanisms that bounded rational agents may fail to recognize as manipulable, for two relevant classes of succinctly representable Hedonic Games: Additively Separable and Fractional Hedonic Games. In these classes, agents have cardinal scores towards other agents, and their preferences over coalitions are determined by aggregating such scores. This aggregation results in a utility function for each agent, which enables the evaluation of outcomes via the utilitarian social welfare. We first prove that, when scores can be arbitrary, every optimal mechanism is NOM; moreover, when scores are limited in a continuous interval, an optimal mechanism that is NOM exists. Given the hardness of computing optimal outcomes in these settings, we turn our attention to efficient and NOM mechanisms. To this aim, we first prove a characterization of NOM mechanisms that simplifies the class of mechanisms of interest. Then, we design a NOM mechanism returning approximations that asymptotically match the best-known approximation achievable in polynomial time. Finally, we focus on discrete scores, where the compatibility of NOM with optimality depends on the specific values. Therefore, we initiate a systematic analysis to identify which discrete values support this compatibility and which do not.
Optimal Metric Distortion for Matching on the Line
Authors: Aris Filos-Ratsikas; Vasilis Gkatzelis; Mohamad Latifian; Emma Rewinski; Alexandros A. Voudouris
Venue: IJCAI 2025 (main)

Abstract: We study the distortion of one-sided and two-sided matching problems on the line. In the one-sided case, n agents need to be matched to n items, and each agent's cost in a matching is their distance from the item they were matched to. We propose an algorithm that is provided only with ordinal information regarding the agents' preferences (each agent's ranking of the items from most- to least-preferred) and returns a matching aiming to minimize the social cost with respect to the agents' true (cardinal) costs. We prove that our algorithm simultaneously achieves the best-possible approximation of 3 (known as distortion) with respect to a variety of social cost measures which include the utilitarian and egalitarian social cost. In the two-sided case, where the agents need be matched to n other agents and both sides report their ordinal preferences over each other, we show that it is always possible to compute an optimal matching. In fact, we show that this optimal matching can be achieved using even less information, and we provide bounds regarding the sufficient number of queries.
Beyond Symmetry in Repeated Games with Restarts
Authors: Henry Fleischmann; Kiriaki Fragkia; Ratip Emin Berker
Venue: IJCAI 2025 (main)

Abstract: Infinitely repeated games support equilibrium concepts beyond those present in one-shot games (e.g., cooperation in the prisoner's dilemma). Nonetheless, repeated games fail to capture our real-world intuition for settings with many anonymous agents interacting in pairs. Repeated games with restarts, introduced by Berker and Conitzer, address this concern by giving players the option to restart the game with someone new whenever their partner deviates from an agreed-upon sequence of actions. In their work, they studied symmetric games with symmetric strategies. We significantly extend these results, introducing and analyzing more general notions of equilibria in asymmetric games with restarts. We characterize which goal strategies players can be incentivized to play in equilibrium, and we consider the computational problem of finding such sequences of actions with minimal cost for the agents. We show that this problem is NP-hard in general. However, when the goal sequence maximizes social welfare, we give a pseudo-polynomial time algorithm.
Airdrop Games
Authors: Sotiris Georganas; Aggelos  Kiayias; Paolo Penna
Venue: IJCAI 2025 (main)

Abstract: Launching a new blockchain system or application is frequently facilitated by a so called airdrop, where the system designer chooses a pre-existing set of potentially interested parties and allocates newly minted tokens to them with the expectation that they will participate in the system — such engagement, especially if it is of significant level — facilitates the system and raises its value and also the value of its newly minted token, hence benefiting the airdrop recipients. A number of challenging questions befuddle designers in this setting, such as how to choose the set of interested parties and how to allocate tokens to them. To address these considerations we put forward a game theoretic model for such airdrop games. Our model can be used to guide the designer’s choices based on the way the system’s value depends on participation (modeled by a “technology function” in our framework) and the costs that participations incurs. We identify both bad and good equilibria and identify the settings and the choices that can be made where the designer can influence the players towards good equilibria in an expedient manner.
Strategyproofness and Monotone Allocation of Auction  in Social Networks
Authors: Yuhang Guo; Dong Hao; Bin Li; Mingyu Xiao; Bakh Khoussainov
Venue: IJCAI 2025 (main)

Abstract: Strategyproofness in network auctions requires that bidders not only report their valuations truthfully, but also do their best to invite neighbours from the social network. In contrast to canonical auctions, where the value-monotone allocation in Myerson's Lemma is a cornerstone, a general principle of allocation rules for strategyproof network auctions is still missing. We show that, due to the absence of such a principle, even extensions to multi-unit network auctions with single-unit demand present unexpected difficulties, and all pioneering researches fail to be strategyproof. For the first time in this field, we identify two categories of monotone allocation rules on networks: Invitation-Depressed Monotonicity (ID-MON) and Invitation-Promoted Monotonicity (IP-MON). They encompass all existing allocation rules of network auctions as specific instances. For any given ID-MON or IP-MON allocation rule, we characterize the existence and sufficient conditions for the strategyproof payment rules, and show that among all such payment rules, the revenue-maximizing one exists and is computationally feasible. With these results, the obstacle of combinatorial network auction with single-minded bidders is now resolved.
More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules
Authors: Sushmita  Gupta; Pallavi Jain; Souvik Saha; Saket Saurabh; Anannya Upasana
Venue: IJCAI 2025 (main)

Abstract: Multiwinner Elections have emerged as a prominent area of research with numerous practical applications. Given a set of candidates, C, a set of voters, V, approving a subset of candidates (called approval set of a voter), and an integer k, we consider the problem of selecting a ``good'' committee using Thiele rules. This problem is computationally challenging for most Thiele rules with monotone submodular satisfaction functions, as there is no (1-1/e- epsilon) approximation algorithm in f(k)(|C| + |V|)^(o(k)) time for any fixed epsilon > 0 and any computable function f, and no PTAS even when the length of approval set is two. Skowron designed an approximation scheme running in FPT time parameterized by the combined parameter, size of the approval set, and k. In this paper, we consider a parameter d+k (no d voters approve the same set of d candidates), where d is upper bounded by the size of the approval set (thus, can be much smaller). With respect to this parameter, we design parameterized approximation schemes, a lossy polynomial-time preprocessing method, and show that an extra committee member suffices to achieve the desired score (i.e., 1-additive approximation). Additionally, we resolve an open question by Yang and Wang regarding the fixed-parameter tractability of the problem under the PAV rule with the total score as the parameter, demonstrating that it admits an FPT algorithm.
The Proportional Veto Principle for Approval Ballots
Authors: Daniel Halpern; Ariel D. Procaccia; Warut Suksompong
Venue: IJCAI 2025 (main)

Abstract: The proportional veto principle, which captures the idea that a candidate vetoed by a large group of voters should not be chosen, has been studied for ranked ballots in single-winner voting. We introduce a version of this principle for approval ballots, which we call flexible-voter representation (FVR). We show that while the approval voting rule and other natural scoring rules provide the optimal FVR guarantee only for some flexibility threshold, there exists a scoring rule that is FVR-optimal for all thresholds simultaneously. We also extend our results to multi-winner voting.
Dividing Conflicting Items Fairly
Authors: Ayumi Igarashi; Pasin Manurangsi; Hirotaka Yoneda
Venue: IJCAI 2025 (main)

Abstract: We study the allocation of indivisible goods under conflicting constraints, represented by a graph. In this framework, vertices correspond to goods and edges correspond to conflicts between a pair of goods. Each agent is allocated an independent set in the graph. In a recent work of Kumar et al. (AAMAS, 2024), it was shown that a maximal EF1 allocation exists for interval graphs and two agents with monotone valuations. We significantly extend this result by establishing that a maximal EF1 allocation exists for any graph when the two agents have monotone valuations. To compute such an allocation, we present a polynomial-time algorithm for additive valuations, as well as a pseudo-polynomial time algorithm for monotone valuations. Moreover, we complement our findings by providing a counterexample demonstrating a maximal EF1 allocation may not exist for three agents with monotone valuations; further, we establish NP-hardness of determining the existence of such allocations for every fixed number n >= 3 of agents. All of our results for goods also apply to the allocation of chores.
Efficient Algorithms for Electing Successive Committees
Authors: Pallavi Jain; Andrzej Kaczmarczyk
Venue: IJCAI 2025 (main)

Abstract: In a recently introduced model of successive committee elections, for a given set of ordinal or approval preferences one aims to find a sequence of a given length of “best” same-size committees such that each candidate is a member of a limited number of consecutive committees. However, the practical usability of this model remains limited, as the described task turns out to be NP-hard for most selection criteria already for seeking committees of size three. Non-trivial or somewhat efficient algorithms for these cases are lacking too. Motivated by a desire to unlock the full potential of the described temporal model of committee elections, we devise (parameterized) algorithms that effectively solve the mentioned hard cases in realistic scenarios of a moderate number of candidates or of a limited time horizon.
Online Housing Market
Authors: Julien Lesca
Venue: IJCAI 2025 (main)

Abstract: We study an online variant of the celebrated housing market problem, where each agent owns a single house and seeks to exchange it based on her preferences. In this online setting, agents may arrive and depart at any time, meaning not all agents are present in the housing market simultaneously. We extend the well-known serial dictatorship and top trading cycle mechanisms to the online scenario, aiming to retain their desirable properties, such as Pareto efficiency, individual rationality, and strategy-proofness. These extensions also seek to prevent agents from strategically delaying their arrivals or advancing their departures. We demonstrate that achieving all these properties simultaneously is impossible and present several variants that achieve different subsets of these properties.
Fair Submodular Maximization over a Knapsack Constraint
Authors: Lijun Li; Chenyang Xu; Liuyi Yang; Ruilong Zhang
Venue: IJCAI 2025 (main)

Abstract: We consider fairness in submodular maximization subject to a knapsack constraint, a fundamental problem with various applications in economics, machine learning, and data mining. In the model, we are given a set of ground elements, each associated with a cost and a color, and a monotone submodular function defined over them. The goal is to maximize the submodular function while guaranteeing that the total cost does not exceed a specified budget (the knapsack constraint) and that the number of elements selected for each color falls within a designated range (the fairness constraint). While there exists some recent literature on this topic, the existence of a non-trivial approximation for the problem -- without relaxing either the knapsack or fairness constraints -- remains a challenging open question. This paper makes progress in this direction. We demonstrate that when the number of colors is constant, there exists a polynomial-time algorithm that achieves a constant approximation with high probability. Additionally, we show that if either the knapsack or fairness constraint is relaxed only to require expected satisfaction, a tight approximation ratio of (1-1/e-epsilon) can be obtained in expectation for any epsilon >0.
Logarithmic Approximations for Fair k-Set Selection
Authors: Shi Li; Chenyang Xu; Ruilong Zhang
Venue: IJCAI 2025 (main)

Abstract: We study the fair k-set selection problem where we aim to select k sets from a given set system such that the (weighted) occurrence times that each element appears in these k selected sets are balanced, i.e., the maximum (weighted) occurrence times are minimized. By observing that a set system can be formulated into a bipartite graph G:=(L cup R, E), our problem is equivalent to selecting k vertices from R such that the maximum (weighted) number selected neighbors of vertices in L is minimized. The problem arises in a wide range of applications in various fields, such as machine learning, artificial intelligence, and operations research. We first prove that the problem is NP-hard even if the maximum degree Delta of the input bipartite graph is 3, and the problem is in P when Delta=2. We then show that the problem is also in P when the input set system forms a laminar family. Based on intuitive linear programming, we show that two rounding algorithms achieve O(log n/(log log n))-approximation on general bipartite graphs, and an independent rounding algorithm achieves O(log(Delta))-approximation on bipartite graphs with a maximum degree Delta. We demonstrate that our analysis is almost tight by providing a hard instance for this linear programming.
Approximately EFX and fPO Allocations for Bivalued Chores
Authors: Zehan Lin; Xiaowei Wu; Shengwei Zhou
Venue: IJCAI 2025 (main)

Abstract: We consider the computation for allocations of indivisible chores that are approximately EFX and fractional Pareto optimal (fPO). It has been shown that 3-EFX and fPO allocations for bi-valued instances always exist, where the cost of an item to an agent is either 1 or k (where k > 1), by rounding the (fractional) earning restricted equilibrium. In this work, we improve the approximation ratio to (2-1/k), while preserving the fractional Pareto optimality. Instead of rounding fractional equilibrium, our algorithm starts with the integral EF1 equilibrium for bi-valued chores and reallocates items until approximate EFX is achieved. We further improve our result for the case when k=2 and devise an algorithm that computes EFX and fPO allocations.
Stackelberg vs. Nash in the Lottery Colonel Blotto Game
Authors: Yan Liu; Bonan Ni; Weiran Shen; Zihe  Wang; Jie Zhang
Venue: IJCAI 2025 (main)

Abstract: Resource competition problems are often modeled using Colonel Blotto games, where players take simultaneous actions. However, many real-world scenarios involve sequential decision-making rather than simultaneous moves. To model these dynamics, we represent the Lottery Colonel Blotto game as a Stackelberg game, in which one player, the leader, commits to a strategy first, and the other player, the follower, responds. We derive the Stackelberg equilibrium for this game, formulating the leader's strategy as a bi-level optimization problem. To solve this, we develop a constructive method based on iterative game reductions, which allows us to efficiently compute the leader’s optimal commitment strategy in polynomial time. Additionally, we identify the conditions under which the Stackelberg equilibrium coincides with the Nash equilibrium. Specifically, this occurs when the budget ratio between the leader and the follower equals a certain threshold, which we can calculate in closed form. In some instances, we observe that when the leader’s budget exceeds this threshold, both players achieve higher utilities in the Stackelberg equilibrium compared to the Nash equilibrium. Lastly, we show that, in the best case, the leader can achieve an infinite utility improvement by making an optimal first move compared to the Nash equilibrium.
Viral Marketing and Convergence Properties in Generalised Voter Model
Authors: Abhiram Manohara; Ahad N. Zehmakan
Venue: IJCAI 2025 (main)

Abstract: Consider a social network where each node (user) is blue or red, corresponding to positive or negative opinion on a topic. In the voter model, in discrete time rounds, each node picks a neighbour uniformly at random and adopts its colour. Despite its significant popularity, this model does not capture some fundamental real-world characteristics such as the difference in the strengths of connections, individuals with no initial opinion, and users who are reluctant to update. To address these issues, we introduce a generalisation of the voter model. We study the problem of selecting a set of seed blue nodes to maximise the expected number of blue nodes after some rounds. We prove that the problem is NP-hard and provide a polynomial time approximation algorithm with the best possible approximation guarantee. Our experiments on real-world and synthetic graph data demonstrate that the proposed algorithm outperforms other algorithms. We also prove that the process could take an exponential number of rounds to converge. However, if we limit ourselves to strongly connected graphs, the convergence time is polynomial and the convergence period (size of the stationary configuration) is bounded by the highest common divisor of cycle lengths in the network.
Asymptotic Analysis of Weighted Fair Division
Authors: Pasin Manurangsi; Warut Suksompong; Tomohiko Yokoyama
Venue: IJCAI 2025 (main)

Abstract: Several resource allocation settings involve agents with unequal entitlements represented by weights. We analyze weighted fair division from an asymptotic perspective: if m items are divided among n agents whose utilities are independently sampled from a probability distribution, when is it likely that a fair allocation exist? We show that if the ratio between the weights is bounded, a weighted envy-free allocation exists with high probability provided that m = Omega(n log n / log log n), generalizing a prior unweighted result. For weighted proportionality, we establish a sharp threshold of m = n / (1 - \mu) for the transition from non-existence to existence, where \mu in (0,1) denotes the mean of the distribution. In addition, we prove that for two agents, a weighted envy-free (and weighted proportional) allocation is likely to exist if m = omega(sqrt{r}), where r denotes the ratio between the two weights.
Asymptotic Fair Division: Chores Are Easier Than Goods
Authors: Pasin Manurangsi; Warut Suksompong
Venue: IJCAI 2025 (main)

Abstract: When dividing items among agents, two of the most widely studied fairness notions are envy-freeness and proportionality. We consider a setting where m chores are allocated to n agents and the disutility of each chore for each agent is drawn from a probability distribution. We show that an envy-free allocation exists with high probability provided that m >= 2n, and moreover, m must be at least n+Theta(n) in order for the existence to hold. On the other hand, we prove that a proportional allocation is likely to exist as long as m = omega(1), and this threshold is asymptotically tight. Our results reveal a clear contrast with the allocation of goods, where a larger number of items is necessary to ensure existence for both notions.
Joint-Perturbation Simultaneous Pseudo-Gradient
Authors: Carlos Martin; Tuomas Sandholm
Venue: IJCAI 2025 (main)

Abstract: We study the problem of computing an approximate Nash equilibrium of a game whose strategy space is continuous without access to gradients of the utility function. Lack of access to gradients is common in reinforcement learning settings, where the environment is treated as a black box, as well as equilibrium finding in mechanisms such as auctions, where the mechanism's payoffs are discontinuous in the players' actions. To tackle this problem, we turn to zeroth-order optimization techniques that combine pseudo-gradients with equilibrium-finding dynamics. Specifically, we introduce a new technique that requires a number of utility function evaluations per iteration that is constant rather than linear in the number of players. It achieves this by performing a single joint perturbation on all players' strategies, rather than perturbing each one individually. This is very important for many-player games, especially when the utility function is expensive to compute in terms of wall time, memory, money, or other resources. We evaluate our approach on various games, including auctions, which have important real-world applications. Our approach yields a dramatic improvement in performance in terms of the wall time required to reach an approximate Nash equilibrium.