Rate Limiting as a Mechanism

A rate limiter is usually presented as an algorithm — a counter, a bucket, a sliding window — and the vault already documents that side of it in Fixed Window Rate Limiter and Sliding Window Rate Limiter. This note reads the same machinery from the other end. A rate limiter is an allocation rule: it takes a set of participants, something each participant says or does, and returns a division of a scarce resource. That is exactly the object Mechanism Design studies, and it inherits every question that field asks — what objective is being maximized? does a participant gain by lying? by pretending to be several participants? by reshaping its traffic? The answers are mostly unflattering. The single rigorous success story is Dominant Resource Fairness (DRF), which Ghodsi, Zaharia, Hindman, Konwinski, Shenker and Stoica proved is simultaneously strategy-proof, Pareto-efficient, envy-free and sharing-incentive-compatible (NSDI 2011) and which shipped in Mesos and later YARN. Almost everything else in production — per-key quotas, per-IP limits, self-declared priority tiers — is trivially defeated by acquiring more identities, a failure whose auction-theoretic analogue is Yokoo, Sakurai and Matsubara’s proof that the Vickrey–Clarke–Groves mechanism is not false-name-proof (Games and Economic Behavior 2004). The honest conclusion, developed at the end of this note, is that most rate limiting is not a fairness mechanism at all — it is a circuit breaker wearing a fairness costume.

Mental Model: Three Layers, Only One of Which Is the Algorithm

Any rate limiter, however it is implemented, decomposes into three separable layers. Confusing them is the source of most of the strategic failures in this note.

The first layer is the identity function ι. Before you can limit anyone you must decide who “anyone” is: an IP address, an API key, a user account, a tenant, a (source, destination) pair, a Kubernetes ServiceAccount. This is a modelling choice with no algorithmic content and it is where nearly all the exploitable structure lives.

The second layer is the report r — whatever the client tells the system about itself that the allocation depends on. In a plain per-key limiter the report is empty: the limiter observes arrivals and nothing else. In a priority scheme the report is a declared class. In a cluster scheduler the report is a resource-demand vector (2 CPU, 4 GB). In a market it is a bid. The more expressive the report, the more there is to lie about.

The third layer is the allocation rule A(ι, r, arrivals) → served / rejected / queued. This is the part textbooks call “the rate limiting algorithm” — token bucket, fixed window, sliding window, weighted fair queueing, DRF. It is the layer that has been studied to death and the layer that matters least strategically.

flowchart TB
    subgraph L1["Layer 1 — Identity function ι"]
        I1["IP address"]
        I2["API key / token"]
        I3["Account / tenant"]
        I4["(src, dst) conversation"]
    end
    subgraph L2["Layer 2 — Report r"]
        R1["nothing<br/>(observed arrivals only)"]
        R2["declared priority class"]
        R3["resource demand vector"]
        R4["bid / willingness to pay"]
    end
    subgraph L3["Layer 3 — Allocation rule A"]
        A1["fixed / sliding window"]
        A2["token bucket"]
        A3["weighted fair queueing"]
        A4["Dominant Resource Fairness"]
        A5["auction / posted price"]
    end
    L1 --> L2 --> L3
    L3 --> OUT["serve · queue · 429"]

    ATT1["Attack: sybil<br/>split into k identities"] -.-> L1
    ATT2["Attack: misreport<br/>inflate demand, claim P0"] -.-> L2
    ATT3["Attack: reshape traffic<br/>burst, retry, pad"] -.-> L3

What it shows: the three layers of any rate limiter and the distinct attack that targets each. The insight: the literature optimizes Layer 3 and the attacker works on Layer 1. A perfectly strategy-proof allocation rule composed with a free-to-forge identity function is not strategy-proof — a client that can mint k identities receives k shares of whatever the rule hands out per identity. Strategyproofness is not compositional, and the composition is where deployments live.

The Four Questions to Ask of Any Limiter

Mechanism design supplies a fixed interrogation. Applied to a quota system it reads:

Question	Mechanism-design name	Concrete form for a rate limiter
What is being maximized?	the objective / social choice function	Throughput? Egalitarian minimum? Revenue? Or merely “the server does not fall over”?
Does honesty pay?	incentive compatibility (IC), strategyproofness (SP)	Does a client that truthfully declares its demand or priority do at least as well as one that lies?
Is participating better than opting out?	individual rationality (IR); DRF’s sharing incentive	Is a tenant better off inside the shared pool than with a statically partitioned 1/n slice?
Is one identity better than many?	false-name-proofness / sybil-resistance	Does splitting into `k` API keys increase total service?

The last row is the one the systems literature almost never asks and the one that decides almost every real case. It is a strictly stronger requirement than strategyproofness: Yokoo et al. state plainly that a strategy-proof protocol “is not necessarily false-name-proof, and vice versa” (Yokoo et al. 2004, §1).

Note also what the first row usually reveals. Ask an operator what their rate limiter maximizes and the answer is rarely a welfare function; it is “we stay up.” Google Cloud’s quota documentation says quotas exist “to help ensure fairness and reduce spikes in resource use and availability” and that they “protect the community of Google Cloud users by preventing the overloading of services” (Cloud Quotas overview) — fairness and overload protection named in the same breath, as if they were the same objective. They are not, and the difference is the subject of the last section.

Max-Min Fairness Is an Allocation Rule, and It Was Attacked in 1989

The oldest formal allocation rule in this space is max-min fairness. Demers, Keshav and Shenker state it precisely in the paper that gave the internet fair queueing: with total resource μ_total shared among N users, where user i requests ρ_i and receives μ_i, an allocation is max-min fair if (1) no user receives more than its request, (2) no other allocation satisfying (1) has a higher minimum allocation, and (3) condition (2) remains recursively true after removing the minimal user and reducing the total accordingly, μ_total ← μ_total − μ_min (Demers, Keshav & Shenker, SIGCOMM 1989, §2.1). Reading the symbols: you lexicographically maximize the sorted vector of allocations from the bottom up, and in the simple saturated case this collapses to μ_i = MIN(μ_fair, ρ_i) where μ_fair is set so the shares sum to μ_total. The authors are explicit that this criterion smuggles in a value judgement: “implicit in the max-min definition of fairness is the assumption that the users have equal rights to the resource.”

