Credit Fairness: Online Fairness in Shared Resource Pools

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 (Kelly et al., 1998).

Our primary motivation is the sharing of computing resources (Ghodsi et al.; Stoica et al., 2011; 2003), 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, Vuppalapati et al. (2023) 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 aforementioned properties. 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, Vuppalapati et al. (2023) propose Karma, which guarantees agents a fraction α of their endowments 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 comes at a cost: under anonymity, credit fairness is incompatible with simultaneously satisfying PE and SP.

To our knowledge, all existing 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) (Aleksandrov and Walsh, 2019b), which assumes that agents do not account for future rounds when strategizing. While this is a relatively weak 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

Finally, using data from a real-world environment, we show that LENDRECOUP's performance 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.

2 RelatedWork

In recent years, there has been renewed interest in repeated allocation mechanisms in dynamic settings where agents have time-varying demands (Freeman et al.; Hossain; Li et al.; Vardi et al.; Vuppalapati et al.; Fikioris et al.; Fikioris et al.; Cookson et al., 2018; 2019; 2021; 2022; 2023; 2024; 2025; 2025). The work most closely related to ours is that of Freeman et al. (2018), 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 lexicographically maximizes the minimum cumulative utility up to the current round, and static max-min fair (SMMF), which lexicographically maximizes the minimum utility in the current round. 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 Vuppalapati et al. (2023), who study setting (I) of Freeman et al. (2018) and propose Karma, a mechanism parameterized by 0 ≤ α ≤ 1, which specifies the fraction of each agent's endowment that is guaranteed when demanded. The remaining resources, together with donations from agents whose demand falls below their guaranteed share, are allocated to agents with excess demand by prioritizing those with the smallest cumulative allocations. Agents gain credits when others borrow their donated resources and lose credits when borrowing from the pool. They derive theoretical guarantees only for α = 0, in which case Karma reduces to DMMF, violating SP and SI.

1 Note that DMMF corresponds to Karma with parameter α = 0. For Karma with 0 < α < 1, we report "Yes" when the property holds for all values of α and "No" when there exists some α for which the property is violated. Since no formal theoretical analysis exists for Karma with α > 0, we report only properties that are straightforward to verify without proof; whether Karma satisfies OSP remains an open question.

