GenAI4ELab/papercli-papers huggingface dataset:
Variety-Seeking Jump Games on Graphs
Authors: Lata Narayanan; Jaroslav Opatrny; Shanmukha Tummala; Alexandros A. Voudouris
Venue: IJCAI 2025 (main)

Abstract: We consider a class of jump games in which agents of different types occupy the nodes of a graph aiming to maximize the variety of types in their neighborhood. In particular, each agent derives a utility equal to the number of types different from its own in its neighborhood. We show that the jump game induced by the strategic behavior of the agents (who aim to maximize their utility) may in general have improving response cycles, but is a potential game under any of the following four conditions: there are only two types of agents; or exactly one empty node; or the graph is of degree at most 2; or the graph is 3-regular and there are two empty nodes. Additionally, we show that on trees, cylinder graphs, and tori, there is always an equilibrium. Finally, we show tight bounds on the price of anarchy with respect to two different measures of diversity: the social welfare (the total utility of the agents) and the number of colorful edges (that connect agents of different types).
The Core of Approval-Based Committee Elections with Few Seats
Authors: Dominik Peters
Venue: IJCAI 2025 (main)

Abstract: In an approval-based committee election, the goal is to select a committee consisting of k out of m candidates, based on n voters who each approve an arbitrary number of the candidates. The core of such an election consists of all committees that satisfy a certain stability property which implies proportional representation. In particular, committees in the core cannot be "objected to" by a coalition of voters who is underrepresented. The notion of the core was proposed in 2016, but it has remained an open problem whether it is always non-empty. We prove that core committees always exist when k ≤ 8, for any number of candidates m and any number of voters n, by showing that the Proportional Approval Voting (PAV) rule, proposed by Thiele in 1895, always satisfies the core when k ≤ 7 and always selects at least one committee in the core when k = 8. We also develop an artificial rule based on recursive application of PAV, and use it to show that the core is non-empty whenever there are m ≤ 15 candidates, for any committee size k ≤ m and any number of voters n. These results are obtained with the help of computer search using linear programs.
Optimal Capacity Modification for Stable Matchings with Ties
Authors: Keshav Ranjan; Meghana Nasre; Prajakta Nimbhorkar
Venue: IJCAI 2025 (main)

Abstract: We consider the Hospitals/Residents (HR) problem in the presence of ties in preference lists of hospitals. Among the three notions of stability, viz. weak, strong, and super stability, we focus on strong stability. Strong stability is appealing both theoretically and practically; however, its existence is not guaranteed. In this paper, our objective is to optimally augment the quotas of hospitals to ensure that a strongly stable matching exists in the modified instance. Such an augmentation is guaranteed to exist when resident preference lists are strict. We explore two natural optimization criteria: (i) minimizing the total capacity increase across all hospitals (MINSUM) and (ii) minimizing the maximum capacity increase for any hospital (MINMAX). We show that the MINSUM problem admits a polynomial-time algorithm, whereas the MINMAX problem is NP-hard. We prove an analogue of the Rural Hospitals theorem for the MINSUM problem. When each hospital incurs a cost for a unit increase in its quota, the MINSUM problem becomes NP-hard, even for 0/1 costs. In fact, we show that the problem cannot be approximated to any multiplicative factor. We also present a polynomial-time algorithm for optimal MINSUM augmentation when a specified subset of edges is required to be included in the matching.
Improved Approximation Ratio for Strategyproof Facility Location on a Cycle
Authors: Krzysztof Rogowski; Marcin Dziubiński
Venue: IJCAI 2025 (main)

Abstract: We study the problem of design of strategy-proof in expectation (SP) mechanisms for facility location on a cycle, with the objective of minimizing the sum of costs of n agents. We show that there exists an SP mechanism that attains an approximation ratio of 7/4 with respect to the sum of costs of the agents, thus improving the best known upper bound of 2 - 2/n in the cases of n ≥ 5. The mechanism obtaining the bound randomizes between two mechanisms known in the literature: the Random Dictator (RD) and the Proportional Circle Distance (PCD) mechanism of Meir (2019). To prove the result, we propose a cycle-cutting technique that allows for estimating the problem on a cycle by a problem on a line.
Discrete Budget Aggregation: Truthfulness and Proportionality
Authors: Ulrike Schmidt-Kraepelin; Warut Suksompong; Markus Utke
Venue: IJCAI 2025 (main)