Their algorithm approximates a hypothetical bit-by-bit round robin service discipline. Let R(t) count rounds completed by time t; with N_ac(t) active conversations and line speed μ, rounds advance at ∂R/∂t = μ / N_ac(t). Each arriving packet of size P is stamped with a virtual finishing time F_i = S_i + P_i where S_i = MAX(F_{i−1}, R(t_i)), and packets are transmitted in increasing order of F. Walking the symbols: R(t_i) is the round at which packet i arrives, F_{i−1} is when the previous packet of the same conversation would have finished, and the MAX means a conversation that has gone idle restarts from the current round rather than banking credit. That last clause is a deliberate anti-gaming detail — without it, a client could idle to accumulate an unbounded backlog of virtual credit and then spend it all at once.

What makes this a mechanism-design paper rather than a queueing paper is §2.1’s discussion of who counts as a user, which is Layer 1 of the mental model above, argued out in 1989:

Per source. “unnaturally restricts sources such as file servers which typically consume considerable bandwidth.”
Per receiver. “allows a receiver’s useful incoming bandwidth to be reduced by a broken or malicious source sending unwanted packets to it.”
Per process on a host. “encourages human users to start several processes communicating simultaneously, thereby avoiding the original intent of fair allocation.” This is the sybil attack, named in a networking paper thirteen years before Douceur named it.
Per source–destination pair (their choice). “allows a malicious source to consume an unlimited amount of bandwidth by sending many packets all to different destinations. While this does not allow the malicious source to do useful work, it can prevent other sources from obtaining sufficient bandwidth.”

They then conclude that source–destination pairs are “the best tradeoff between security and efficiency” — an explicit admission that the identity function is chosen to bound an attack, not to model reality. Every subsequent per-client limiter makes the same trade and usually without saying so.

flowchart LR
    subgraph choice["Choice of identity ι — DKS 1989 §2.1"]
        S["per source"] -->|"penalizes<br/>file servers"| BAD1["inefficient"]
        D["per receiver"] -->|"attacker floods<br/>a victim"| BAD2["DoS on receiver"]
        P["per process"] -->|"fork more<br/>processes"| BAD3["sybil: unbounded"]
        C["per (src,dst) pair"] -->|"fan out to many<br/>destinations"| BAD4["sybil: bounded by<br/>reachable destinations"]
    end
    C ==> PICK["chosen:<br/>'best tradeoff between<br/>security and efficiency'"]

What it shows: the four candidate identity functions Demers, Keshav and Shenker considered and the specific manipulation each admits. The insight: none of the four is sybil-proof; the paper picks the one whose sybil attack is bounded (you can only fan out to as many destinations as exist and you gain no useful work) rather than unbounded. Bounding the gain from identity-splitting, not eliminating it, is the realistic design target.

Weighted variants — weighted fair queueing, and Parekh and Gallager’s Generalized Processor Sharing (GPS), the fluid model that WFQ approximates — do not change the strategic picture. They add a weight vector φ_i so that a backlogged session receives a share proportional to φ_i / Σφ_j, which makes the rule weighted max-min fair. Weights are assigned by the operator, so they are not a report and cannot be lied about; but the denominator Σφ_j is a sum over identities, so splitting one session with weight φ into k sessions of weight φ each multiplies your share by roughly k. The weight vector is a defense against nothing if the identity space is open.

Uncertain

Verify: the exact statement and bounds of Parekh & Gallager’s GPS results (IEEE/ACM ToN 1(3):344–357, June 1993). Reason: source blocked — the CiteSeerX PDF returned HTTP 404 and no other full-text copy was retrieved during this task. The GPS characterization above is stated from the standard definition of weighted processor sharing and from the DKS paper’s related discussion, not from the Parekh–Gallager text itself. To resolve: obtain the IEEE/ACM Transactions on Networking PDF or the MIT thesis (dspace.mit.edu/handle/1721.1/3239 covers the multiple-node case) and confirm the delay bound D_i ≤ σ_i/g_i form and the leaky-bucket admission assumption. uncertain

Dominant Resource Fairness: The One Rigorous Success

DRF is the strongest available evidence that a resource-allocation policy can be designed the way an auction is designed — properties first, algorithm second — and still ship. Ghodsi et al. do exactly that: §3 of the paper lists four properties they demand of any multi-resource policy, and then §4 constructs the policy that satisfies them.

The four required properties, verbatim from the paper’s §3:

Sharing incentive — “Each user should be better off sharing the cluster, than exclusively using her own partition of the cluster… a user should not be able to allocate more tasks in a cluster partition consisting of 1/n of all resources.” This is individual rationality with the outside option pinned at a static equal split.
Strategy-proofness — “Users should not be able to benefit by lying about their resource demands. This provides incentive compatibility, as a user cannot improve her allocation by lying.”
Envy-freeness — “A user should not prefer the allocation of another user.”
Pareto efficiency — “It should not be possible to increase the allocation of a user without decreasing the allocation of at least another user.”

Four further “nice-to-have” properties are listed: single-resource fairness, bottleneck fairness, population monotonicity, and resource monotonicity.

The rule itself is one sentence. For each user, compute the share of every resource they hold; the largest of those shares is their dominant share and the corresponding resource their dominant resource. DRF then applies max-min fairness to dominant shares — it repeatedly hands the next task to whichever user currently has the lowest dominant share.

The worked example, step by step

The paper’s §4.1 example is small enough to check by hand. A cluster has 9 CPUs and 18 GB RAM. User A’s tasks demand ⟨1 CPU, 4 GB⟩; user B’s demand ⟨3 CPU, 1 GB⟩. Each A-task consumes 1/9 of CPU and 4/18 = 2/9 of memory, so A’s dominant resource is memory. Each B-task consumes 3/9 = 1/3 of CPU and 1/18 of memory, so B’s dominant resource is CPU. Equalizing dominant shares means solving

