CS Paper Radar

Weighted Fairness in Multi-User Earth Observation Satellite Scheduling

Maxime Lucet, Nawal Benabbou, Aurélie Beynier, Nicolas Maudet, Gauthier Picard

cs.GT cs.MA ·submitted 2026-10-25 13:25 UTC · v1

Abstract

As constellations of satellite grow in size, and become more costly, they are increasingly funded by multiple stakeholders who expect access to the constellation's resources that is commensurate with their investment. Such cooperation raises significant challenges for constellation operation, in particular regarding the fairness of the computed schedules among stakeholders. While several existing works deal with fairness in the Earth Observation Satellite Scheduling Problem (EOSSP), most of them assume that users (e.g. space agencies, research labs, countries) have the same weights, i.e. contributed equally to the project and therefore have equal access to the constellation. However, in practice, users' contributions often differ significantly. Hence, in this paper, we study a weighted variant of the EOSSP where users are assigned weights reflecting their respective contributions to the constellation. We propose several solution concepts with varying focus on efficiency and fairness, namely weighted utilitarianism, weighted egalitarianism, weighted leximin, and weighted ordered weighed averaging (WOWA). We formulate the related optimization problems as Mixed-Integer Linear Programs (MILPs), and compare them against two natural heuristics: weighted greedy and weighted round robin. All methods are evaluated on scenarios drawn from the literature, under strict runtime constraints, in order to assess the performance of each approach with respect to both efficiency and fairness metrics.

Closest papers

Nearest neighbours by meaning across the whole index.

STAR-GS: Truthful and Visibility-Aware Resource Scheduling for Ground Station as a Service

cs.NI cs.ETcs.GT ·2026-08-23 ·Zhiying Wang, Xiaojian Wang, Huayue Gu, Zhishan Guo, Ruozhou Yu
published similarity 0.63
Abstract · Accepted to IEEE ICNP 2026

The rapid growth of Low Earth Orbit satellite constellations has created increasing demand for efficient and scalable downlink services. Ground Station as a Service (GSaaS) provides an on-demand access model for satellite operators, but commercial GSaaS providers must schedule limited ground-station bandwidth among multiple satellites with heterogeneous data demands, overlapping visibility windows, strict deadlines, and strategic bidding behaviors. This paper studies GSaaS resource scheduling from a ground-station-centric perspective, where the provider jointly determines task admission, ground-station assignment, bandwidth allocation, and payments. Under satellite orbital dynamics, bandwidth constraints, and downlink task deadlines, maximizing the provider's revenue is NP-hard. To address this challenge, we propose STAR-GS, a truthful and feasibility-aware scheduling mechanism that combines bid-aware admission control, best-fit ground-station assignment, Earliest Deadline First (EDF)-based bandwidth scheduling, and critical-payment pricing. By integrating auction theory with schedulability analysis, STAR-GS incentivizes task owners to truthfully report their private valuations while ensuring that admitted tasks can be feasibly completed before their deadlines. Simulations using Ansys Systems Tool Kit (STK) show that STAR-GS consistently achieves higher revenue than heuristic baselines, obtains near-MILP performance with substantially lower runtime, and scales smoothly to workloads containing up to 900 tasks.

0.41

The AR Fairness Metamodel: A Structured Framework for Fairness Measures

cs.CY cs.AIcs.LOcs.MA+1 ·2026-09-16 ·Julian Alfredo Mendez, Timotheus Kampik
code/data similarity 0.57
Abstract

This paper presents the AR fairness metamodel, a framework designed to represent, analyze, and compare different fairness scenarios. The metamodel considers key elements, such as agents, resources, and their attributes, and enables the systematic definition and comparison of various fairness measures. We provide examples involving both discrete and continuous measures, including equality, equity, group fairness, individual fairness, the Gini index, the Theil index, Jain's fairness index, and a detailed fairness measure for Australia's Child Care Subsidy. We also explore relationships among group fairness, individual fairness, and envy-freeness, supported by formal proofs. At the conceptual modeling level, our approach builds on the Tiles framework, which offers modular components that can be connected to capture diverse fairness definitions. The goal is to make AR-based fairness definitions practical and adaptable across contexts, providing a clear way to define, compare, and evaluate them. An implementation of the Tiles framework is available as an open-source tool, and can support fairness modeling and evaluation across a wide range of applications.

0.22

Multi-Granularity Communication-Computing Resource Mapping for User Association in MEO-Assisted LEO Satellite Networks