Abstract: We study a budget aggregation setting where voters express their preferred allocation of a fixed budget over a set of alternatives, and a mechanism aggregates these preferences into a single output allocation. Motivated by scenarios in which the budget is not perfectly divisible, we depart from the prevailing literature by restricting the mechanism to output allocations that assign integral amounts. This seemingly minor deviation has significant implications for the existence of truthful mechanisms. Specifically, when voters can propose fractional allocations, we demonstrate that the Gibbard-Satterthwaite theorem can be extended to our setting. In contrast, when voters are restricted to integral ballots, we identify a class of truthful mechanisms by adapting moving-phantom mechanisms to our context. Finally, we show that while a weak form of proportionality can be achieved alongside truthfulness, stronger proportionality notions derived from approval-based committee voting are incompatible with truthfulness.
Finding Possible Winners in Spatial Voting with Incomplete Information
Authors: Hadas Shachnai; Rotem Shavitt; Andreas Wiese
Venue: IJCAI 2025 (main)

Abstract: We consider a spatial voting model where both candidates and voters are positioned in the d-dimensional Euclidean space, and each voter ranks candidates based on their proximity to the voter's ideal point. We focus on the scenario where the given information about the locations of the voters' ideal points is incomplete; for each dimension, only an interval of possible values is known. In this context, we investigate the computational complexity of determining the possible winners under positional scoring rules. Our results show that the possible winner problem in one dimension is solvable in polynomial time for all k-truncated voting rules with constant k. Moreover, for some scoring rules for which the possible winner problem is NP-complete, such as approval voting for any dimension or k-approval for two or more dimensions, we give an FPT algorithm parameterized by the number of candidates. Finally, we classify tractable and intractable settings of the em weighted possible winner problem in one dimension, and resolve the computational complexity of the weighted case for all two-valued positional scoring rules when d=1.
Improved MMS Approximations for Few Agent Types
Authors: Parnian Shahkar; Jugal Garg
Venue: IJCAI 2025 (main)

Abstract: We study fair division of indivisible goods under the maximin share (MMS) fairness criterion in settings where agents are grouped into a small number of types, with agents within each type having identical valuations. For the special case of a single type, an exact MMS allocation is always guaranteed to exist. However, for two or more distinct agent types, exact MMS allocations do not always exist, shifting the focus to establishing the existence of approximate-MMS allocations. A series of works over the last decade has resulted in the best-known approximation guarantee of 3/4 + 3/3836. In this paper, we improve the approximation guarantees for settings where agents are grouped into two or three types, a scenario that arises in many practical settings. Specifically, we present novel algorithms that guarantee a 4/5-MMS allocation for two agent types and a 16/21-MMS allocation for three agent types. Our approach leverages the MMS partition of the majority type and adapts it to provide improved fairness guarantees for all types.
Probabilistic Analysis of Stable Matching in Large Markets with Siblings
Authors: Zhaohong Sun; Tomohiko Yokoyama; Makoto Yokoo
Venue: IJCAI 2025 (main)

Abstract: We study a practical centralized matching problem which assigns children to daycare centers. The collective preferences of siblings from the same family introduce complementarities, which can lead to the absence of stable matchings, as observed in the hospital-doctor matching problems involving couples. Intriguingly, stable matchings are consistently observed in real-world daycare markets, despite the prevalence of sibling applicants. We conduct a probabilistic analysis of large random markets to examine the existence of stable matchings in such markets. Specifically, we focus on scenarios where daycare centers have similar priorities over children, a common characteristic in real-world markets. Our analysis reveals that as the market size approaches infinity, the likelihood of stable matchings existing converges to 1. To facilitate our exploration, we refine an existing heuristic algorithm to address a more rigorous stability concept, as the original one may fail to meet this criterion. Through extensive experiments on both real-world and synthetic datasets, we demonstrate the effectiveness of our revised algorithm in identifying stable matchings, particularly when daycare priorities exhibit high similarity.
A Little Subsidy Ensures MMS Allocation for Three Agents
Authors: Xiaowei Wu; Quan Xue; Shengwei Zhou
Venue: IJCAI 2025 (main)