maximize (x, y)                      # x = A's task count, y = B's task count
subject to   x + 3y  ≤  9            # CPU capacity
             4x + y  ≤  18           # memory capacity
             2x/9    =  y/3          # equalize dominant shares

which yields x = 3, y = 2. User A gets ⟨3 CPU, 12 GB⟩ and user B gets ⟨6 CPU, 2 GB⟩ — A holds 2/3 of the RAM, B holds 2/3 of the CPUs, and their dominant shares are equal at 2/3. Note the outcome is not an equal split of anything: A gets a third of the CPUs and two-thirds of the memory. Equalizing dominant shares deliberately gives each tenant more of what it actually needs.

flowchart TB
    START["9 CPU, 18 GB free<br/>A wants ⟨1 CPU, 4 GB⟩ · B wants ⟨3 CPU, 1 GB⟩"]
    S1["pick lowest dominant share → B<br/>B: ⟨3/9, 1/18⟩ dom 1/3 · A: 0"]
    S2["pick A · A dom 2/9"]
    S3["pick A · A dom 4/9"]
    S4["pick B · B dom 2/3"]
    S5["pick A · A dom 2/3<br/>CPU now 9/9 saturated → stop"]
    START --> S1 --> S2 --> S3 --> S4 --> S5
    S5 --> END["A: ⟨3 CPU, 12 GB⟩<br/>B: ⟨6 CPU, 2 GB⟩<br/>both dominant shares = 2/3"]

What it shows: the five scheduling decisions DRF makes on the paper’s Table 1 example, each labelled with the dominant share that drove the choice. The insight: DRF is a greedy rule with one comparison — “who currently has the smallest dominant share” — and its heavy theoretical guarantees come from that single line, not from any global optimization. That is what makes it deployable inside a scheduler’s hot loop.

What is actually proved, and under what assumptions

The property claims are frequently garbled in secondary write-ups, so here is the verified ledger from Appendix A of the paper, which proves each theorem under progressive filling — an idealized fluid algorithm in which “resources can be allocated in arbitrary small amounts,” increasing every user’s dominant share at the same rate until some resource saturates, then freezing the users on that resource and recursing.

#	Statement	Status in the paper	Assumption
Thm 9	DRF is Pareto efficient	proved	progressive filling (divisible)
Thm 10	DRF satisfies sharing incentive and bottleneck fairness	proved	progressive filling
Thm 11	Every DRF allocation is envy-free	proved	progressive filling
Thm 12	Strategy-proofness — “A user cannot increase her dominant share in DRF by altering her true demand vector”	proved	progressive filling
Thm 13	With strictly positive demands, all users get the same dominant share	proved	`d_ij > 0` for all `i, j`
Thm 14	DRF satisfies population monotonicity	proved	strictly positive demands only
Thm 6	No policy can satisfy sharing incentive, Pareto efficiency and resource monotonicity simultaneously	proved (impossibility)	—
Thm 7	In the discrete case, any two users’ allocations differ from the continuous allocation by at most one `max-task`	proved	each machine ≥ `max-task`

Two caveats the marketing usually drops. First, DRF does not satisfy resource monotonicity — adding capacity can reduce someone’s allocation — and the paper is candid that this is unavoidable rather than a bug: Theorem 6 shows sharing incentive, Pareto efficiency and resource monotonicity are mutually incompatible, and the authors chose to keep the first two “since adding new resources to a system is a relatively rare event.” Second, population monotonicity holds only for strictly positive demand vectors; the paper notes that otherwise “DRF no longer satisfies the population monotonicity property.”

The comparison table in §6 is the part worth internalizing. Against the two natural alternatives — asset fairness (equalize the total quantity of resources each user gets, summed across types) and competitive equilibrium from equal incomes (CEEI, the microeconomics standard) — DRF is the only one holding all four required properties:

Property	Asset Fairness	CEEI	DRF
Sharing incentive	✗	✓	✓
Strategy-proofness	✓	✗	✓
Envy-freeness	✓	✓	✓
Pareto efficiency	✓	✓	✓
Single-resource fairness	✓	✓	✓
Bottleneck fairness	✗	✓	✓
Population monotonicity	✓	✗	✓
Resource monotonicity	✗	✗	✗

(Reproduced from Table 2 of the paper.) CEEI’s failure is the instructive one: it is “the preferred fair division mechanism in microeconomic theory” and it is not strategy-proof, with a concrete counterexample in §6.1.2 where user 1 raises her share by claiming she needs more of resource 2 than she actually does. A rule can be efficient, envy-free and economically canonical and still reward lying.

DRF is not a paper trick. Mesos implemented it, and Apache Hadoop YARN carries DominantResourceCalculator to this day — the class comment in Hadoop 3.4.1 restates the rule (“it seeks to maximize the minimum dominant share across all entities… In the single resource case, it reduces to max-min fairness for that resource”) and cites the NSDI paper by URL (DominantResourceCalculator.java, rel/release-3.4.1). It is annotated @Private @Unstable, so it is an internal comparator rather than a supported public API.

Where DRF’s strategyproofness stops

Parkes, Procaccia and Shah revisited DRF three years later and found the boundary (EC 2012 / ACM TEAC 3(1)). Their results matter more to practitioners than the original theorems, because they attack precisely the assumption a real scheduler violates.

DRF’s guarantees rest on Leontief preferences — utility is determined by the proportions in a demand vector, so half a task is worth half a task. Parkes et al. observe that this “implicitly requires that both resources and tasks be divisible,” whereas in practice “an agent’s task would require a minimum, indivisible bundle of resources. For example, if an agent requires 2 CPUs and 1 GB RAM to run one instance of its task, allocating 1 CPU and 1/2 GB RAM would be no more preferred than allocating nothing at all.” Real utility is a step function. Under that (entirely realistic) model:

