PaperlayerView exact revision on arXiv

Source-linked AI summary

When do token systems stabilize? Compatibility constraints and community structure

Flore Sentenac, Mingwei Yang, Sophie H. Yu

arXiv:2610.36744v1cs.GTmath.PR

TL;DR

Token systems need stable balances to sustain repeated service exchange, but compatibility constraints make service opportunities uneven. The paper gives a subset-based stability criterion, shows the minimum-token rule is optimal for stability, and characterizes community and individual obstructions in stochastic block models.

  • Problem

    The paper asks when token balances remain stable when agents face requester-specific compatibility constraints that restrict who can provide service.

    Source: §1 · p. 2

  • Method

    It generalizes the token-system model to requester-specific provider sampling and applies its stability criterion to stochastic block models with uniformly sampled requesters.

    Source: §1 · p. 3

  • Results

    The minimum-token rule stabilizes every system stabilizable by an admissible stationary rule, while block-model stability is characterized by community and individual obstructions.

    Source: §1 · p. 3

  • Takeaways & Limitations

    In the block model, excluding both obstructions guarantees stability with high probability; the individual obstruction is always present at sublogarithmic degree scales.

    Source: §1 · p. 3

    Self-service is imposed to keep the system well-defined with isolated vertices; similar results without it are not pursued here.

    Source: §3.1 · p. 7

Abstract

from arXiv · show

Token systems support repeated service exchange without monetary transfers, but their viability depends on the stability of token balances. We study token systems with compatibility constraints among agents. A requester is randomly sampled in each period, and only a few randomly sampled agents are available to provide service. We establish a necessary and sufficient condition for stability and show that the minimum-token rule, which selects the available provider with the lowest token balance, achieves the optimal stability region. We then apply this stability criterion to a random token system generated from stochastic block models with uniformly sampled requesters. We tightly characterize the stability regime by identifying two obstructions to stability: insufficient service opportunities for a group of communities or for an individual agent.

1 Introduction

The paper extends token-system stability analysis to requester-specific compatibility constraints and applies it to community-structured systems. It identifies subset-level service-opportunity conditions and two distinct obstructions to stability.

1 Introduction

  • In kidney exchange, token balances can reward hospitals that contribute easy-to-match pairs by prioritizing their hard-to-match pairs for future matches.Hospitals’ selective submission of harder-to-match pairs to centralized platforms motivates accounting for contributions.Source: §1 · p. 2
  • With uniform requester and provider sampling, the earlier model is unstable at d = 1 but stable under the minimum-token rule at d = 2.The paper addresses the earlier model’s omission of community structure in compatibility relationships.Source: §1 · pp. 2–3
  • A necessary and sufficient subset condition characterizes stabilizability, and the minimum-token rule stabilizes every system that any admissible stationary rule can stabilize.The condition compares each subset’s request rate with the probability that at least one member is sampled as a potential provider.Source: §1 · p. 3
  • In stochastic block models, stability is obstructed by insufficient service opportunities for a group of communities or an individual; excluding both guarantees stability with high probability.The individual obstruction is always present at sublogarithmic degree scales and becomes vacuous at superlogarithmic scales when the community condition holds.Source: §1 · p. 3

1.1 Related literature

  • The paper studies positive recurrence under nonstrategic provider-selection rules, distinguishing its focus from work on incentives, efficiency, or liquidity.Its network-constrained model also differs from load-balancing settings because the paying requester determines the candidate distribution.Source: §1.1 · p. 4

2 Generalized token systems

The model samples a requester and then draws candidate providers from that requester’s availability distribution. A subset-based stability criterion establishes when stabilization is possible and shows that the minimum-token rule attains that region.

2 Generalized token systems

  • Requesters are sampled from a distribution, then draw d candidate providers independently with replacement according to requester-specific availability weights.Agents’ balances may be positive or negative, and the requester gives a token to the selected provider.Source: §2 · p. 5

2.1 Stability criterion

  • The minimum-token rule stabilizes every system stabilizable by an admissible stationary selection rule, regardless of the admissible stationary tie-breaking rule.The proof uses negative quadratic Lyapunov drift when low-balance subsets gain tokens on average.Source: §2.1 · pp. 5–6
  • A stabilizing admissible stationary rule exists exactly when every nonempty proper agent subset satisfies the cut condition, with equality permitted only for sampling-separating sets.A sampling-separating set can serve only itself and cannot serve agents outside the set.Source: §2.1 · p. 6
  • The five-agent star K1,4 is unstable under uniform requests and d = 2, while the four-agent star K1,3 is stable.The K1,4 example applies the subset criterion to the leaves.Source: §2.1 · p. 6

3 Token systems with community structures

The section characterizes stability in compatibility-constrained token systems through two possible bottlenecks: insufficient service opportunities for a group of communities or for an individual agent. With strict margins, avoiding both obstructions yields high-probability stability under the minimum-token rule.

3.1 Model and stability condition

  • The model uses a symmetric stochastic block graph for compatibility, with community-dependent edge probabilities and self-service included.Self-service keeps the system well-defined even for isolated vertices; the authors note that similar results could be derived without this assumption.Source: §3.1 · p. 7
  • The general cut criterion compares demand from agent subsets with the probability that their members are sampled as providers; a strict reverse inequality for any cut implies instability.The criterion reduces to the two interpretable obstruction conditions.Source: §3.1 · p. 7

