This paper studies the problem of minimizing group-level inequity in facility location games on the real line, where agents belong to different groups and may act strategically. We explore a fairness-oriented objective that minimizes the maximum group effect. For each group, the group effect is defined as its total or maximum distance to the nearest facility, weighted by group-specific factors. We show that this formulation generalizes several prominent optimization objectives, including the classical utilitarian (social cost) and egalitarian (maximum cost) objectives, as well as two group-fair objectives, maximum total and average group cost. In order to minimize the maximum group effect, we first propose two novel mechanisms for the single-facility case, the Balanced mechanism and the Major-Phantom mechanism. Both are strategyproof and achieve tight approximation guarantees under distinct formulations of the maximum group effect objective. Our mechanisms not only close the existing gap in approximation bounds for the group-fairness objectives, maximum total group cost and maximum average group cost, but also unify many classical truthful mechanisms within a broader fairness-aware framework. For the two-facility case, we revisit and extend the classical endpoint mechanism to our generalized setting and demonstrate that it provides tight bounds for two distinct maximum group effect objectives.

We study the approval-based multi-winner election problem where \(n\) voters jointly decide a committee of \(k\) winners from \(m\) candidates. We focus on the axiom average justified representation (AJR) proposed by Fernández, Elkind, Lackner, García, Arias-Fisteus, Basanta-Val, and Skowron (2017). AJR postulates that every group of voters with a common preference should be sufficiently represented in that their average satisfaction should be no less than their Hare quota. Formally, for every group of \(\lceil \ell \cdot \tfrac{n}{k} \rceil\) voters with \(\ell\) common approved candidates, the average number of approved winners for this group should be at least \(\ell\). It is well-known that a winning committee satisfying AJR is not guaranteed to exist for all multi-winner election instances. In this paper, we study the likelihood of the existence of AJR under the Erdos–Rényi model. We consider the Erdos–Rényi model parameterized by \(p \in [0,1]\) that samples multi-winner election instances from the distribution where each voter approves each candidate with probability \(p\) (and the events that voters approve candidates are independent), and we provide a clean and complete characterization of the existence of AJR committees in the case where \(m\) is a constant and \(n\) tends to infinity. We show that there are two phase transition points \(p_1\) and \(p_2\) (with \(p_1 \le p_2\)) for the parameter \(p\) such that: 1) when \(p \lt p_1\) or \(p \gt p_2\), an AJR committee exists with probability \(1 - o(1)\), 2) when \(p_1 \lt p \lt p_2\), an AJR committee exists with probability \(o(1)\), and 3) when \(p = p_1\) or \(p = p_2\), the probability that an AJR committee exists is bounded away from both \(0\) and \(1\).

The augmentation of algorithms with predictions of the optimal solution, such as from a machine-learning algorithm, has garnered significant attention in recent years, particularly in facility location problems. Moving beyond the traditional focus on utilitarian and egalitarian objectives, we design learning-augmented facility location mechanisms for the envy ratio objective, a fairness metric defined as the maximum ratio between the utilities of any two agents. For the deterministic setting, we propose a mechanism which utilizes predictions to achieve $\alpha$-consistency and $\frac{\alpha}{\alpha - 1}$-robustness for a selected parameter $\alpha \in [1,2]$, and prove its optimality. We also resolve open questions raised by Ding et al. [2020], devising a randomized mechanism without predictions to improve upon the best-known approximation ratio from $2$ to $1.8944$. Building upon these advancements, we construct a novel randomized mechanism which incorporates predictions to achieve improved performance guarantees.

We study the facility location problems (FLPs) with altruistic agents who act to benefit others in their affiliated groups. Our aim is to design mechanisms that elicit true locations from the agents in different overlapping groups and place a facility to serve agents to approximately optimize a given objective based on agents' costs to the facility. Existing studies of FLPs consider myopic agents who aim to minimize their own costs to the facility. We mainly consider altruistic agents with well-motivated group costs that are defined over costs incurred by all agents in their groups. Accordingly, we define Pareto strategyproofness to account for altruistic agents and their multiple group memberships with incomparable group costs. We consider mechanisms satisfying this strategyproofness under various combinations of the planner's objectives and agents' group costs. For each of these settings, we provide upper and lower bounds of approximation ratios of the mechanisms satisfying Pareto strategyproofness.

We initiate the study of fair allocation with the set of divisible or indivisible items distributed in multiple regions. The key requirement is that each agent can only obtain items from one region. In this work, we consider two kinds of fairness concepts: envy-based notions including envy-freeness (EF) and envy-freeness up to one/any item (EF1/EFX), and share-based notions including proportionality (PROP) and proportionality up to one/any item (PROP1/PROPX). On the negative side, we show NP-hardness and inapproximability results about the aforementioned fairness notions. On the positive side, we propose several algorithms to compute the partial allocations that satisfy envy-based notions and allocations that approximate the above fairness notions.

We study the facility location problems where agents are located on a real line and divided into groups based on criteria such as ethnicity or age. Our aim is to design mechanisms to locate a facility to approximately minimize the costs of groups of agents to the facility fairly while eliciting the agents' locations truthfully. We first explore various well-motivated group fairness cost objectives for the problems and show that many natural objectives have an unbounded approximation ratio. We then consider minimizing the maximum total group cost and minimizing the average group cost objectives. For these objectives, we show that existing classical mechanisms (e.g., median) and new group-based mechanisms provide bounded approximation ratios, where the group-based mechanisms can achieve better ratios. We also provide lower bounds for both objectives. To measure fairness between groups and within each group, we study a new notion of intergroup and intragroup fairness (IIF) . We consider two IIF objectives and provide mechanisms with tight approximation ratios.