Two-sided matching, such as student-school assignments, is widely studied but suffers from a fundamental conflict between efficiency and fairness. Notably, Pareto efficiency and justified-envy-freeness are incompatible even in simple one-to-one matchings like the stable marriage problem. Prior research has improved efficiency by relaxing fairness, often tolerating student envy. This study takes a different approach by focusing on envy that students perceive more strongly—specifically, envy toward acquaintances. We model student relationships as an undirected graph and define local envy as justified envy toward a neighbor. A matching without such envy satisfies local envy-freeness, a relaxed fairness concept. We investigate whether Pareto-efficient matchings can co-exist with local envy-freeness by imposing structure on the graph and school preferences. To explore this, we introduce a local version of Cho et al.’s (AAMAS 2024) parameterized fairness, which quantifies levels of local envy-freeness. We then analyze the achievable levels under Pareto-efficient mechanisms for graphs that are “close” to trees and single-peaked preferences on the graph.

Abstract The theory of two-sided matching has been extensively developed and applied to many real-life application domains. As the theory has been applied to increasingly diverse types of environments, researchers and practitioners have encountered various forms of distributional constraints. Arguably, the most general class of distributional constraints would be hereditary constraints; if a matching is feasible, then any matching that assigns weakly fewer students at each college is also feasible. However, under general hereditary constraints, it is shown that no strategyproof mechanism exists that simultaneously satisfies fairness and weak nonwastefulness, which is an efficiency (students’ welfare) requirement weaker than nonwastefulness. We propose a new strategyproof mechanism that works for hereditary constraints called the Multi-Stage Generalized Deferred Acceptance mechanism (MS-GDA). It uses the Generalized Deferred Acceptance mechanism (GDA) as a subroutine, which works when distributional constraints belong to a well-behaved class called hereditary M $$^{\natural }$$ -convex set. We show that GDA satisfies several desirable properties, most of which are also preserved in MS-GDA. We experimentally show that MS-GDA strikes a good balance between fairness and efficiency (students’ welfare) compared to existing strategyproof mechanisms when distributional constraints are close to an M $$^{\natural }$$ -convex set * .

Consider a graph G where each vertex has a threshold. A vertex v in G is activated if the number of active vertices adjacent to v is at least as many as its threshold. A vertex subset A 0 of G is a target set if eventually all vertices in G are activated by initially activating vertices of A 0 . The Target Set Selection problem ( TSS ) involves finding a smallest target set of G . This problem has already been extensively studied and is known to be NP-hard even for very restricted conditions. In this paper, we analyze TSS and its weighted variant, called the Weighted Target Set Selection problem ( WTSS ), from the perspective of parameterized complexity. Let k be the solution size and let ℓ be the maximum threshold. We first show that TSS is W[1]-hard for split graphs when parameterized by k + ℓ , and W[2]-hard for cographs when parameterized by k . We next prove that WTSS is W[2]-hard for trivially perfect graphs when parameterized by k . On the other hand, we show that WTSS can be solved in O ( n log ⁡ n ) time for complete graphs with n vertices. Additionally, we design FPT algorithms for WTSS when parameterized by nd + ℓ , tw + ℓ , ce , and vc , where nd , tw , ce , and vc are the neighborhood diversity, the treewidth, the cluster editing number, and the vertex cover number of the input graph, respectively.

Facility location games provide an abstract model of mechanism design. In such games, a mechanism takes a profile of n single-peaked preferences over an interval as an input and determines the location of a facility on the interval. In this paper, we restrict our attention to distance-based single-peaked preferences and focus on a well-known class of parameterized mechanisms called ordered weighted average methods, which is proposed by Yager [38] and contains several practical implementations such as the standard average and the Olympic average. We comprehensively analyze their performance in terms of both incentives and fairness. More specifically, we provide necessary and sufficient conditions on their parameters to achieve strategy-proofness, non-obvious manipulability, individual fair share, and proportional fairness, respectively.

Linear programming (LP) problems with gainfree Leontief substitution systems have been intensively studied in economics and operations research, and include the feasibility problem of a class of Horn systems, which arises in, e.g., polyhedral combinatorics and logic. This subclass of LP problems admits a strongly polynomial time algorithm, where devising such an algorithm for general LP problems is one of the major theoretical open questions in mathematical optimization and computer science. Recently, much attention has been paid to devising certifying algorithms in software engineering, since those algorithms enable one to confirm the correctness of outputs of programs with simple computations. In this paper, we provide the first combinatorial (and strongly polynomial time) certifying algorithm for LP problems with gainfree Leontief substitution systems. As a by-product, we answer affirmatively an open question whether the feasibility problem of the class of Horn systems admits a combinatorial certifying algorithm.

