This paper investigates the problem of shared resource allocation, where a set of agents must be assigned to heterogeneous resources, with each agent allocated exactly one resource and each resource potentially shared by multiple agents. An agent’s utility for a given resource is jointly determined by the resource's type and the number of agents sharing it. We focus on two fundamental classes of monotone valuations: monotone nondecreasing and monotone nonincreasing, where an agent’s utility respectively increases or decreases with the number of agents sharing the resource. Within this shared resource framework, we examine classical notions of fairness and stability, including maximin-share fairness, envy-freeness, Nash stability, and two epistemic relaxations—epistemic envy-freeness and epistemic Nash stability—as well as swap stability. We propose formal definitions adapted to this setting and systematically analyze the relationships among these concepts. The primary contributions of this work consist of establishing existence and computational complexity results for each notion under both monotonicity assumptions and developing polynomial-time algorithms in cases where fair or stable allocations are guaranteed to exist.

This paper studies the design of strategyproof distributed mechanisms for a constrained location problem involving two heterogeneous facilities under the max-variant cost model. A set of agents with private locations on the real line is partitioned into disjoint groups, and the two facilities must be placed at locations drawn from a given multiset of candidate locations, with each candidate location hosting at most one facility. Each agent requires access to both facilities, and her individual cost is defined as the distance from her location to the farther facility. Each such mechanism operates in two stages. First, it selects a pair of candidate locations as representatives for each group based solely on the reports of that group's members. It then selects the final locations of the two facilities from the aggregated multiset of group representatives. We investigate deterministic strategyproof mechanisms within this distributed framework and derive constant lower and upper bounds on their distortion with respect to four social objectives: the Average-of-Average, Max-of-Max, Max-of-Average, and Average-of-Max costs.

In this paper, we study a fair resource scheduling problem involving the assignment of a set of interval jobs among a group of heterogeneous machines. Each job is associated with a release time, a deadline, and a processing time. A machine can process a job if the entire processing period falls within the release time and deadline of the job. Each machine can process at most one job at any given time, and different jobs yield different utilities for the machines. The goal is to find a fair and efficient schedule of the jobs. We discuss the compatibility between envy-freeness up to any item (EFX) and various efficiency concepts. Additionally, we present polynomial-time algorithms for various settings.

The widespread and effective online social networks may cause misinformation to diffuse in the networks, which could lead to public panic and even serious economic consequences. The classical misinformation containment (MC) problem aims to select a small node set as positive seeds to compete against the misinformation and limit the influence of misinformation as much as possible, where the misinformation seed set is given. Most of the prior works concentrate on either minimizing the number of users infected by misinformation or maximizing the number of users protected by the positive cascade. That is, they only concentrate on optimizing the number of nodes. However, the interaction effects between nodes differ from user to user and the related profit obtained from interaction activities may also be different. This article proposes a novel problem, called profit minimization of misinformation (PMM), which is the first to analyze the profit of activity in the MC problem. Given a misinformation seed set, the PMM problem aims at selecting a node set satisfying the cardinality constraint to minimize the profit of edges starting from infected nodes but ending at infected or protected nodes. Based on the sandwich method, we design a data-dependent approximation scheme for the PMM problem. We approximate the upper and lower bounds of the objective in the equivalent problem by the reverse influence sampling technique. Our algorithm is verified on realistic data sets, which demonstrate the superiority of our method.