Sybil Proofness in BRACE: A Mathematical Analysis of Sybils in Competitive Combinatorial Exchanges

This exposition is for quick feedback and sanity checks before I conduct more research and finally write the paper. I have made some strong claims without formally writing out proofs and tried to stay true to just the results. Feedback should be sent to contact sources listed on my website.

I recently dove deep into the Sybil Proofness rabbit hole while also reading an amazing paper called “Competitive Combinatorial Exchanges” by Jantschgi et al.

This gave me the idea to give myself an exercise to try and attack this market “for fun and profit” (as ironically introduced by Qin et al.) using the intuition I picked up from the literature.

This blog post documents that exercise. I’ve tried to keep things (in)formal enough to be readable, but also rigorous enough that a researcher familiar with market design or cryptoeconomic security will find the arguments meaningful. A detailed research paper will come out with the same results soon.

If you aren’t familiar with this area, the BRACE paper itself does an excellent job explaining the economic motivation behind these ideas. Here, I’ll give a compact overview for those who just want a tl;dr of this blog. For our non technical friends,

We study the behavior of BRACE (Budget Relaxed Approximate Competitive Equilibrium) in economies where principals may deploy arbitrarily many Sybil identities. We find that BRACE remains fair and well-behaved even when Sybils appear, but prices and allocations shift proportionally to the number of fake identities. An interesting finding is that BRACE is stable to small attacks but cannot fully prevent strategic manipulation if a single actor controls many identities.

And for our technical peeps,

Modeling Sybils as a perturbation of the type-distribution (principal utility distribution), we establish that BRACE remains well-defined, preserves -approximate clearing and maintains ordinal welfare guarantees but induces price deviations of order , where is the Sybil infiltration rate. We further show that honest-agent welfare degrades at most linearly in under Lipschitz preferences, while strategyproofness-in-the-large (SP-L) fails whenever any principal controls a non-vanishing identity mass.

Introduction

The Budget Relaxed Approximate Competitive Equilibrium (BRACE) mechanism is a recently developed allocation rule designed for markets where:

  • goods are indivisible,
  • agents only have ordinal preferences,
  • endowments or rights are lottery-valued,
  • the system must respect hard capacity constraints,
  • and equilibrium must exist even when classical competitive equilibrium fails.

BRACE introduces a tiny random budget relaxation, which transforms non-convex demand (caused by indivisible goods) into convex demand in expectation. This small twist is pretty awesome as it restores the existence of equilibrium, while preserving fairness and efficiency guarantees.

Before entering the technical definitions, let’s motivate why BRACE is necessary with a simple example.

A Motivating Example

Imagine a platform that needs to allocate two indivisible compute slots, such as two GPU time windows. These slots cannot be split or shared i.e each can only go to a single user, so the platform faces a simple but rigid capacity constraint.

Assume that one unit of Slot A and one unit of Slot B are available in this round. Three users (agents) are competing for these resources and each has straightforward ordinally ranked preferences over the possible outcomes. Agent 1 most prefers to receive Slot A, would accept Slot B if A is unavailable, and considers receiving nothing as the least desirable option. Agent 2 has the exact opposite priorities: they most prefer Slot B, then Slot A, and finally nothing. Agent 3 is less discriminating; they strictly prefer receiving either slot over receiving nothing, but they have no preference between A and B i.e they value both equally.

To make the scenario realistic, assume that the platform uses lottery based priority rights to decide how much “purchasing power” or entitlement each agent brings into the round. Notice that systems like blockchain mempools, priority auctions, and repeated matching platforms sometimes use randomization to allocate rights over time in a fair way. In this example, Agent 1 has a chance of being endowed with Slot A from prior rounds, Agent 2 has a chance of being endowed with Slot B, and Agent 3 arrives with no endowed rights at all. These endowments are probabilistic which creates uncertainty about who can feasibly acquire which slot.

One might hope that a competitive equilibrium (defined as a set of prices for the two slots under which each agent selects their preferred affordable option and markets clear) could resolve the allocation. However, the classical equilibrium framework breaks down almost immediately.