cs.NI ·2026-11-08 ·Yi Jing, Chunxiao Jiang, Jiawei Wang, Jiachen Sun, Yafeng Zhan
similarity 0.55
Abstract

Low-Earth-orbit (LEO) satellite networks are evolving into spaceborne communication-computing infrastructures. Their user association must jointly account for the radio link and the CPU, GPU, NPU, memory, cache, storage, energy, queue, and thermal states that determine executable service capacity. This paper studies a MEO-assisted LEO architecture in which medium-Earth-orbit (MEO) regional state aggregators collect and relay time-stamped telemetry, the network operation control center (NOCC) maintains the global logical resource view and makes the final association decisions, and LEO satellites provide access and onboard execution. We develop a multigranularity representation and service-primitive-driven mapping that converts a service-level request into a target-LEO-dependent quantized resource vector. The integer formulation, exact mixed-integer linear programming (MILP) reference, and a capacity-aware primal-dual algorithm share the same mapped objective. Experiments use real-world service bandwidth traces, a 1584-satellite LEO shell, multiple traffic seeds, controlled load and mapping error, delayed telemetry, and temporal sessions. Relative to static mapping, the proposed method improves realized utility by 10.64% and lowers end-to-end outage by 5.70 percentage points. Target quantization reduces signaling by 19.84% with negligible utility loss. Additional load, delay, temporal, runtime, and exact-MILP audits delimit the operating region and remaining mapping uncertainty.

0.45

Maximin share allocations for two types of items

cs.GT ·2026-10-13 ·Yu Chen, Kai Jie Wong, Xiaorui Zhang
published similarity 0.55
Abstract · A preliminary version was presented at the Fourth IJCAI Workshop on Computational Fair Division [Aug 2026]

We study the fair allocation of indivisible items among $n$ agents with additive valuations (or costs) using the fairness notion of maximin share (MMS). Since MMS allocations do not always exist when $n > 2$, one direction in the literature has been to identify special classes of instances in which exact MMS allocations can be guaranteed. We show that, when items can be divided into two types of chores, MMS allocations always exist and can be computed in polynomial time using a novel geometric approach inspired by prior work in job scheduling. We further discuss how our technique extends to instances with two types of goods, as well as mixed instances consisting of one type of objective good and one type of objective chore.

0.16

Reinforcement Learning-Guided Evolutionary Policy Optimization for Preference-Adjustable Heterogeneous Agile Earth Observation Satellite Scheduling

cs.AI ·2026-08-25 ·He Wang, Junyu Wu, Hui Li, Yanjie Song, Witold Pedrycz +1 more
published similarity 0.55
Abstract · Published in IEEE Transactions on Geoscience and Remote Sensing

Heterogeneous agile Earth observation satellite (AEOS) scheduling requires task selection, satellite assignment, and observation sequencing under satellite-dependent visibility windows, attitude maneuvering requirements, energy consumption, and onboard storage constraints. Since satellites differ in orbital access, maneuvering capability, and payload resources, the same task may have different feasible windows, transition costs, and resource-consumption patterns on different platforms, which increases the difficulty of unified modeling and efficient optimization. To address this problem, this paper proposes an evolutionary policy optimization framework for heterogeneous AEOS scheduling with preference-adjustable weighted objectives. In the modeling layer, assignment-based indirect encoding is combined with decoder-based equivalent-cost evaluation to retain satellite-dependent constraints while integrating task gain, energy saving, and load balance into an interpretable scalar utility. In the optimization layer, schedule decoding, population-based search, and online actor-critic operator control are decoupled, so that reinforcement learning selects high-level search operators rather than constructing schedules directly. Based on this framework, a reinforcement-learning-assisted operator-selection memetic evolutionary algorithm (RLOSMEA) is developed to coordinate global exploration, feasibility recovery, and local refinement under a limited function-evaluation budget. Experiments on different heterogeneous AEOS scenarios show that RLOSMEA achieves higher overall weighted utility and more stable convergence than representative metaheuristic baselines. Sensitivity and learning-behavior analyses further confirm the robustness of the proposed method and the effectiveness of reinforcement-learning-guided operator selection.

0.46

Risk-Aware Handover Management Approach for Non-Terrestrial Networks with the NTN-Connect Simulator

eess.SP ·2026-11-16 ·Mohammed Almekhlafi, Antoine Lesage-Landry, Gunes Karabulut Kurt
similarity 0.55
Abstract