In this paper, we study several classes of satisfiability preserving assignments to the constraint satisfaction problem. In particular, we consider fixable, autark and satisfying assignments. Since it is in general NP-hard to find a nontrivial (i.e., nonempty) satisfiability preserving assignment, we introduce linear satisfiability preserving assignments, which are defined by polyhedral cones in an associated vector space. The vector space is obtained by the identification, introduced by Kullmann, of assignments with real vectors. We consider arbitrary polyhedral cones, where only restricted classes of cones for autark assignments are considered in the literature. We reveal that cones in certain classes are maximal as a convex subset of the set of the associated vectors, which can be regarded as extensions of Kullmann's results for autark assignments of CNFs. As algorithmic results, we present a pseudo-polynomial time algorithm that computes a linear fixable assignment for a given integer linear system, which implies the well known pseudo-polynomial solvability for integer linear systems such as two-variable-per-inequality, Horn and q-Horn systems.

In this paper, we study several classes of satisfiability preserving assignments to the constraint satisfaction problem (CSP). In particular, we consider fixable, autark and satisfying assignments. Since it is in general NP-hard to find a nontrivial (i.e., nonempty) satisfiability preserving assignment, we introduce linear satisfiability preserving assignments, which are defined by polyhedral cones in an associated vector space. The vector space is obtained by the identification, introduced by Kullmann, of assignments with real vectors. We consider arbitrary polyhedral cones, where only restricted classes of cones for autark assignments are considered in the literature. We reveal that cones in certain classes are maximal as a convex subset of the set of the associated vectors, which can be regarded as extensions of Kullmann's results for autark assignments of CNFs. As algorithmic results, we present a pseudo-polynomial time algorithm that computes a linear fixable assignment for a given integer linear system, which implies the well known pseudo-polynomial solvability for integer linear systems such as two-variable-per-inequality (TVPI), Horn and q-Horn systems.

This paper studies optimal matroid partitioning problems for various objective functions. In the problem, we are given a finite set $E$ and $k$ weighted matroids $(E, \mathcal{I}_i, w_i)$, $i = 1, \dots, k$, and our task is to find a minimum partition $(I_1,\dots,I_k)$ of $E$ such that $I_i \in \mathcal{I}_i$ for all $i$. For each objective function, we give a polynomial-time algorithm or prove NP-hardness. In particular, for the case when the given weighted matroids are identical and the objective function is the sum of the maximum weight in each set (i.e., $\sum_{i=1}^k\max_{e\in I_i}w_i(e)$), we show that the problem is strongly NP-hard but admits a PTAS.

Scheduling sensors to prolong the lifetime of covering targets in the field is one of the central problems in wireless sensor networks. This problem, called the maximum lifetime coverage problem (MLCP), can be formulated as a linear programming problem with exponential size, and has a constant-factor approximation algorithm. In reality, however, batteries of sensors have recovery effects, which is a phenomenon that the deliverable energy in batteries can be replenished by itself if it is left idling for sufficient duration. Thanks to that effects, we can obtain much longer lifetime of sensors if each sensor is forced to take a sleep at some interval. In this paper, we introduce two models that extend the MLCP, incorporating battery recovery effects. The first model represents battery recovery effects in a deterministic way, while the second one uses a probabilistic model to imitate the effects. We then propose efficient algorithms that work for both models by extending approximation algorithms for the original MLCP. Numerical experiments show that the lifetime of our schedule is 10–40% longer than one without battery recovery effects.

In this paper, we consider solving the integer linear systems, i.e., given a matrix A in R^{m*n}, a vector b in R^m, and a positive integer d, to compute an integer vector x in D^n such that Ax <= b, where m and n denote positive integers, R denotes the set of reals, and D={0,1,..., d-1}. The problem is one of the most fundamental NP-hard problems in computer science. For the problem, we propose a complexity index h which is based only on the sign pattern of A. For a real r, let ILS_=(r) denote the family of the problem instances I with h(I)=r. We then show the following trichotomy: - ILS_=(r) is linearly solvable, if r < 1, - ILS_=(r) is weakly NP-hard and pseudo-polynomially solvable, if r = 1, and - ILS_=(r) is strongly NP-hard, if r > 1. This, for example, includes the existing results that quadratic systems and Horn systems can be solved in pseudo-polynomial time.