Because the compute slots are indivisible, agents cannot choose fractional bundles to smooth out their choice. They must either take or leave an entire slot. Preferences are also purely ordinal, meaning agents can rank outcomes but cannot express precise tradeoffs between them. Combined with stochastic endowments, this makes their budget sets irregular and discontinuous. Moreover, both Agent 1 and Agent 2 have such strong preferences that, even at very high prices, they might still demand the same slot which causes non-convex demand, something classical equilibrium theory cannot handle. As a result, there may be no set of prices that simultaneously respects agents’ preferences, budgets, and the capacity constraints of the two slots.

Therefore, in markets with indivisible goods, ordinal preferences, and lottery-based endowments, the standard competitive equilibrium tools simply do not work. The mathematical conditions needed for equilibrium such as convex demand, continuous excess demand, and feasible clearing can all fail simultaneously, even in very small markets. It is precisely these kinds of environments that motivate the development of mechanisms like BRACE.

Relevant markets where BRACE is applicable

BRACE is especially relevant to markets with indivisibilities, ordinal input formats, and probabilistic rights. Concrete examples:

  1. Mempool / Blockspace Priority Allocation.
    • Goods: discrete blockspace slots or inclusion slots in a block.
    • Agents: transaction senders with priority credits (e.g., past fee rebates, reputation lotteries).
    • Endowments: lottery rights from previous rounds (e.g., rollovers of priority).
    • Why BRACE fits: blockspace is indivisible at transaction level; ordinal preferences (urgency ranking) and probabilistic queue-crediting are common.
  2. Priority Gas Auctions / Sequencing Rights.
    • Goods: positions in a transaction sequence or execution ordering (finite discrete slots).
    • Agents: MEV relayers, proposers, sequencers with ordinals on positions and stochastic entitlements.
    • Why BRACE fits: discrete ordering, ordinal valuation of positions, randomized entitlements (e.g., proposer rotations).
  3. Validator Slot / Committee Assignment Markets (staking ecosystems).
    • Goods: validator committee seats or ephemeral slots for processing blocks.
    • Agents: validators or delegators with probabilistic staking rewards as endowments.
    • Why BRACE fits: seats are indivisible; priority is sometimes allocated via lotteries or stake-based sampling; fairness and security constraints are central.
  4. Decentralized Exchange (DEX) Matching with Bundle Constraints.
    • Goods: discrete fill-quantities in combinatorial trades or batched auction slots.
    • Agents: liquidity takers and makers who hold lottery-like rights (e.g., LP coupons).
    • Why BRACE fits: combinatorial bundles and indivisible order blocks with ordinal preferences over execution patterns.
  5. Off-chain / Layer-2 Resource Scheduling.
    • Goods: finite scheduling slots for compute or storage; agents have priority tokens minted via on-chain events.
    • Why BRACE fits: allocation must be fair, respects caps, and often uses ordinal priority signals.

In each of these settings the common features are discrete resources, ordinal inputs or coarse preference information, and probabilistic or history-dependent endowments. Now that we have touched upon the usefulness of BRACE, let us introduce the mathematical model to describe BRACE rigorously.

BRACE Model

Notations

Following the original paper closely, we introduce some notation:

  • Let be the number of distinct indivisible resource types (goods).
  • Let denote the capacity vector: copies of good are available.
  • Let denote the finite set of feasible bundles (multisets of goods). We write a bundle as , where is the number of copies of good in bundle . We assume .
  • Let be a finite set of identities (agents as reported to the mechanism). The BRACE model will later allow augmentation with Sybils (for now we write ).
  • For each identity :
    • denotes the set of acceptable bundles for .
    • denotes the set of probability distributions (lotteries) supported on . We identify each lottery with a vector (probability mass function on ).
    • denotes the endowment lottery of : a (possibly degenerate) random bundle that initially holds.
    • is a weak order (complete and transitive) on ; agents rank lotteries (ordinal preferences). We assume admits a stochastic-dominant representation when required or else we treat abstractly.