Theorem 5.1: “Under indivisibilities there is no mechanism that satisfies PO, SI, and SP.” Their proof needs only two agents and one resource, each demanding a bundle of size 1/2 + ε.
Theorem 5.3: “Under indivisibilities there is no mechanism that satisfies PO, EF1, and SP” — where EF1 is envy-freeness relaxed to “up to one bundle.” Again two agents, one resource, bundles of 1/3.
Pareto efficiency and strict envy-freeness are “trivially incompatible” under indivisibility: if two agents each need the whole cluster, the only Pareto-optimal allocations give everything to one of them.
Their conclusion: “SP seems to preclude reasonable mechanisms when tasks are indivisible,” so their proposed mechanism SequentialMinMax drops SP and keeps PO + SI + EF1.

They also quantify what fairness costs. DRF “can produce allocations that only provide roughly 1/m of the social welfare of the optimal allocation, where m is the number of resources” — but crucially “this poor welfare property is necessary for any mechanism that satisfies at least one of the three properties SI, EF, and SP.” Fairness and throughput are genuinely opposed, and DRF is not the reason.

flowchart TB
    DIV["Divisible tasks<br/>(Leontief preferences)"] --> OK["DRF: PO + SI + EF + SP<br/>all four provable<br/>(Ghodsi 2011, Thms 9–12)"]
    IND["Indivisible task bundles<br/>(utility = step function)"] --> NO1["Thm 5.1: PO + SI + SP impossible"]
    IND --> NO2["Thm 5.3: PO + EF1 + SP impossible"]
    IND --> NO3["PO + EF trivially impossible"]
    NO1 --> DROP["Best achievable:<br/>PO + SI + EF1, drop SP<br/>(SequentialMinMax)"]
    NO2 --> DROP
    OK -.->|"real schedulers<br/>allocate whole tasks"| IND

What it shows: the divisibility assumption on which DRF’s four guarantees rest, and the three impossibility results that fire the moment it is dropped. The insight: every production scheduler allocates whole containers, so every production scheduler is on the bottom branch. DRF-in-Mesos and DRF-in-YARN are running a mechanism whose strategyproofness proof does not apply to them — it applies to a fluid idealization they approximate to within one max-task (DRF Theorem 7). That approximation bound is a real and useful guarantee; strategyproofness is not one of the things it preserves.

Identity-Splitting Is the Central Attack

Everything above concerns lying about what you want. The dominant attack on real rate limiters is lying about who you are.

The auction-theoretic result that transfers

Yokoo, Sakurai and Matsubara studied bidders who “submit multiple bids under multiple identifiers such as multiple e-mail addresses” and called such a bid a false-name bid. Their headline results are three:

The VCG mechanism, “which is strategy-proof and Pareto efficient when there exists no false-name bids, is not false-name-proof.”
Proposition 1: “In combinatorial auctions, there exists no false-name-proof auction protocol that satisfies Pareto efficiency.”
Proposition 2: VCG is false-name-proof when the surplus function U_A(·) is concave over bidders — formally, for bidder sets Y ⊆ Z and any W, U_A(Z ∪ W) − U_A(Z) ≤ U_A(Y ∪ W) − U_A(Y). Reading it: the marginal value of adding a group of bidders never increases as the existing bidder set grows. Submodularity of U over bidders implies this concavity (their Proposition 3).

The counterexample (Example 2) is arithmetic you can do in your head. Two goods a₁, a₂. Bidder 1 values them at (7, 7, 14) — 7 for either alone, 14 for the pair. Bidder 2 values (0, 0, 12) — 12 for the pair only, nothing for singletons. Bidder 3 is absent. Bidding honestly under one identity, bidder 1 wins both goods and pays 12, the surplus that bidder 2’s exclusion destroyed. If bidder 1 instead splits into two identities each bidding 7 for one good, the situation becomes their Example 1: each fake bidder pays 12 − 7 = 5, so bidder 1 pays 10 instead of 12. Same allocation, two units of profit conjured out of an extra email address.

Now transfer the result. A rate limiter is a mechanism without payments. In VCG, extra identities are not free — each one wins goods it must pay for, and the manipulation only works because the pivot calculation happens to become cheaper. In a quota system there is nothing to pay, and total service is typically additive in identities: k API keys with quota q each yield kq. The gain from sybil is not a subtle pivot artifact; it is linear and unconditional. The strongest theoretical guarantee in the field — VCG’s dominant-strategy truthfulness — already fails against false names in a domain where identities cost money. A per-key quota, where they cost an email address, has no chance.

Proposition 2 is the constructive half, and it is what good deployments actually implement without citing it. If the service a client receives is concave in the number of identities it presents, splitting stops paying. Make it flat and splitting is worthless.

flowchart LR
    subgraph A["Additive rule (naive)"]
        A1["1 key → q"] --> A2["k keys → k·q"] --> A3["gain from sybil: linear<br/>∴ everyone sybils"]
    end
    subgraph B["Concave rule"]
        B1["1 key → q"] --> B2["k keys → q·(1 + log k), capped"] --> B3["gain diminishes<br/>∴ sybil is barely worth it"]
    end
    subgraph C["Nested / shared-budget rule"]
        C1["1 key → q"] --> C2["k keys → still q<br/>(children draw on parent)"] --> C3["gain: zero<br/>∴ false-name-proof by construction"]
    end

What it shows: three ways a quota system can respond to a client that multiplies its identities, and the sybil payoff under each. The insight: false-name-proofness is not achieved by detecting fake identities — it is achieved by making the allocation rule concave (ideally flat) in identity count, so detection becomes unnecessary. Yokoo’s Proposition 2 is the theorem behind that intuition; the third column is a rate-limiting design pattern, not an auction.

Why detection is not the answer