3.2 Community obstruction

  • A strict failure of the whole-community condition implies high-probability instability under every admissible provider-selection rule.The obstruction occurs when a group of communities requests service more often than its members appear among candidates.Source: §3.2 · p. 8

3.3.1 Erd˝os–Rényi graphs

  • In Erdős–Rényi graphs, singleton cuts are the bottleneck for the degree threshold, which depends on the minimum normalized degree.The theorem and figure describe stability and instability regions separated by thresholds, while leaving the critical equality uncovered.Source: §3.3.1 · pp. 8–9, Figure 1 · p. 10

3.3.2 Stochastic block models

  • In stochastic block models, an individual obstruction arises when an agent’s candidate exposure is too low; its presence implies high-probability instability under every admissible rule.The argument uses low-exposure probability estimates and a second-moment argument to establish that such an agent exists with high probability.Source: §3.3.2 · p. 10

3.4 Combining the two obstructions

  • When the community condition holds and every community avoids the individual threshold, the minimum-token rule stabilizes the system with high probability.At the logarithmic degree scale, the individual threshold is critical; at superlogarithmic scales, the community condition suffices.Source: §3.4 · p. 11

4 Proof of Theorem 1

The proof establishes that the cut criterion is sufficient for stability under the minimum-token rule and that its failure rules out stability under any admissible stationary policy. Its drift argument relies on the support graph’s components and the behavior of token totals on deficient cuts.

4 Proof of Theorem 1

  • When every cut satisfies the criterion and equality cuts are sampling-separating, the minimum-token rule is stable with any permitted tie-breaking.A quadratic Lyapunov drift bound and the Foster–Lyapunov criterion establish positive recurrence.Source: §4 · pp. 11, 13
  • If every support component is a singleton, the chain remains at the all-zero state and is positive recurrent.Otherwise, the proof proceeds under the assumption that some component contains at least two agents.Source: §4 · p. 11
  • For any component containing at least two agents, supported transfers make the chain irreducible on the component-wise zero-sum integer state space.Directed paths allow tokens to be moved between endpoints while leaving intermediate balances unchanged.Source: §4 · pp. 11–12
  • Sampling-separating sets are exactly unions of connected components of the undirected support graph.Transfers remain within components, so each component’s total balance is conserved.Source: §4 · pp. 11–12
  • If a cut violates the criterion, or attains equality without being sampling-separating, no admissible stationary provider-selection policy stabilizes the system.The cut’s token total is a supermartingale with bounded increments, yielding a contradiction to finite expected return time.Source: §4 · pp. 13–14

5 Deferred proofs for Section 3

This section develops exposure-rate and exposure-comparison tools for the proofs of stability and instability thresholds, including a singleton-exposure threshold under (Block-Cut). It also uses the exposure rate function to establish threshold comparisons in the single-community Erdős–Rényi case.

5.1 Properties of the exposure-rate function

  • I_i is continuous and strictly decreasing on [0,ξ_i], with I_i(0)=λ_i and I_i(t)=0 for t≥ξ_i; for equal λ_i=λ, ξ_i=1 and I_i(t)=λ(1−t+t ln t).Source: §5.1 · p. 14

5.2 Exposure estimates and singleton obstructions

  • For 0 < t < ξ_i, the section bounds the lower tail of weighted degree using I_i(t) and compares proxy exposure T_u with actual exposure B_u.The comparison controls uniform excess of T_u over B_u and expected absolute error conditional on a prescribed neighborhood.Source: §5.2 · pp. 15–16
  • If L_n→∞ and L_nI_i(t)≤(1−δ)ln n, a low-exposure vertex exists with high probability; for bounded L_n, a singleton cut violates (Cut-Uniform).The low-exposure vertex satisfies B_u≤t+ε for every fixed ε>0.Source: §5.2 · pp. 17–18

5.3 Proof of Proposition 1

  • A block indicator satisfying condition (2) yields a cut violating the necessary inequality with high probability, and Theorem 1 implies instability.For bounded L_n, a deficient singleton cut gives the same conclusion; the two cases cover admissible scales.Source: §5.3 · p. 18

5.4 Proof of Proposition 2

  • For J∗>0 and lim supₙ→∞ LₙJ∗/ln n<1, if Lₙ→∞, a vertex with Bᵤ<1/d exists with high probability, and its singleton cut violates (Cut-Uniform).For bounded Lₙ, Theorem 1 and Lemma 5 rule out stability.Source: §5.4 · p. 19

5.5 Proof of Theorem 3

  • If (Block-Cut) holds and lim inf L_nJ*/ln n > 1, where J*=min_i I_i(1/d), then exposure bounds and block approximation imply stability.The proof obtains a positive exposure margin above 1/d and verifies the cut inequality for every nonempty proper cut.Source: §5.5 · p. 22

5.6 Proof of Theorem 2

  • I1(1/d) > 1 exactly when λ > λ∗ d; Proposition 2 and Theorem 3 then establish the corresponding instability and stability claims.The Erdős–Rényi graph is the single-community stochastic block model, where I1(t) = λ(1 − t + t ln t).Source: §5.6 · p. 22
Loading 2610.36744v1…