The economy is

All randomness is over lotteries and budget-relaxation draws. When we write it integrates over endowment realizations, budget-relaxations, and any mechanism-level randomization. The BRACE paper’s formal definitions also appear in the original paper (Definitions 4–6, Propositions 1–2) although the author’s notations differ a bit from my own.

Prices and normalization

  • Let prices be a vector .
  • Normalize prices onto the simplex:
  • For a deterministic bundle , define .
  • For a lottery , define the price-value:

Budgets and -relaxation

  • Under price , agent ’s nominal budget is
    Since is a lottery, may be random.

  • Fix . BRACE introduces a budget-relaxation random variable drawn i.i.d. from a distribution supported on a small simplex.

  • The relaxed budget is

Taking recovers the tight-budget setting where equilibrium generally fails to exist.

Demand correspondence

For fixed prices and realizations :

  • The feasible set of lotteries is:

  • The demand correspondence is:

Regularity properties from BRACE:

  • is nonempty for all .
  • is upper hemicontinuous in when budgets include .
  • Lotteries + budget-relaxation smooth out non-convexities from indivisible goods.

Aggregate expected demand and -clearing

  • Aggregate expected demand for good :

  • Excess demand:

  • -approximate clearing condition:

Definition: -BRACE

A pair is a -BRACE allocation for economy if:

1. Each agent selects a most-preferred affordable lottery:
2. Prices satisfy the -clearing conditions.

Notice that BRACE defines an equilibrium in expectation: the are random lotteries, and clearing is applied to expected aggregate demand. Refer to the original paper for the best way to get first hand feel for these definitions.

Some Theoretical Facts about BRACE

  • Existence (Proposition 1).
    For any finite economy and any , a -BRACE exists.

  • Welfare & fairness (Proposition 2).
    Every -BRACE is:

    • individually rational,
    • ordinally efficient w.r.t. ,
    • endowment-monotone,
    • identity-level justified-envy-free.

These are proven in the original paper.

Now that we have developed a formal model for BRACE, let us get down to business.

A Sybil Attack on GPU Slot Market

To see how Sybil identities can distort allocations in a BRACE market, return to the GPU-slot example with two slots, A and B, and three honest agents. Agent 1 prefers A over everything else and has a chance of already owning A. Agent 2 prefers B and has a chance of owning B. Agent 3 is flexible and just wants any slot. In this small, balanced market, BRACE sets prices roughly evenly where Slot A and Slot B end up with similar equilibrium prices because demand is symmetric. Each agent receives a fair lottery allocation based on their preferences and endowments.

Now imagine that Agent 1 is actually a strategic principal who creates five fake Sybil identities. Each Sybil pretends to be a new user who desperately wants Slot A and reports a preference ranking of A > (everything else) > nothing. None of these Sybils come with any initial endowment. Before the attack, only one out of three agents strongly wanted A and after the attack, six out of eight identities suddenly claim that A is their top choice. From the perspective of the BRACE mechanism, which only sees identities and their reported types, this looks like a dramatic surge in demand for Slot A.

BRACE responds to this new apparent demand by raising the price of Slot A relative to Slot B. Before the attack, Slots A and B may have been roughly equal in price; after adding the five Sybils, Slot A might become, for example, 30–40% more “expensive” in the price simplex. BRACE also reallocates expected demand accordingly: more of the scarce budget slack now flows into the A side of the market, matching the fact that most identities claim to want A first.

Notice that this artificial price increase benefits the attacker. The principal’s real endowment which was a genuine 50% probability of owning Slot A, becomes more valuable when Slot A rises in price. Even if the Sybils themselves receive no actual compute time, their presence helps inflate the market value of the principal’s real asset. When the Sybils cost nothing to create, the principal can use them as “gravity wells” that pull the equilibrium toward one side of the market.

Formal Modelling of Sybil Attack in BRACE

Assumptions (for perturbation method)