Douceur’s The Sybil Attack explains why the detection route is a dead end. His model has entities communicating over a broadcast cloud; a faulty entity may present many identities. Lemma 1: if the ratio of a faulty entity’s resources to those of a minimally capable entity is ρ, then it “can present g = ρ distinct identities.” The available countermeasures are resource challenges — demanding proof of communication, storage, or computation (his examples: reply within a time window; store a large incompressible blob; solve a hash puzzle where finding a solution costs ~2^(n−1) hash evaluations and verifying costs constant time) — and Lemma 2 requires these challenges be issued to all identities simultaneously, which does not scale. The paper’s conclusion is that “without a logically centralized authority,” distinct identities cannot be established.

For a public API this is decisive: an IP-keyed limiter is defeated by a /64 of IPv6 or a residential proxy pool, and no clever counting algorithm fixes it. What does fix it is the logically centralized authority Douceur names — which for a SaaS API is the account system, and behind that, the payment instrument.

The three production patterns, verified

GitHub is the textbook anti-sybil design. Unauthenticated requests are “associated with the originating IP address, not with the user or application that made the request,” and get 60 requests per hour. Authenticated users get 5,000 per hour (GitHub REST API rate limits, API version 2026-03-10). That 83× gap is the mechanism: it makes the cheap-to-forge identity nearly worthless and pushes every serious client onto the expensive-to-forge one. Then the budgets are made nested rather than additive — the docs spell out the anti-splitting rule explicitly: “requests made by a higher-limit app reduce the remaining budget available for lower-limit authentication methods. For example, if an app with a 15,000 request limit makes 10,000 requests on your behalf, you will have exhausted the 5,000 request budget for your personal access tokens.” Creating another OAuth app to act on your behalf gains you nothing; you draw on the same pool. Where budgets do scale with identity count, the growth is explicitly concave and capped: an installation gets “another 50 requests per hour for each repository” above 20 repositories and per user above 20 users, but “the rate limit cannot increase beyond 12,500 requests per hour.”

GitHub’s secondary limits add the other missing piece — pricing by cost. No more than 900 points per minute per endpoint, where “Most REST API GET, HEAD, and OPTIONS requests” cost 1 point and “Most REST API POST, PATCH, PUT, or DELETE requests” cost 5. A write is charged five times a read because it costs the server more; this is the crude, ungeneralized ancestor of charging an agent for the externality it imposes, which is what The VCG Mechanism does properly. And the docs note that “Some REST API endpoints have a different point cost that is not shared publicly” — deliberate opacity as an anti-gaming device, which quietly abandons the assumption underpinning The Revelation Principle that the mechanism is common knowledge.

Google Cloud is the opposite choice, made deliberately. “Quotas generally apply at the Google Cloud project level. Your use of a resource in one project doesn’t affect your available quota in another project. Within a Google Cloud project, quotas are shared across all applications and IP addresses” (Cloud Quotas overview). That is an additive rule in the project dimension: more projects, more quota. It is not an oversight — the sybil cost has simply been moved out of the rate limiter and into billing, identity verification, and the organization hierarchy. The lesson generalizes: a quota system does not have to be false-name-proof on its own if some other layer prices identity.

Kubernetes goes further and tells clients to sybil themselves. API Priority and Fairness assigns each request to a flow identified by “the name of the matching FlowSchema plus a flow distinguisher — which is either the requesting user, the target resource’s namespace, or nothing,” and then gives “approximately equal weight to requests in different flows of the same priority level.” The consequence is stated outright in the documentation: “To enable distinct handling of distinct instances, controllers that have many instances should authenticate with distinct usernames” (Kubernetes — API Priority and Fairness). A per-identity equal-share rule rewards identity multiplication, and rather than fight it inside a trusted cluster, Kubernetes recommends it as the way to get your fair share. This is the cleanest possible demonstration that “fair queueing” plus “open identity space” equals “an incentive to fork.” APF mitigates the blast radius with shuffle sharding — flows are hashed to a random subset of queues so that a low-intensity flow is unlikely to share every queue with a high-intensity one — and the documentation publishes the collision probabilities (with hand size 8 and 128 queues, the probability that a given flow is fully shadowed by 4 elephants is about 3.4 × 10⁻⁶). See API Priority and Fairness for the mechanics.

Priority Is a Scarce Resource That Clients Are Asked to Declare for Free

The second classic failure is priority. A system that lets clients tag their own requests P0 / P1 / P2 and serves them in that order has built a direct-revelation mechanism with an empty payment rule. Its outcome is over-determined: since declaring P0 weakly dominates declaring anything else for every client, in equilibrium everything is P0 and the priority field carries zero information. Formally, the rule is not incentive compatible in dominant strategies; by The Revelation Principle (Proposition 9.25 in Nisan, Roughgarden, Tardos & Vazirani, Algorithmic Game Theory) there is no point looking for a cleverer indirect encoding of the same free declaration — if no truthful direct mechanism implements the objective, no mechanism does.

There are exactly four escapes, and every real system uses one of them.

1. Take the declaration away from the client. Classify by request type, which the operator controls. Stripe does this: it splits traffic into “critical API methods (e.g. creating charges) and non-critical methods (e.g. listing charges)” and reserves a share of the fleet for the former — “If our reservation number is 20%, then any non-critical request over their 80% allocation would be rejected with status code 503” (Stripe — Scaling your API with rate limiters). The client never declares anything. This is the cheapest fix and the reason it is the most common one.

2. Cap the declaration. Give each client a budget of high-priority calls rather than a free label. Priority then becomes rivalrous within the client’s own allocation, and spending it on a low-value request has a real opportunity cost. Kubernetes’ exempt priority level is the degenerate case — an escape hatch narrow enough that no ordinary workload can claim it.

3. Charge for it. Money is the classical device that makes truth-telling costly, and Algorithmic Game Theory frames the domain split exactly this way: the Gibbard–Satterthwaite theorem (their Theorem 9.8) says that on unrestricted preference domains only dictatorial rules are dominant-strategy implementable, and the standard escape is to restrict the domain — “the ability for agents to make monetary transfers allows for a rich class of strategy-proof rules.” Priority pricing (a surcharge for expedited service) is that escape applied to queueing. It is rare in internal systems precisely because internal systems have no currency.