Repeated allocation has also been studied in settings where indivisible items arrive over time and must be allocated immediately without revocation. Zeng and Psomas (2020) and Benad`e et al. (2024) study the trade-off between fairness and efficiency in this setting, while Aleksandrov and Walsh (2019a) examine online fair division under monotonicity constraints. Aleksandrov and Walsh (2019b) show that, for agents with additive utilities, SP, envy-freeness, and PE cannot be simultaneously achieved against worst-case adversaries. Benad`e et al. (2018) provide a deterministic algorithm with vanishing envy over time. Benad`e et al. (2022) study a partial information setting, where ordinal but not cardinal information is elicited and values are drawn from i.i.d. distributions. Finally, Igarashi et al. (2024) study the repeated allocation of indivisible goods and chores, providing guarantees on both per-round and cumulative fairness and efficiency.

3 Preliminaries

For k ∈ N, we denote [k] := {1, . . . , k}. Consider a system with n agents and discrete rounds t = 1, 2, . . .. (All definitions apply to any finite prefix of rounds.) At each round, each agent i contributes a fixed endowment of ei > 0 units, and the total endowment is E = ∑i ei. We denote by E-i = ∑j̸=i ej the total number of units not including i's endowment. We assume a dynamic setting in which agents have time-varying demands. At round t, agent i has a true demand of di,t ≥ 0 units and reports a demand of d′i,t ≥ 0. Let di,1:t = (di,t′ )1≤t′≤t and d′i,1:t = (d′i,t′ )1≤t′≤t denote the vectors of agent i's actual and reported demands up to round t, respectively. Further, let d′-i,1:t denote the reported demands of all agents other than i up to round t. At every round t, an online allocation mechanism M (henceforth simply mechanism) assigns each agent an allocation aMi,t (d′1,1:t , . . . , d′n,1:t ) = aMi,t (d′i,1:t , d′-i,1:t ) with ∑i aMi,t (d′i,1:t , d′-i,1:t ) ≤ E. We will typically write simply ai,t when the exact mechanism and the demands are clear from context. Let aMi,1:t (d′i,1:t , d′-i,1:t ) (often simply ai,1:t) denote the vector of agent i's allocations up to round t. Agents derive one unit of utility for every unit of resource they receive up to their demand and do not value additional units; that is, the utility of agent i with demand di,t at round t is ui,t(ai,t, di,t) = min(di,t, ai,t). We additionally assume that utilities are additive over rounds, so that agent i's total utility over the first t rounds for an allocation ai,1:t is Ui,t(ai,1:t, di,1:t) = ∑tt′=1 ui,t′ (ai,t′ , di,t′ ). For notational simplicity, we write ui,t(ai,t) or Ui,t(ai,1:t) when the dependence on di,t or di,1:t is clear. It will often be convenient to reason about an agent's utility with respect to their reported, rather than true, demand; for this purpose, we use the shorthand u′i,t (ai,t) = ui,t(ai,t, d′i,t ) and U ′ i,t (ai,1:t) = Ui,t(ai,1:t, d′i,1:t ). Although this quantity does not represent an agent's actual utility, it appears often because our definition of credit fairness will disregard incentive considerations and implicitly assume that reported demands equal true demands, as is standard for fairness properties.

Following prior work (Freeman et al., 2018), we allow the allocations ai,t to be real-valued even though resource units and demands are discrete. We interpret real-valued allocations as being implemented via randomization where agent i is allocated ai,t units in expectation.

Properties of Mechanisms. In addition to the new property that we will define later, we focus on three fundamental desiderata: Pareto efficiency (PE), sharing incentives (SI), and strategyproofness (SP). PE requires that if any agent receives fewer units than their demand, then all units must be allocated to agents who derive positive utility from them, i.e., the sum of agents' utilities equals E.

Definition 1. A mechanism M is Pareto efficient if, for every round t and every report profile (d′1,1:t , . . . , d′n,1:t ), the following holds: whenever there exists an agent i such that aMi,t (d′i,1:t , d′-i,1:t ) < d′i,t , then it must be the case that:

SI requires that agents receive at least as much utility from (truthfully) participating in the system as they would have received by not participating.

Definition 2. AmechanismM satisfies sharing incentives if, for every round t, every agent i, all true demands di,1:t, and any report profile d′-i,1:t of the other agents, it holds that:

where ei = (ei, . . . , ei) denotes the allocation in which agent i receives their endowment in every round.

SP requires that agents never benefit frommisreporting.

Definition 3. A mechanism M is strategy-proof if, for every agent i, every round t, all true demands di,1:t, all report profiles d′i,1:t of agent i, and any report profile d′-i,1:t of the other agents, it holds that:

Finally, online strategyproofness (OSP) (Aleksandrov and Walsh, 2019b) requires that, fixing reports of all agents in rounds 1, . . . , t-1, no agent can increase their utility in round t by misreporting.

Definition 4. A mechanism M is online strategy-proof if, for every agent i, every round t, all demands di,1:t, all report profiles d′i,1:t of agent i such that di,1:t-1 = d′i,1:t-1 , and any report profile d′-i,1:t of the other agents, it holds that:

4 Credit Fairness

It is known that SMMF satisfies PE, SI, and SP (Freeman et al., 2018). However, as Vuppalapati et al. (2023) note, SMMF can produce highly inequitable allocations in terms of the number of resources received-as large as a factor of Ω(n)-even between users with the same average demand. We illustrate this shortcoming with the following example, which is heavily inspired by Vuppalapati et al.'s proof of the aforementioned result.

Note that the total demand of all three agents is the same. Under SMMF, the resulting allocations are as follows:

Agents 1 and 2 each receive a utility of 4, while agent 3 receives a utility of 1.

Agent 3 could argue that, having lent their endowment to other agents in the first two rounds, they should have the right to reclaim those resources in round 3 when they need them. However, because SMMF is memoryless, it denies this possibility. In this section, we formally capture the undesirable behavior of SMMF in this example by introducing credit fairness, an axiomatic property that reflects the idea that agents should have priority over resources they previously lent.

4.1 Formal Definition

To define credit fairness, we require the notion of a credit system. A credit system (ci,t)i∈[n],t∈N is simply a balance of credits for every agent. We denote by ci,t ∈ R the number of credits that agent i has at the start of round t, and require that ci,1 = 0 for every agent i. Let ∆ci,t ≜ ci,t+1 - ci,t. Furthermore, for every agent i and round t, let A-i,t = AM-i,t (d′1,1:t , . . . , d′n,1:t ) ≜ ∑j̸=i ai,t denote the total round t allocation of agents other than i under mechanismM.

Definition 5. A mechanismM is credit fair if there exists a credit system (ci,t)i∈[n],t∈N for which the following properties hold for all agents i and rounds t:

Let us unpack this definition. Condition (CF1) states that agents who receive less than ei utility (informally, agents donating resources to the system) should not lose credits but may gain up to ei - u′i,t (ai,t). Likewise, agents who receive more than ei utility (informally, borrowers) should not gain credits but may lose up to u′i,t (ai,t) - ei. Agents whose utility equals their endowment neither gain nor lose credits. Although this condition does not require a one-to-one correspondence between credits and resources, it bounds how far credits can diverge from allocations. At a high level, it justifies interpreting positive credits as claims on resources and negative credits as obligations.

Condition (CF2) requires that if an agent i lends resources to others, i.e., the other agents collectively receive utility exceeding the resources they contribute, then agent i must gain at least one unit of credit for each such resource. This captures the idea that agents should be rewarded when they are pivotal to others receiving valued resources.

Condition (CF3) requires that the credit system be deflationary: the total number of credits cannot increase over time. Since credits represent claims on resources, allowing their total to grow would imply that agents could collectively obtain resources without anyone bearing a corresponding cost.

To understand condition (CF4), consider an agent with di,t > ei. If the agent has positive credits, they must receive at least their endowment ei. If the agent has negative credits, they are guaranteed only ei +ci,t. Intuitively, the systemmay reclaim from the agent up to the number of resources equal to the credit they owe.

Finally, condition (CF5) relies on the notion of a creditadjusted endowment, defined as ei + ci,t, which reflects both the agent's baseline endowment and whether they are a net borrower or lender. The condition requires that if some agent j receives strictly more than their credit-adjusted endowment in a round, then every other agent with sufficient demand must receive at least their own credit-adjusted endowment. Interpreting the credit-adjusted endowment as an agent's "fair share," this ensures that no agent receives more than their fair share while another receives strictly less.

In the full version of the paper (Zahedi and Freeman, 2026), we show that none of CF1-CF5 is implied by the remaining four conditions.

In summary, credit fairness establishes a memory-based system in which credits act as a ledger of past deviations from an agent's endowment: agents who receive less accumulate limited future claims, while those who receive more incur limited future obligations. Rather than guaranteeing a fixed minimum share, as adopted by mechanisms such as Karma, credit fairness enforces a dynamic notion of equity in which an agent's entitlement adapts to their credit balance. Agents with positive credits are guaranteed at least their endowment, while agents in debt have their guaranteed minimum reduced according to what they owe.

4.2 Properties

We begin with a useful lemma that characterizes credit updates for any credit-fair and Pareto-efficient mechanism in settings where resources are overdemanded. The proof of this lemma and all other omitted proofs appear in the full version of the paper (Zahedi and Freeman, 2026).

Lemma 1. Fix a round t with ∑j d′j,t ≥ E. Let M be a mechanism that is credit fair and Pareto efficient. Then, for every agent i ∈ [n], it holds that ∆ci,t = ei -ai,t.

We now show that, when combined with Pareto efficiency, credit fairness implies sharing incentives. The proof is omitted for space constraints, but the main idea is to show that if an agent receives less than their SI baseline utility u′i,t (ei)

in some round, then that agent must have nonpositive credits, even after the round-t allocations, i.e., ci,t+1 ≤ 0. This fact is sufficient to guarantee that the agent's cumulative utility still does not fall below their SI baseline.

Theorem1. LetM be a credit-fair and Pareto efficient mechanism. Then M satisfies sharing incentives.

As a corollary of Theorem 1, any Pareto efficient mechanism that violates sharing incentives cannot be credit fair. Since DMMF is Pareto efficient but violates sharing incentives, it follows that DMMF is not credit fair.

Corollary 1. The dynamic max-min fair mechanism violates credit fairness.

Furthermore, we show that SMMF, despite satisfying sharing incentives and Pareto efficiency, violates credit fairness, which further validates the necessity of our definition.

Proposition 1. The static max-min fair mechanism violates credit fairness.

To our knowledge, SMMF is the only known mechanism that satisfies SP, PE, and SI, yet it violates credit fairness. This naturally raises the question of whether there exists a mechanism that satisfies the stronger combination of SP, PE, and credit fairness. Our next result shows that the answer is no, at least under the mild restriction of anonymity. A mechanism is anonymous if permuting the agents results in the allocation being permuted in the same way; in other words, the mechanism does not depend on the identities of the agents. Whether anonymity can be removed from the following theorem is an open question.

Theorem 2. No mechanism is anonymous, strategyproof, credit fair, and Pareto efficient.

and the following credit balances:

Note that, given the demands and allocations, these credit balances are implied by Lemma 1.

The first-round allocations are implied by SI and PE. In the second round, SI requires that both agents 1 and 3 receive at least one unit, and (CF5) then requires that the additional unit be allocated to agent 3. The third- and fourth-round allocations are dictated by PE. Finally, the fifth-round allocation is implied by (CF5), which does not allow agent 2 to receive more than one unit unless agent 1 receives at least three.

Now suppose agent 1 instead reports a demand of 0 in the first round. In this case, the allocations must be:

with the following credits:

To verify the allocations, observe that the allocations in the first, third, and fourth rounds are required by PE, the secondround allocation follows from anonymity, and the fifth-round allocation is implied by (CF5). As a result of the misreport, agent 1's total utility increases by 0.5, from 4 to 4.5, demonstrating a profitable deviation. Therefore, M is not SP.

While SP, PE, and credit fairness cannot all be satisfied simultaneously by an anonymous mechanism, any two of them can. SMMF is SP and PE but not credit fair. The static mechanism that allocates each agent their endowment ai,t = ei at each round is SP and credit fair (SP is obvious; see [Zahedi and Freeman, 2026] for a proof of credit fairness). In the next section we will introduce a mechanism that is credit fair and PE.

5 LENDRECOUP Mechanism

We present a mechanism, LENDRECOUP, that is credit fair and PE. At each round, LENDRECOUP allocates resources by first satisfying demands as much as possible up to agents' credit-adjusted endowment max(0, ei +ci,t). If resources remain after every agent receives min(d′i,t ,max(0, ei + ci,t)), the surplus is distributed among agents with remaining demand, prioritizing agents with low cumulative allocations. If resources still remain after all agents receive their demands, then remaining resources are allocated to agents with low demand in the current round. Credits are updated in a one-toone correspondence with resource transfers: an agent gains (loses) one credit for each unit of resource lent to (borrowed from) the system.

To formally specify LENDRECOUP, we use the Proportional Sharing With Constraints (PSWC) procedure of Freeman et al. (2018). This procedure takes as input a total resource amount A, agent weights w, and agent-specific lower and upper bounds m (for "minimum") and l (for "limit"). It outputs per-agent allocations by finding a scalar x such that each agent i receives xwi units whenever mi ≤ xwi ≤ li; otherwise, agent i receives mi if xwi <mi, or li if xwi > li. The PSWC procedure can be implemented in O(n log n) time using the Divvy algorithm (Gulati et al., 2012).

Pseudocode for LENDRECOUP is given in Algorithm 1. To implement prioritization of agents with low cumulative allocations, we conceptually "reallocate" all resources from previous rounds using the PSWC procedure, with minimum allocations set to the allocations already made. This allows any

Algorithm 1 LENDRECOUP

remaining uncommitted resources at round t to be used to equalize cumulative allocations as much as possible.

with the following credit balances:

In all rounds the algorithm is in the shortage branch (Line 7). The critical round is t = 3, in which we have creditadjusted endowments ¯ d1,3 = ¯ d2,3 = 0 and ¯ d3,3 = 3, yielding ∑i ¯ di,t = 3 ≥ E = 3. Therefore, LENDRECOUP runs PSWC with minimum allocations 0 and maximum allocations ¯ dt, resulting in all 3 resources being allocated to agent 3.

LENDRECOUP is PE, since it never allocates resources that are not valued unless all demands are exhausted.

Proposition 2. LENDRECOUP is Pareto efficient.

We next show that LENDRECOUP is credit fair.

Theorem 3. LENDRECOUP satisfies credit fairness.

Proof. We examine the five conditions individually.

Condition (CF1) holds in the shortage case by the definition of the credit update and the fact that ai,t = u′i,t (ai,t) in this case; hence, ∆ci,t = ei - ai,t for all i. In the no-shortage case, the same argument applies to agents with ai,t = d′i,t . Otherwise, note that ai,t > d′i,t implies ai,t ≤ ei, since the PSWC call never reaches x > 1 (as x > 1 would allocate more than ei resources to every agent, violating the capacity constraint). For such agents, we have 0 ≤ ∆ci,t = ei-ai,t ≤ ei - u′i,t (ai,t).

Condition (CF2). Fix any agent i and round t. Observe that: ∑j̸=i u′j,t (aj,t) ≤ ∑j̸=i aj,t = ∑j aj,t - ai,t = E - ai,t. Rearranging and substituting ∆ci,t = ei - ai,t gives: ∑j̸=i u′j,t (aj,t) - E-i ≤ ei - ai,t = ∆ci,t.

Condition (CF4). Fix an agent i and round t. We consider the following two cases.

Case 1: ∑i d′i,t ≤ E. In this case, Algorithm 1 calls PSWC with minima m = d′t , which implies ai,t ≥ d′i,t ≥ min(d′i,t , ei +min(0, ci,t)), as required by (CF4).

Case 2: ∑i d′i,t > E. Define κi,t := max(0, ei +ci,t) so that ¯ di,t := min(d′i,t , κi,t). We consider two subcases.

Case 2a: E ≤ ∑j ¯ dj,t. The mechanism calls PSWC with weights w = e, minima m = 0, and upper limits l = ¯ dt. Without upper limits, PSWC would return the proportional allocation ai,t = ei (since A = E = ∑i ei). With the upper limits, PSWC can only reduce the allocation of agents whose proportional share exceeds their cap, and redistribute any leftover to agents whose cap exceeds their proportional share. In particular, we have ai,t ≥ min(ei, ¯ di,t) for all agents i. Now consider ci,t ≥ 0 and ci,t < 0 separately. If ci,t ≥ 0, then κi,t ≥ ei, hence ¯ di,t = min(d′i,t , κi,t) ≥ min(d′i,t , ei). Therefore, we have:

If ci,t < 0 and ei + ci,t < 0, the desired inequality holds trivially since allocations are nonnegative. If ci,t < 0 and ei + ci,t ≥ 0, then κi,t = ei + ci,t, and therefore ¯ di,t = min(d′i,t , ei + ci,t). This implies ¯ di,t ≤ ei, and hence min(ei, ¯ di,t) = ¯ di,t. As a result, we have:

Case 2b: E > ∑j ¯ dj,t. In this case, the mechanism calls PSWC with minima set tom= ∑t-1 t′=1 at′ + ¯ dt, which guarantees that the cumulative allocation after round t is at least ∑t-1 t′=1 ai,t′ + ¯ di,t. Thus ai,t ≥ ¯ di,t = min(d′i,t , κi,t). If ci,t ≥ 0, then κi,t ≥ ei, which implies ¯ di,t ≥ min(d′i,t , ei) = min(d′i,t , ei +min(0, ci,t)). If ci,t < 0 and ei + ci,t < 0, the bound is trivial. If ci,t < 0 and ei + ci,t ≥ 0, then κi,t = max(0, ei + ci,t), and the same argument as above yields ai,t ≥ min(d′i,t , ei + ci,t) = min(d′i,t , ei + min(0, ci,t)).

Condition (CF5). Fix a round t and suppose there exists an agent j such that: aj,t > max(0, ej + cj,t) = κj,t.

We must show that for every agent i, either ai,t ≥ d′i,t or ai,t ≥ ei + ci,t.

Case 1: ∑i d′i,t ≤ E. In this case, the mechanism allocates ai,t ≥ d′i,t to all agents, so (CF5) holds trivially.

Case 2: ∑i d′i,t > E and E ≤ ∑i ¯ di,t. Here, PSWC is called with upper limits l = ¯ dt. Therefore, for every agent i we have ai,t ≤ ¯ di,t ≤ κi,t. Therefore, the premise aj,t > κj,t can never hold, and (CF5) holds vacuously.

Case 3: ∑i d′i,t > E and E > ∑i ¯ di,t. In this case, as shown above, the minimum constraints guarantee that every agent k receives at least ¯ dk,t = min(d′k,t , κk,t) units. Now fix any agent i. If d′i,t ≤ κi,t, then ¯ di,t = d′i,t , and hence ai,t ≥ d′i,t . Otherwise, d′i,t > κi,t, in which case ¯ di,t = κi,t and ai,t ≥ ¯ di,t = κi,t = max(0, ei + ci,t) ≥ ei + ci,t. Therefore, for every i, either ai,t ≥ d′i,t or ai,t ≥ ei+ci,t.

Since LENDRECOUP is anonymous, Theorem 2 implies that it cannot be strategyproof. However, we can show that it satisfies the weaker notion of online strategyproofness.

Theorem 4. LENDRECOUP is online strategy-proof.

6 Experiments

We compare three alternatives against LENDRECOUP: (i) static max-min fairness (SMMF), (ii) dynamic max-min fairness (DMMF), and (iii) Karma (with α = 0.5). For Karma, we choose α = 0.5 because Vuppalapati et al. (2023) use that value of α in their own empirical evaluation. Recall that Karma with α = 0 corresponds to DMMF.

6.1 Workloads

We evaluate mechanisms over 50 independent simulation repetitions. In each repetition, we simulate a system with 50 agents over 500 rounds. To generate demand profiles, we use Google cluster traces (Wilkes; Reiss et al., 2011; 2011), similar to [Freeman et al., 2018]. These traces record taskprocessing events on a 12.5k-machine cluster over roughly one month in May 2011. Each task submission specifies resource demands requested by the submitting agent, including CPU, memory, and disk space. Demands are normalized relative to the maximum capacity of each resource across all machines in the traces. We focus exclusively on CPU requests.

Following [Freeman et al., 2018], we divide time into 15minute rounds and define each agent's demand in a round as the total CPU requested by tasks submitted during that interval. After processing the traces, we remove agents with constant demands or with average demand below a small threshold. Each remaining agent is assigned an endowment equal to its average demand across all rounds. This reflects real-world settings where agents contribute resources roughly proportional to their long-term demand and rely on sharing during demand spikes.

6.2 EvaluationMetrics

We evaluate mechanisms using agents' cumulative utilities Ui. Let U static i denote the utility agent i receives under the static allocation, where each agent obtains their endowment in every round. We consider the following metrics.

NashWelfare (NW) is ∑i wi log(Ui), where wi = ei ∑j ej . NW balances efficiency and fairness by rewarding high total utility while penalizing inequality. We report NW normalized by the value achieved under the static allocation.

Sharing Index (SIx) for agent i is SIxi = Ui/U static i . It measures the individual gain or loss from sharing; values below one indicate harm. We report the minimum SIx across agents and the percentage of agents with SIxi < 1.

WeightedMin-Max (WMM) ratio is mini Ui/wi maxi Ui/wi . It measures fairness by comparing the worst- and best-off agents after weight normalization, with larger values indicating greater equity. This metric can be sensitive to agents with consistently low demands, for whom Ui/wi will be small under any mechanism. This motivates the normalized variant below.

Normalized Min-Max (NMM) ratio is mini SIxi maxi SIxi , capturing inequality in realized performance relative to agents' standalone guarantees.

Weighted Equity (WEq) is mini Ui/wi mediani Ui/wi . It compares the worst-off agent to a typical agent after weight normalization, 2 with larger values indicating greater equity. WEq is less sensitive to outliers than the min-max ratios above, though still affected by low-demand agents.

Normalized Equity (NEq) is mini SIxi mediani SIxi , and is less sensitive than WEq to agents with low demands.

6.3 Results

As shown in Table 2, NW is tightly clustered across mechanisms. Since all four mechanisms are Pareto efficient, their utilitarian welfares ∑i Ui are identical; thus NW reflects only distributional effects in these simulations. Overall, DMMF and Karma achieve the highest values, with LENDRECOUP extremely close behind, while SMMF trails slightly. The small spread suggests that none of the mechanisms delivers a decisive welfare advantage, and that LENDRECOUP attains near-frontier performance despite its stronger guarantees.

For SIx, LENDRECOUP and SMMF stand out by completely avoiding harm from sharing: both report a minimum value of 1.00 and 0% of agents with SIxi < 1. In contrast, DMMF and Karma exhibit harm for a substantial minority of agents, with minimum SIxi values below one (0.96) and roughly a third of agents experiencing losses relative to the constant-allocation baseline (≈ 36%).

These differences matter because SIxi directly captures whether sharing can leave participants worse off than not participating. By eliminating observed harm (both in worst case and incidence), LENDRECOUP offers a stronger practical value proposition than mechanisms achieving similar welfare while shifting costs onto a subset of agents.

2 The inverse of this metric appears in [Vuppalapati et al., 2023], where it is called disparity.

For WMM and WEq, DMMF performs best, with Karma nearly tied, while LENDRECOUP achieves roughly 60% of DMMF's performance; SMMF trails significantly. In contrast, under the normalized metrics NMM and NEq, Karma and DMMF perform relatively worse: SMMF performs best for NMM followed by LENDRECOUP, while LENDRECOUP performs best for NEq. The disparity between the weighted and normalized metrics is notable; understanding the causes of this gap is an interesting direction for future work. Among the mechanisms considered, LENDRECOUP is the most robust across metrics, again suggesting that it yields a more even distribution of utilities across agents.

7 Conclusion

We introduce the notion of credit fairness in resource-sharing systems, motivated by the idea that agents who lend resources to the system in early rounds should receive priority later. Combined with Pareto efficiency, credit fairness strengthens sharing incentives, making it both a fairness and stability notion for shared systems. Although this strengthening comes at a cost-credit fairness cannot be achieved by an anonymous mechanism simultaneously with both Pareto efficiency and strategyproofness-we introduce LENDRECOUP, a novel mechanism that is credit fair, Pareto efficient, and online strategyproof. Experiments on real-world computational resource-sharing traces show that LENDRECOUP achieves performance comparable to existing state-of-the-art mechanisms. Together with its formal credit-fairness guarantee, these results position LENDRECOUP as a compelling candidate for practical deployment.

Our work raises several open questions. We study a setting with a single resource type, capped linear utility functions, and a fixed set of agents and resource units. Extending credit fairness to more general settings is an interesting direction for future work. Even within our setting, the design space of mechanisms and desiderata remains far from fully explored. For instance, are there mechanisms that achieve stronger theoretical guarantees (e.g., ϵ-Nash SP) and/or improved empirical performance than the four mechanisms studied here?

Acknowledgments

This work was partially supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) under grants RGPIN-2019-04936 and DGECR-2019-00475. Both authors contributed equally to this work.