Before we start the actual derivation, We lay down some assumptions. To derive stability bounds, we typically assume the following:

  • Finite bundle system: finite, .
  • Bounded budgets: uniformly bounded; supported in an simplex.
  • Lipschitz aggregate demand: is Lipschitz in the population type measure.
  • Lipschitz indirect utilities: A cardinal utility representation consistent with yields Lipschitz .

These assumptions appear implicitly in BRACE’s continuity and fixed-point arguments.

Principals and Sybil Identities

Definition 1 (Principals)

Let be the set of principals i.e real economic actors. Each identity belongs to exactly one principal through a mapping

Definition 2 (Sybil Identity)

An identity is a Sybil if

Let and define the Sybil infiltration rate

Definition 3 (Sybil-Augmented Economy)

Given the original economy , the Sybil-augmented economy is

A principal selects for each of its identities.

BRACE in the Sybil Economy

A -BRACE in consists of:

  • price vector
  • budget relaxations
  • random allocations

Recall in context:

Expected excess demand:

BRACE clearing requires

Theoretical Results

Existence Under Sybils

For every , the Sybil-augmented economy admits a -BRACE.

Proof.
From the paper, the BRACE existence theorem holds for all finite economies. Sybil augmentation preserves finiteness.

ON THE SIDE: What if finiteness condition was broken? It will affect our proofs adversely. Napkin math gives : So If a principal creates infinitely many Sybils with identical types, then no price vector can satisfy the -clearing conditions. This unsurprisingly implies that the first defense is to make sybils costly to create.

Welfare Validity Under Sybils

Every -BRACE in is individually rational and ordinally efficient w.r.t. .

Proof. Direct from Proposition 2 of the BRACE paper.

Price Perturbation Bounds

Let be the empirical type distribution in the honest economy, the Sybil-perturbed distribution. Let and denote the corresponding -BRACE prices.

We strengthen the previously stated result.

Assumptions

  1. finite with .
  2. Lipschitz excess demand: for some , for all in the simplex.
  3. Jacobian nondegeneracy: the differential of excess demand at equilibrium satisfies

Sybil–Price Stability Bound

There exist constants and such that for all ,

Proof

We supply a proof using perturbation of roots (took a while to deal with).

Let
The BRACE clearing condition requires .

By assumption,

Consider a first-order expansion around : where .

Since , rearrange:

Invert using assumption 3:

Taking norms:

Since ,

Thus, for , for sufficiently small .

Honest Welfare Bounds

Let the indirect utility of an honest identity be .

Yet Another Assumption

Each is -Lipschitz:

Let be the total welfare of honest agents.

Honest Welfare Loss Bound

For sufficiently small ,

Proof

Using Lipschitz utilities and Price Stability Bound,

Summing over honest identities:

Therefore, in the presence of a small perturbation , the honest agents’ total welfare will only decrease by a small amount, proportional to the size of the perturbation constants.

Incentives and Failure of Strategyproofness in the Large (SP-L)

Now to deal with the strongest result. Define , the set of identities belonging to principal .

Necessary and Sufficient Conditions for SP-L

BRACE is strategyproof-in-the-large iff

Proof

( necessity)

Suppose some principal has .
Manipulating the types of identities changes the empirical distribution by so by Stability Bound: Thus the principal can change prices by a non-vanishing amount thereby violating negligible influence.
Hence SP-L fails.

( sufficiency)

If then every principal affects the empirical distribution by , implying via Stability Bound that which is exactly the negligible-influence condition under which SP-L holds (BRACE Theorem 4).

Therefore, BRACE is strategyproof-in-the-large exactly when no single principal can control a significant fraction of identities. Large numbers dilute influence and ensures negligible impact and no incentive to misreport.

Principal Fairness

Identity-level Justified Envy-Freeness (JEF) does not imply principal-level fairness.

Principal-Level JEF Failure

There exist economies and principals such that:

  • every identity satisfies identity-level JEF
  • but at principal level:

Proof

Construct a principal with many Sybils whose endowments are negatively correlated, while another principal holds a single identity.

BRACE allocations are JEF for each identity, but principal can aggregate into a diversified portfolio with lower variance.