4. Restrict the domain instead. This is DRF’s route and it is worth naming as such. DRF is not strategy-proof because of a payment; it is strategy-proof because Leontief preferences are a restricted domain on which a non-dictatorial strategy-proof rule happens to exist. That is the same escape from Gibbard–Satterthwaite, taken without money — and it is exactly why the guarantee evaporates in Parkes–Procaccia–Shah’s indivisible setting: the domain restriction no longer holds.

stateDiagram-v2
    [*] --> FreeDeclaration: client tags its own priority
    FreeDeclaration --> AllP0: declaring P0 weakly dominates
    AllP0 --> NoInformation: field carries zero signal
    NoInformation --> FCFS: system degrades to first-come-first-served

    [*] --> OperatorClassifies: priority by endpoint (Stripe)
    [*] --> BudgetedPriority: fixed P0 allowance per client
    [*] --> PricedPriority: surcharge for expedite
    [*] --> RestrictedDomain: Leontief demands (DRF)
    OperatorClassifies --> Informative
    BudgetedPriority --> Informative
    PricedPriority --> Informative
    RestrictedDomain --> Informative: truthful reports are optimal

What it shows: the equilibrium collapse of a free self-declared priority field, and the four designs that avoid it. The insight: the collapse is not a matter of client goodwill or documentation. It is the unique dominant-strategy outcome, so an internal platform whose priority field is “please be honest” will observe it eventually, and the observed symptom is a priority queue that has silently become FIFO.

Retries: A Mechanism That Rewards Defection

The most under-appreciated strategic surface in rate limiting is the rejection path. A naive limiter serves whatever arrives while capacity remains; a client that retries immediately upon rejection therefore occupies a larger fraction of the next admission window than a client that backs off politely. The allocation rule literally pays clients to defect, and the well-behaved client subsidizes the aggressive one. Worse, the aggregate outcome is not merely unfair — it is the Retry Storms and Cascading Failures feedback loop, where the retries that individually make sense collectively destroy the service.

The engineering fix is documented in AWS’s own analysis of the problem. Marc Brooker’s post models optimistic concurrency control against a remote database with mean network delay 10 ms and variance 4 ms, and shows that plain capped exponential backoff is insufficient: “Instead of reducing the number of clients competing in every round, we’ve just introduced times when no client is competing” — the clients’ sleeps stay correlated, so the calls arrive in clusters. Adding randomness breaks the correlation. He names three variants (AWS Architecture Blog — Exponential Backoff And Jitter):

Full Jitter — sleep a uniform random value in [0, min(cap, base·2^attempt)).
Equal Jitter — keep half the deterministic backoff and randomize the other half, so sleeps are never very short.
Decorrelated Jitter — like Full Jitter, but the upper bound grows from the previous random value rather than the attempt count.

With 100 contending clients, jitter “reduced our call count by more than half” against un-jittered backoff, and Full Jitter did the least total work. The measured ranking: no-jitter is “the clear loser,” Equal Jitter is the weakest of the jittered three, and Full Jitter and Decorrelated Jitter trade a little work against a little time. The honest caveat is in the post too — “none of these approaches fundamentally change the N² nature of the work to be done.” (A May 2023 update notes most AWS SDKs now implement this in their standard and adaptive retry modes.)

Read as a mechanism, jitter is a randomized tie-breaking rule that removes the advantage of synchronization, and backoff is a cost imposed on retrying that makes hammering unprofitable. But note the crucial limitation: both are implemented in the client. They are a convention, not an enforced rule, and a client that simply does not implement them is strictly better off in the short run. That is what makes retry behavior a genuine strategic problem rather than an engineering one — the mechanism designer does not control the strategy space.

The server-side counterpart is to make aggression observable and chargeable. Three patterns do this:

Count rejections against the quota. If a 429 consumes a token, retrying costs the client its own future capacity and the incentive inverts. Stripe’s concurrent-request limiter has this flavour: it caps requests in flight rather than requests per second precisely because “users often get frustrated waiting for the endpoint to return and then retry. These retries add more demand to the already overloaded resource, slowing things down even more.”
Publish the deadline and enforce it. GitHub returns retry-after and x-ratelimit-reset, and instructs clients not to retry before the stated time. This turns backoff from a guess into a coordinated schedule — the server, which alone knows the true reset time, reports it, and clients that comply avoid wasted calls.
Retry budgets. Cap retries as a fraction of a client’s successful traffic, so a client in total failure cannot amplify at all. This bounds the amplification factor structurally rather than per-request; see Retries Backoff and Idempotency at the Protocol Layer.

sequenceDiagram
    participant P as Polite client<br/>full jitter
    participant A as Aggressive client<br/>immediate retry
    participant S as Server<br/>naive window limiter
    Note over S: window opens, 10 slots
    A->>S: 10 requests at t=0
    S-->>A: 10 served
    P->>S: 1 request at t=0
    S-->>P: 429
    Note over P: sleeps uniform in 0 .. 2^k x base
    Note over S: window opens, 10 slots
    A->>S: 10 requests at t=0
    S-->>A: 10 served
    P->>S: arrives at t=0.7 into window
    S-->>P: 429 - window already full
    Note over P,S: politeness is strictly dominated<br/>under a naive window limiter

What it shows: two clients under a fixed-window limiter, one implementing jitter and one retrying immediately, across two windows. The insight: exponential backoff with jitter is socially optimal and individually dominated. Unless the server prices retries — by charging rejections against quota, or by publishing and enforcing retry-after — a limiter that simply serves whoever arrives first inside each window is a mechanism whose dominant strategy is to hammer it. This is the same structure as the defection equilibrium in The Prisoner’s Dilemma and the same one that appears in Congestion Control as a Game.

Schemes Compared by Incentive Property

Putting the schemes side by side against the questions from the top of the note. “Work-conserving” means the server is never left idle while requests are waiting — a property hard quotas deliberately give up.