The continuous movement of low Earth orbit (LEO) satellites in non-terrestrial networks (NTNs) leads to frequent handovers, requiring joint optimization of visibility duration, transmit power, and user quality-of-service (QoS). This work address this issue by proposing a risk-aware handover management framework that minimizes transmit power and maximizes admitted users under per-satellite power budgets and user-rate chance constraints, while a preference score term penalizes short duration associations. We decompose the resulting mixed-integer nonlinear program (MINLP) into an inner power allocation subproblem and an outer generalized assignment association subproblem. The inner subproblem reformulates the chance constraint into its deterministic counterpart using the value-at-risk (VaR) closed-form. The obtained transmit power allocation is then used in the association subproblem, which is solved optimally using an off-the-shelf solver. Finally, we employ the polynomial-complexity Hungarian algorithm to solve the relaxed assignment problem and enforce the per-satellite power budget using a knapsack algorithm. Simulations, using the proposed NTN-Connect simulator, on the OneWeb and Starlink constellations show that the proposed low-complexity solution achieves near-optimal performance and better performance compared to the risk-aware maximum stay (RA-MST) and risk-aware maximum received signal received power (RA-MRSRP) baselines. On the Starlink constellation, it increases the inter-handover interval (IHI) from $0.37$ to $1.47$~min, reducing the handover rate by $75\%$. At a maximum-IHI operating point, it reduces the total transmit power by 1.1 dBW (22\%) while increasing the admission rate from 97.4\% to 99.3\%.

0.26

Revisiting EFX and fPO Allocations for Binary Chores

cs.GT ·2026-09-12 ·Zehan Lin, Xiaowei Wu, Shengwei Zhou
similarity 0.53
Abstract · 28 pages, no figure

We study fair and efficient allocations of indivisible chores under binary additive costs, with a focus on unequal entitlements and best-of-both-worlds guarantees. While binary valuations have been extensively studied for goods, their chore counterpart remains much less understood. A notable exception is due to Tao et al. (TCS 2025), who established that EFX and fPO are compatible for binary chores with equal entitlements. We revisit binary chores under unequal entitlements and establish the computation of allocations that satisfy WEFX and fPO. Our key technical contribution is a new lexicographic potential function tailored to chores: any allocation minimizing this potential ensures both WEFX and fPO. This potential further guides a polynomial-time local-search algorithm for computing allocations with such fairness and efficiency guarantees. For best-of-both-worlds guarantees, we show that unequal entitlements create a sharp obstruction: even with two agents and identical binary additive costs, no lottery can simultaneously satisfy ex-ante WEF and ex-post WEF1. In contrast, for equal entitlements, we construct in polynomial time a lottery that is ex-ante EF and fPO, while every realization is both EFX and fPO.

0.41

Sequential Contract Design for Budgeted Crowdsourcing

cs.GT ·2026-11-19 ·Michal Feldman, Vasilis Gkatzelis, Shaul Rosner, Inbal Talgam-Cohen
benchmark similarity 0.53
Abstract · 37 pages

A principal wishes to crowdsource a collection of tasks under a fixed compensation budget. The quality of a task's outcome is stochastic and depends on the worker's effort level. Since this effort is unobservable, the principal offers contracts to workers specifying their compensation for each possible outcome. The principal offers these contracts sequentially, using previously observed outcomes and payments to decide whom to approach next and what contract to offer. The objective is to maximize the expected value of the work produced while ensuring that total payments never exceed the budget, regardless of the realized outcomes. Contract design must therefore account both for a worker's incentives and for the budget available to incentivize others. For valuations that are additive across tasks, we characterize how the approximability of the optimal adaptive policy depends on the numbers of workers, effort levels, and outcomes. Polynomial-time constant-factor approximation is possible whenever the number of workers, effort levels per worker, or outcomes per task is constant, but impossible in general when all three are unrestricted, unless $P=NP$. We obtain tight guarantees for every fixed number of workers, establish computational hardness even in restricted settings, and obtain exact algorithms and approximation schemes in more structured settings. We also investigate simple contract structures, demonstrating both the benefits of adapting contracts to previous outcomes and the limitations of local contract rules, while identifying conditions under which a local policy achieves a constant-factor guarantee. Finally, we extend our analysis beyond additive valuations, obtaining constant-factor approximations for monotone submodular valuations with binary outcomes, including guarantees against a stronger full-knowledge benchmark under additional assumptions.

0.27