Since BRACE fairness is defined on identities, the aggregation step is outside the mechanism’s fairness guarantees.

Thus may dominate in every JEF comparison.

Incentive Compatible Sybil-Proofness Bounds

Here give explicit bounds on how much a principal can gain by injecting Sybils.

Let the Sybil-augmented distribution be

Let be the BRACE price.

Define the principal’s utility:

Marginal Sybil Incentive Bound

For sufficiently small ,

Proof

By chain rule,

Use Lipschitz gradient bound:

Use Stability Bound:

Thus

Hence a corollary

Sybil Proofness at Rate

If a principal controls Sybils, the maximum gain from Sybil creation is:

Therefore, the additional utility a principal can obtain by creating Sybils is at most , growing linearly with the number of Sybils.

A Stronger Impossibility Result

Continuing from the above, we provide a new result: unless BRACE is modified, no competitive equilibrium with indivisible goods can be Sybil-proof beyond linear order.

No Better Than Sybil Resistivity

For any -BRACE mechanism and any , there exist economies where a principal can achieve welfare gains , and no mechanism satisfying BRACE axioms can reduce this below .

Proof (Sketch)

The tightness of Stability Bound follows from a first-order perturbation lower bound:
for some whenever the principal’s Sybil strategy induces type variation of order .

Utilities then shift by under Lipschitzness.

Thus is both upper and lower tight.

An Ambitious Attempt at Distributional Sybil-Proofness

I also played around and thought to try and derive a measure-theoretic condition for full Sybil-proofness.

Let the type distribution be absolutely continuous w.r.t. a reference measure with density .

Radon–Nikodym Sybil-Proofness Criterion

BRACE is Sybil-proof iff every principal’s manipulation satisfies:

Proof

( ) If the equality holds, the empirical distribution does not change, implying .

( ) If the densities differ on a positive-measure set, then , implying by Stability Bound that , hence a profitable deviation exists.

This result shows that BRACE’s Sybil-proofness is equivalent to the empirical distribution of principals remaining exactly unchanged under manipulation. Mathematically, it’s elegant because it reduces a strategic, combinatorial attack resistance to a precise condition on Radon–Nikodym derivatives. I am personally obsessed with this since it links mechanism design directly to measure theory.

Conclusion

Now as usual I will let ChatGPT give you all a nice send off:

In this article, we extended the BRACE framework to economies in which principals may replicate themselves through Sybil identities. We began by formally distinguishing between identities and principals, and by allowing each principal to choose arbitrary preference and endowment types for the identities it controls. Within this augmented model, we proved that the core structural guarantees of BRACE—existence, individual rationality, ordinal efficiency with respect to , and identity-level justified-envy-freeness—continue to hold. This follows from the fact that BRACE requires only the finiteness of the population and the regularity induced by lotteries and budget-relaxations; Sybil augmentation preserves these properties.

The main contribution of our analysis lies in quantifying the sensitivity of BRACE prices and allocations to Sybil infiltration. By studying the BRACE fixed-point map under perturbations of the empirical type distribution, we established linear price-continuity bounds: if Sybils constitute an -fraction of the population, the induced equilibrium price vector satisfies Under mild Lipschitz assumptions on indirect utilities, this yields correspondingly linear distortions in honest-agent welfare. These results highlight a key dichotomy: BRACE is stable under small identity perturbations, but not robust to adversarial manipulation when a principal controls a non-negligible portion of the population.

Our analysis further revealed two structural limitations. First, BRACE is not strategyproof-in-the-large when any principal’s share of the population is bounded away from zero; such principals can manipulate the empirical type distribution sufficiently to affect the BRACE fixed point. Second, BRACE’s fairness guarantees apply at the identity level, not the principal level. Once individual allocations are aggregated back to principals, justified-envy-freeness may fail, providing avenues for unfair advantage through identity replication.

Would love thoughts, comments and suggestions.

I have been Abhimanyu Nag

No comment found.

Add a comment

You must log in to post a comment.

Follow