Scheme	Report the client makes	Strategy-proof?	Sybil-resistant?	Work-conserving?	What it really optimizes
Fixed window per key (Fixed Window Rate Limiter)	none	vacuously (nothing to lie about)	✗ — additive in keys	✗ rejects with capacity free	server survival; boundary bursts up to 2×
Sliding window per key (Sliding Window Rate Limiter)	none	vacuously	✗ — additive in keys	✗	smoother enforcement of the same cap
Token Bucket per key	none	vacuously	✗ — additive in keys	✗	burst tolerance with a long-run average
Concurrency cap (Stripe’s in-flight limiter)	none	vacuously	✗ but bounded by real client concurrency	partially	protecting a contended resource
Weighted fair queueing / GPS	none (weights set by operator)	vacuously	✗ — share ∝ 1/Σφ over identities	✓	weighted max-min fairness on one resource
Self-declared priority	priority class	✗ — everything becomes P0	✗	✓	nothing, in equilibrium
Operator-classified priority (Stripe)	none	vacuously	✗	✓	availability of critical endpoints
Shuffle-sharded fair queueing (API Priority and Fairness)	none	vacuously	✗ — documented as encouraged	✓	isolation of low- from high-intensity flows
DRF (divisible)	resource demand vector	✓ proved (Thm 12)	✗ — nothing in the model prices identity	✓ (Pareto efficient)	max-min on dominant shares
DRF (indivisible tasks)	demand bundle	✗ (Thms 5.1, 5.3)	✗	✓	approximation within one `max-task`
Posted price / metered billing	none — you pay per unit	✓ (take it or leave it)	✓ — identities cost money	✓	revenue, and thereby demand rationing
The VCG Mechanism	full valuation	✓ in dominant strategies	✗ (Yokoo Prop. 1)	✓	social welfare

Two patterns fall out. First, the column “strategy-proof?” is mostly answered vacuously — the overwhelming majority of production rate limiters take no report at all, so there is nothing to lie about and truthfulness is trivial. That is not a triumph; it means those limiters cannot express or exploit any information about what clients actually need. Second, only the schemes involving money are sybil-resistant. That is the whole finding, and it is the reason cloud providers put quota at the billing-account boundary rather than trying to make the limiter itself clever.

Failure Modes and Gotchas

The limiter is fair and the system is not. Per-request fairness is not per-cost fairness. Ten GET /users/me calls and ten POST writes both consume ten tokens under a request-counting limiter while imposing wildly different load. GitHub’s 5:1 point weighting for mutating verbs is the minimal correction; the general form is charging by measured cost, which is what Multi-Tenancy and Fairness in LLM Serving must do because a 100-token and a 100,000-token LLM request differ by three orders of magnitude in work.

Idle-credit accumulation. Any scheme that lets a client bank unused allowance rewards strategic idling: stay quiet, then dump. Fair queueing avoids it structurally — the S_i = MAX(F_{i−1}, R(t_i)) rule resets an idle conversation to the current virtual round. Token buckets accept it deliberately, bounded by bucket depth. Fixed windows suffer the well-known 2× boundary burst as an accidental version of the same thing.

Weights and priorities drift into meaninglessness. Every long-lived internal platform ends up with a priority ladder where the majority of traffic sits at the top rung, for exactly the equilibrium reason above. The diagnostic is a histogram of declared priority; if it is not roughly the shape you designed for, the field has stopped carrying information.

Sybil pressure appears wherever the quota binds. Watch for the leading indicators before they become an incident: a sudden rise in account or project creation from one payment instrument or CIDR; API keys created in bursts; clients that round-robin across credentials; traffic that reappears at the same aggregate rate after you cut one key. The mitigation is aggregation — apply a second limit at a coarser identity that is expensive to duplicate (organization, billing account, verified domain) above the per-key limit, which is exactly GitHub’s nesting.

Retry amplification is invisible until it is fatal. A quota that is never breached produces no retries, so the amplification factor sits at 1.0 and nobody measures it. Instrument the ratio of attempts to distinct logical operations per client in normal operation, not during the incident.

Treating rate limiting as fairness when it is really a circuit breaker. This is the big one, and it is where the whole framing of this note has to be qualified — see below.

Alternatives and When to Choose Them

When the honest goal is “do not fall over,” build a circuit breaker, not a mechanism. Most rate limiting is overload protection and nothing else. Stripe draws the line precisely: rate limiters are per-user and preventative, while “a load shedder makes its decisions based on the whole state of the system rather than the user who is making the request.” A load shedder is a control loop with a setpoint. It has no incentive properties worth reasoning about because it is not allocating a scarce good among competing claimants; it is refusing work to protect a resource. Analysing it as a mechanism produces sophisticated answers to a question nobody asked. The test: if you would apply the same limit to a single trusted internal caller with no competitors, it is overload protection.

When there is genuine competition among self-interested tenants for a shared pool, mechanism thinking pays. That is the DRF setting — a cluster scheduler dividing CPU and memory among teams that would each happily take everything. Here the properties are worth the effort, and DRF is the right default for multi-resource allocation because it is the only known policy holding all four of sharing incentive, strategy-proofness, envy-freeness and Pareto efficiency in the divisible model.

When the resource is single-dimensional and the identities are trusted, use weighted fair queueing. It is work-conserving (unlike a hard quota), it gives isolation, and it is decades-proven. Add shuffle sharding when the flow count exceeds the queue count, as Kubernetes does.

When you can charge, charge. A posted price is the simplest strategy-proof, sybil-resistant, work-conserving allocation rule in existence, and Approximate and Simple Mechanisms documents why simple pricing so often beats optimal mechanism design in deployment: it is easy to explain, robust to distributional assumptions, and needs no report from the client. Metered billing is a rate limiter whose enforcement is a bill.

When you cannot charge but need truthful demand reports, restrict the domain. DRF’s trick — Leontief demand vectors — is generalizable advice. Narrow what clients are allowed to say until a truthful rule exists on that narrow space.