Abstract: We consider the problem of fair allocation of m indivisible items to a group of n agents with subsidies (money). We address scenarios where agents have general additive cost/utility functions. Our work primarily focuses on the special case of three agents. Assuming that the maximum cost/utility of an item to an agent can be compensated by one dollar, we demonstrate that a total subsidy of 1/6 dollars is sufficient to ensure the existence of Maximin Share (MMS) allocations for both goods and chores. Additionally, we provide examples to establish the lower bounds of the required subsidies.
Revisiting Proportional Allocation with Subsidy: Simplification and Improvements
Authors: Xiaowei Wu; Quan Xue; Shengwei Zhou
Venue: IJCAI 2025 (main)

Abstract: In this paper, we revisit the problem of fair allocation with subsidy. We first consider the allocation of m indivisible chores to n agents with additive (dis)utility functions. Under the assumption that the maximum (dis)utility of an item can be compensated by one dollar, Wu et al. (WINE 2023) showed that a total of n/4 dollars suffices to guarantee a proportional allocation by rounding fractional allocations. Their subsidy guarantee is optimal when n is even. For odd n, there is still a small gap between the upper and lower bounds for the total subsidy. In this paper, we propose a much simpler algorithm for the problem, which does not require rounding fractional allocations, and achieves an optimal subsidy guarantee for all values of n. Different from existing works, our algorithm does not require the computation and rounding of fractional allocations and admits a much simpler analysis. We further show that our algorithm and analysis framework can be extended to the mixture of (subjective) goods and chores, achieving the optimal subsidy guarantee.
Public Signaling in Markets with Information Asymmetry Using a Limited Number of Signals
Authors: Xu Zhao; Ren Liu; Weiran Shen
Venue: IJCAI 2025 (main)

Abstract: Consider a market with a seller and many buyers. The seller has a kind of item for sale to the buyers. The items have a quality and each buyer has a private type. The quality is only known to the seller, and the buyers only have a prior belief of the quality. A third party (e.g., intermediaries or product reviewers) is able to reveal information about the actual quality by using a so-called signaling scheme. After receiving the information, buyers can update their beliefs accordingly and decide whether to buy the items. We consider the third party's problem of maximizing the purchasing probability by sending signals. However, the optimal signaling scheme has implementation issues, as the number of signals in the optimal scheme is the same as the number of buyer types, which can be exceedingly large or even infinite. We therefore investigate whether a finite and limited set of signals could still approximate the performance of the optimal signaling scheme. Unfortunately, our results show that with a finite number of signals, no signaling scheme can achieve a certain fraction of the performance of the optimal signaling scheme. This limitation persists even with the regularity or the monotone hazard rate assumption. Nevertheless, we identify a mild technical condition under which the third party can approximate the optimal performance within a constant factor by employing only two signals. We also conduct extensive experiments to substantiate our theoretic results. These experiments compare the performance of using a small signal set across different value distributions. Despite the negative results, our experiment results show that using only a small number of signals is able to achieve a fairly reasonable performance in average cases.
Implicitly Aligning Humans and Autonomous Agents through Shared Task Abstractions
Authors: Stéphane Aroca-Ouellette; Miguel Aroca-Ouellette; Katharina von der Wense; Alessandro  Roncone
Venue: IJCAI 2025 (main)

