Credit Fairness: Online Fairness In Shared Resource Pools

Seyed Majid Zahedi, Rupert Freeman · 2026

Read Credit Fairness: Online Fairness In Shared Resource Pools by Seyed Majid Zahedi, Rupert Freeman (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-17944.txt.

Introduction

Seyed Majid Zahedi and Rupert Freeman study fair shares when a group splits a resource over time. Their 2026 preprint sets a clean scene. Agents share a pool that must be split in each round. Each agent's need changes from round to round. Each unit given pays off at a flat rate up to the agent's need, and extra units pay nothing. The question is how to share so that credit and fairness line up over time.

One-round fairness can starve an agent who was quiet early and needy later. The authors build a credit view of fairness for this shared pool. Their frame weighs what each agent has banked or is owed. The problem shows up in cloud quotas, power grids, and shared budgets.

Catalog record

CREATORSeyed Majid Zahedi, Rupert Freeman
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-17944

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Credit Fairness: Online Fairness In Shared Resource Pools Seyed Majid Zahedi, Rupert Freeman Abstract . We consider a setting in which a group of agents share resources that must be allocated among them in each discrete time period. Agents have time-varying demands and derive constant marginal utility from each unit of resource received up to their demand, with zero utility for any additional resources. In this setting, it is known that independently maximizing the minimum utility in each round satisfies sharing incentives (agents weakly prefer participating in the mechanism to not participating), strategyproofness (agents have no incentive to misreport their demands), and Pareto efficiency ( 9 ) . However, recent work ( 19 ) has shown that this max–min mechanism can lead to large disparities in the total resources received by agents, even when they have the same average demand. In this paper, we introduce credit fairness , a strengthening of sharing incentives that ensures agents who lend resources in early rounds are able to recoup them in later rounds. Credit fairness can be achieved in conjunction with either Pareto efficiency or strategyproofness, but not both. We propose a mechanism that is credit fair and Pareto efficient, and we evaluate its performance in a computational resource-sharing setting. 1. Introduction In this paper, we consider a set of agents who contribute resources to a shared pool of homogeneous resources. Each agent owns a fixed endowment but faces time-varying demands. In such settings, pooling resources naturally increases utilization by accommodating agent-level demand spikes ( 14 ) . Our primary motivation is the sharing of computing resources ( 10 ; 17 ) , such as supercomputers for scientific computing, network bandwidth, and datacenters for internet services. More broadly, our model accommodates a wide range of applications, including shared energy systems (e.g., microgrids), transportation infrastructure (e.g., airport runways), research infrastructure (e.g., telescopes), and organizational resources shared across departments or units within a company. In all of these settings, several requirements naturally arise as fundamental to system stability and success. Pareto efficiency (PE) requires that it be impossible to make some agent better off without making another agent worse off, and is essential for any system whose central goal is maximizing resource utilization. Sharing incentives (SI) requires that agents prefer participating in the shared system over relying solely on their own resources in every round. SI serves as both a fairness property and a stability guarantee: without SI, systems risk collapse as agents opt out. Finally, strategyproofness (SP) requires that agents maximize their utility by truthfully reporting their demands to the system. Because system performance can only be optimized with respect to reported demands, any discrepancy between reports and true demands can jeopardize efficiency. While SI is a compelling property, 19 point out that system fairness may fail even for mechanisms that satisfy SI. Focusing on resource utilization, they observe that the classic static max-min fairness (SMMF) mechanism—which lexicographically maximizes the minimum utility in every round—can lead to large disparities in agent utilities, despite satisfying all three desirable properties discussed above. Intuitively, this occurs because SMMF is memoryless and therefore does not prioritize agents who contributed resources to others in earlier rounds. As a result, agents may lend resources to the system without ever being repaid. To address this issue, 19 propose Karma , which guarantees each agent a fraction \alpha of their contributed resources in each round and allocates the remaining resources by prioritizing agents with low cumulative allocations. Our goal in this work is to formally capture, via an axiomatic property, the sense in which SMMF is unfair. To this end, we introduce credit fairness . Intuitively, credit fairness posits the existence of an accounting framework (a “credit system”) that tracks lending and borrowing and ensures that agents who are net donors are not deprioritized in favor of agents who are net borrowers. Moreover, when combined with PE, credit fairness constitutes a strengthening of SI: it preserves the stability interpretation of SI while enhancing it from a fairness perspective. This strengthening, however, comes at a cost—we show that credit fairness is no longer jointly compatible with PE and SP, although any two of the three properties can be satisfied simultaneously. To our knowledge, all existing allocation mechanisms in this setting violate credit fairness, including Karma. We design a simple mechanism, LendRecoup , that is both credit fair and PE. Additionally, we show that LendRecoup is online strategyproof (OSP) ( 2 ) , a weaker notion of strategyproofness that assumes agents do not account for future rounds when strategizing. While this is a relatively weak incentive guarantee, it is, in some sense, the strongest one can hope for, as our impossibility result rules out full SP. Table 1 summarizes the properties satisfied by existing mechanisms. 1 1 1 Note that DMMF corresponds to Karma with parameter \alpha=0 . For Karma with 0<\alpha<1 , we report “Yes” when the property holds for all values of \alpha and “No” when there exists some \alpha for which the property is violated. Since no formal theoretical analysis exists for Karma with \alpha>0 , we report only properties that are straightforward to verify without proof; whether Karma satisfies OSP remains an open question. Finally, using data from a real-world computational resource-sharing setting, we demonstrate that the performance of LendRecoup is comparable to or better than that of other mechanisms across a range of fairness and efficiency metrics. Combined with the formal guarantee of credit fairness, these results suggest that LendRecoup is a compelling candidate for practical deployment. Mechanism PE SP OSP SI Credit Fair SMMF Yes Yes Yes Yes No DMMF Yes No Yes No No Karma ( \alpha\in(0,1)) Yes No ? No No Karma ( \alpha=1 ) Yes No ? Yes No LendRecoup Yes No Yes Yes Yes Table 1 . Summary of properties satisfied by static max-min fairness, dynamic max-min fairness, Karma, and LendRecoup . 2. Related Work In recent years, there has been renewed interest in repeated allocation mechanisms in dynamic settings where agents have time-varying demands ( 9 ; 12 ; 15 ; 18 ; 19 ; 7 ; 8 ; 6 ) . The work most closely related to ours is that of 9 , who study the online allocation of multiple resource units from a shared pool among agents who both contribute to and draw from the pool over multiple rounds. Agents are assumed to have piecewise-linear utilities that are high up to a demand and low beyond it. They consider two settings: (I) zero utility beyond demands and (II) strictly positive utility beyond demands. For (I), they analyze two max–min fair mechanisms: dynamic max–min fair (DMMF), which maximizes the minimum cumulative utility up to the current round, and static max–min fair (SMMF), which maximizes the minimum utility in the current round independently of previous rounds. They show that SMMF satisfies SP, SI, and PE, while DMMF violates SP and SI. For (II), they show that no online mechanism can satisfy PE along with either SI or SP. Another closely related work is that of 19 , who study setting (I) of 9 and propose Karma , an online mechanism parameterized by 0\leq\alpha\leq 1 , which specifies the fraction of each agent’s endowment

Read the complete text