When identities are cheap and the pool is public, give up on fairness and buy sybil-resistance elsewhere. Proof-of-work, CAPTCHAs, phone or payment verification, and account age all implement Douceur’s resource challenges. The rate limiter downstream of them can then be simple.

Production Notes

Stripe runs four limiters, and only one of them is about fairness. The request rate limiter (N requests per second per user, implemented as a token bucket in Redis, one bucket per Stripe user) “has rejected millions of requests this month alone, especially for test mode requests where a user inadvertently runs a script that’s gotten out of hand.” The concurrent request limiter caps in-flight requests — “You can only have 20 API requests in progress at the same time” — and fired on about 12,000 requests in the same month. The fleet usage load shedder reserves a percentage of the fleet for critical methods. The worker utilization load shedder, “the final line of defense,” splits traffic into four categories and sheds test-mode traffic first; it rejected 100 requests that month. The distribution of those numbers is the point: the fairness-shaped limiter fires constantly on accidents, and the emergency mechanisms almost never fire. Stripe’s own recommendation — “Start by building a Request Rate Limiter” — is advice to build the crude thing first, and it is correct.

Stripe also documents the mechanism-design side effect nobody plans for. The concurrent limiter “asks your users to use a different programming model of ‘Fork off X jobs and have them process the queue’ compared to ‘Hammer the API and back off when I get a HTTP 429’.” Choosing an allocation rule chooses the client architecture your ecosystem will converge on. That is mechanism design whether or not anyone calls it that.

Google Cloud’s quota system is a mechanism whose incentive-alignment layer is the invoice. Quotas are per-project and additive across projects; the friction on creating projects, and the billing account behind them, is what stops the obvious exploit. Note also the honest framing in the docs: quotas exist to “reduce spikes in resource use and availability” and to “protect the community of Google Cloud users by preventing the overloading of services” — overload protection stated first, fairness second.

Kubernetes’ APF is the fullest fair-queueing deployment in mainstream infrastructure, “Stable since Kubernetes v1.29” per the documentation, with the stable API group flowcontrol.apiserver.k8s.io/v1 (checked 2026-08-29). Its concurrency unit is the “seat,” and expensive requests take more than one — a list request is charged seats in proportion to the number of objects it will return, and watch requests are charged for the duration of their initial notification burst. That is cost-proportional pricing inside a fairness mechanism, and it is the correct answer to the “fair per request, unfair per cost” failure mode above. Its borrowing model — priority levels lend and borrow seats against nominal concurrency shares — is a small internal market. Details in API Priority and Fairness.

YARN’s DominantResourceCalculator is DRF in production, and it is @Private @Unstable. The theory shipped; the API contract did not. That is worth noticing when reading claims that DRF “is what YARN uses” — it is one comparator among several, selected by the yarn.scheduler.capacity.resource-calculator property, whose default is verifiably not DRF: CapacitySchedulerConfiguration.DEFAULT_RESOURCE_CALCULATOR_CLASS = DefaultResourceCalculator.class, the memory-only comparator (CapacitySchedulerConfiguration.java line 233, rel/release-3.4.1). Multi-resource DRF in YARN is opt-in.

The Limits of the Analogy — Read This Before Applying Any of It

The MOC asks for the boundary of this framing, and it is a real boundary.

Most rate limiting is not allocating a scarce good. It is refusing work to protect a component. There is no welfare function, no competing claimants, and no strategic agent — just a service with a saturation point and a valve upstream of it. The correct model is a control loop or a circuit breaker, and every property in this note is irrelevant to it. A limiter on a single-tenant internal service is not a mechanism in any useful sense.

The strategic agents are usually not strategic. The overwhelming majority of 429s are bugs: a retry loop with no ceiling, a pagination loop that never terminates, a cron job that fired twice. Modelling these as utility-maximizing manipulation over-intellectualizes a while(true). Mechanism design earns its place when there is a repeated, informed, self-interested counterparty — a paying customer with an incentive to extract more, an internal team competing for cluster share, an adversary. Below that bar, the right investment is better client libraries.

Strategyproofness is often not worth its price. Parkes, Procaccia and Shah proved you give up an Ω(m) factor of social welfare for it, and that the loss is unavoidable for any mechanism satisfying sharing incentive, envy-freeness, or strategyproofness. If your tenants are trusted colleagues, buying strategyproofness with a factor-of-m throughput loss is a bad trade.

Payments dissolve most of the problem, and most systems can have them. Nearly every difficulty in this note — sybil, priority declaration, retry aggression — is solved by charging. Internal platforms usually can charge, in showback or chargeback if not in currency. The reflex to build a clever fairness algorithm instead of a simple accounting one is often the wrong reflex.

The framing earns its keep in a narrow band: multi-tenant systems, with tenants who are informed and self-interested, competing for a genuinely scarce shared pool, where the operator cannot or will not price it. That band contains cluster schedulers, LLM serving fleets, public API platforms, and shared control planes. It does not contain most rate limiters.

vault

Explorer

Rate Limiting as a Mechanism

Rate Limiting as a Mechanism

Mental Model: Three Layers, Only One of Which Is the Algorithm

The Four Questions to Ask of Any Limiter

Max-Min Fairness Is an Allocation Rule, and It Was Attacked in 1989

Dominant Resource Fairness: The One Rigorous Success

The worked example, step by step

What is actually proved, and under what assumptions

Where DRF’s strategyproofness stops

Identity-Splitting Is the Central Attack

The auction-theoretic result that transfers

Why detection is not the answer

The three production patterns, verified

Priority Is a Scarce Resource That Clients Are Asked to Declare for Free

Retries: A Mechanism That Rewards Defection

Schemes Compared by Incentive Property

Failure Modes and Gotchas

Alternatives and When to Choose Them

Production Notes

The Limits of the Analogy — Read This Before Applying Any of It

See Also

Graph View

Table of Contents

Backlinks