Abstract: In collaborative tasks, autonomous agents fall short of humans in their capability to quickly adapt to new and unfamiliar teammates. We posit that a limiting factor for zero-shot coordination is the lack of shared task abstractions, a mechanism humans rely on to implicitly align with teammates. To address this gap, we introduce HA^2: Hierarchical Ad Hoc Agents, a framework leveraging hierarchical reinforcement learning to mimic the structured approach humans use in collaboration. We evaluate HA^2 in the Overcooked environment, demonstrating statistically significant improvement over existing baselines when paired with both unseen agents and humans, providing better resilience to environmental shifts, and outperforming all state-of-the-art methods.
Binary Event-Driven Spiking Transformer
Authors: Honglin Cao; Zijian Zhou; Wenjie Wei; Yu Liang; Ammar Belatreche; Dehao Zhang; Malu Zhang; Yang Yang; Haizhou Li
Venue: IJCAI 2025 (main)

Abstract: Transformer-based Spiking Neural Networks (SNNs) introduce a novel event-driven self-attention paradigm that combines the high performance of Transformers with the energy efficiency of SNNs. However, the larger model size and increased computational demands of the Transformer structure limit their practicality in resource-constrained scenarios. In this paper, we integrate binarization techniques into Transformer-based SNNs and propose the Binary Event-Driven Spiking Transformer, i.e. BESTformer. The proposed BESTformer can significantly reduce storage and computational demands by representing weights and attention maps with a mere 1-bit. However, BESTformer suffers from a severe performance drop from its full-precision counterpart due to the limited representation capability of binarization. To address this issue, we propose a Coupled Information Enhancement (CIE) method, which consists of a reversible framework and information enhancement distillation. By maximizing the mutual information between the binary model and its full-precision counterpart, the CIE method effectively mitigates the performance degradation of the BESTformer. Extensive experiments on static and neuromorphic datasets demonstrate that our method achieves superior performance to other binary SNNs, showcasing its potential as a compact yet high-performance model for resource-limited edge devices. The repository of this paper is available at https://github.com/CaoHLin/BESTFormer.
Credit Assignment and Fine-Tuning Enhanced Reinforcement Learning for Collaborative Spatial Crowdsourcing
Authors: Wei Chen; Yafei Li; Baolong Mei; Guanglei Zhu; Jiaqi Wu; Mingliang Xu
Venue: IJCAI 2025 (main)

Abstract: Collaborative spatial crowdsourcing leverages distributed workers' collective intelligence to accomplish spatial tasks. A central challenge is to efficiently assign suitable workers to collaborate on these tasks. Although mainstream reinforcement learning (RL) methods have proven effective in task allocation, they face two key obstacles: delayed reward feedback and non-stationary data distributions, both hindering optimal allocation and collaborative efficiency. To address these limitations, we propose CAFE (credit assignment and fine-tuning enhanced), a novel multi-agent RL framework for spatial crowdsourcing. CAFE introduces a credit assignment mechanism that distributes rewards based on workers' contributions and spatiotemporal constraints, coupled with bi-level meta-optimization to jointly optimize credit assignment and RL policy. To handle non-stationary spatial task distributions, CAFE employs an adaptive fine-tuning procedure that efficiently adjusts credit assignment parameters while preserving collaborative knowledge. Experiments on two real-world datasets validate the effectiveness of our framework, demonstrating superior performance in terms of task completion and equitable reward redistribution.
Inference of Human-derived Specifications of Object Placement via Demonstration
Authors: Alex Cuellar; Ho Chit Siu; Julie A Shah
Venue: IJCAI 2025 (main)

Abstract: As robots' manipulation capabilities improve for pick-and-place tasks (e.g., object packing, sorting, and kitting), methods focused on understanding human-acceptable object configurations remain limited expressively with regard to capturing spatial relationships important to humans. To advance robotic understanding of human rules for object arrangement, we introduce positionally-augmented RCC (PARCC), a formal logic framework based on region connection calculus (RCC) for describing the relative position of objects in space. Additionally, we introduce an inference algorithm for learning PARCC specifications via demonstrations. Finally, we present the results from a human study, which demonstrate our framework's ability to capture a human's intended specification and the benefits of learning from demonstration approaches over human-provided specifications.
ListenNet: A Lightweight Spatio-Temporal Enhancement Nested Network for Auditory Attention Detection
Authors: Cunhang Fan; Xiaoke Yang; Hongyu Zhang; Ying Chen; Lu Li; Jian Zhou; Zhao Lv
Venue: IJCAI 2025 (main)

Abstract: Auditory attention detection (AAD) aims to identify the direction of the attended speaker in multi-speaker environments from brain signals, such as Electroencephalography (EEG) signals. However, existing EEG-based AAD methods overlook the spatio-temporal dependencies of EEG signals, limiting their decoding and generalization abilities. To address these issues, this paper proposes a Lightweight Spatio-Temporal Enhancement Nested Network (ListenNet) for AAD. The ListenNet has three key components: Spatio-temporal Dependency Encoder (STDE), Multi-scale Temporal Enhancement (MSTE), and Cross-Nested Attention (CNA). The STDE reconstructs dependencies between consecutive time windows across channels, improving the robustness of dynamic pattern extraction. The MSTE captures temporal features at multiple scales to represent both fine-grained and long-range temporal patterns. In addition, the CNA integrates hierarchical features more effectively through novel dynamic attention mechanisms to capture deep spatio-temporal correlations. Experimental results on three public datasets demonstrate the superiority of ListenNet over state-of-the-art methods in both subject-dependent and challenging subject-independent settings, while reducing the trainable parameter count by approximately 7 times. Code is available at:https://github.com/fchest/ListenNet.
Stochasticity-aware No-Reference Point Cloud Quality Assessment
Authors: Songlin Fan; Wei Gao; Zhineng Chen; Ge Li; Guoqing Liu; Qicheng Wang
Venue: IJCAI 2025 (main)

Abstract: The evolution of point cloud processing algorithms necessitates an accurate assessment for their quality. Previous works consistently regard point cloud quality assessment (PCQA) as a MOS regression problem and devise a deterministic mapping, ignoring the stochasticity in generating MOS from subjective tests. This work presents the first probabilistic architecture for no-reference PCQA, motivated by the labeling process of existing datasets. The proposed method can model the quality judging stochasticity of subjects through a tailored conditional variational autoencoder (CVAE) and produces multiple intermediate quality ratings. These intermediate ratings simulate the judgments from different subjects and are then integrated into an accurate quality prediction, mimicking the generation process of a ground truth MOS. Specifically, our method incorporates a Prior Module, a Posterior Module, and a Quality Rating Generator, where the former two modules are introduced to model the judging stochasticity in subjective tests, while the latter is developed to generate diverse quality ratings. Extensive experiments indicate that our approach outperforms previous cutting-edge methods by a large margin and exhibits gratifying crossdataset robustness. Codes are available at https://git.openi.org.cn/OpenPointCloud/nrpcqa.
Constrained Preferential Bayesian Optimization and Its Application in Banner Ad Design
Authors: Koki Iwai; Yusuke Kumagae; Yuki Koyama; Masahiro Hamasaki; Masataka Goto
Venue: IJCAI 2025 (main)

Abstract: Preferential Bayesian optimization (PBO) is a variant of Bayesian optimization that observes relative preferences (e.g., pairwise comparisons) instead of direct objective values, making it especially suitable for human-in-the-loop scenarios. However, real-world optimization tasks often involve inequality constraints, which existing PBO methods have not yet addressed. To fill this gap, we propose constrained preferential Bayesian optimization (CPBO), an extension of PBO that incorporates inequality constraints for the first time. Specifically, we present a novel acquisition function for this purpose. Our technical evaluation shows that our CPBO method successfully identifies optimal solutions by focusing on exploring feasible regions. As a practical application, we also present a designer-in-the-loop system for banner ad design using CPBO, where the objective is the designer's subjective preference, and the constraint ensures a target predicted click-through rate. We conducted a user study with professional ad designers, demonstrating the potential benefits of our approach in guiding creative design under real-world constraints.