Exploring the second part of the Theory of MEV. :D

Blockchain systems rely on decentralized networks of participants to maintain a global shared state and execute transactions (in the case of ethereum, validators). A core challenge is dealing with varying incentives and strategic behavior by different network participants. In particular, validators who produce blocks have temporary power to reorder or include transactions, enabling profit at the expense of others. This phenomenon of excessive profits extractable by temporary inclusion monopolists by reordering or inserting transactions is known as Maximal Extractable Value (MEV).

In an earlier work, “Towards a Theory of MEV I,” Kulkarni et al. study the game theoretic properties of MEV, explicitly answering questions about how reordering impacts the price of sandwich attacks and how sandwich attacks affect routing MEV. They find that of reordering MEV, the maximum price impact caused by reordering of sandwich attacks on the order of O(log n) where n is the number of user trades and that in the case of routing MEV, the existence of MEV degrades and counterintuitively improves the routing quality. For a quick recap, you can look at a talk by Tarun Chitra and my blog.

In this blog, I cover the work “Towards a Theory of MEV II: Uncertainty.” While the first paper focused on analyzing MEV for constant function market makers specifically, this work aims to develop a more general theory around payoffs (more on what payoffs are later).

Ultimately, blockchain users encounter a variety of uncertainty; as the image shows, it’s on a spectrum. This article only covers the first part and is about Ordering Uncertainty. Ultimately, MEV can be viewed as sophisticated participants capturing profits from user uncertainty, and one more way of looking at it is capturing profits from user inefficiencies.

This paper provides a quantitative trade-off between the freedom to reorder transactions and the payoffs in decentralized networks. The results can be viewed as an analog of sampling theorems, showing simple rules suffice for simple payoffs, but more complexity is necessary to limit unfairness for arbitrary payoffs. The technical core involves Fourier analysis of the symmetric group, representation theory, and uncertainty principles. These characterize the relationship between sequencing rules, payoff complexity, and fairness guarantees.

Fair Ordering has been introduced as a solution to handle MEV mitigation. These methods propose changing blockchain consensus, forcing validators to adhere to a particular order of transactions. This order can be determined by time or some other rules. One common form of Transaction ordering is FCFS (first come, first serve), where validators note the times of the transactions they receive, and the one that comes earlier appears early in the order as per the fair ordering protocol. In two recent papers, “Order-Fair Consensus in the Permissionless Setting,” Kelkar et al. and “Themis: Fast, Strong Order-Fairness in Byzantine Consensus,” Kelkar et al. propose ways to achieve such fair Ordering.

However, research in social choice theory renders such attempts moot. How? Social choice theory is a field of economics and political science that deals with creating frameworks that explore how individual preferences can be aggregated to make collective decisions. Two important results in Social choice theory make it hard to design universal fair ordering protocols.

The Condorcet paradox demonstrates that majority preferences can be inconsistent under certain conditions because of the intransitive preferences of choices among voters. For example:

Suppose there are three voters - Alice, Bob, and Charlie. They are trying to decide among three options - A, B, and C. Their preferences are:

Alice: A > B > C Bob: B > C > A Charlie: C > A > B

If we tally the votes between each pair of options:

• A vs. B: Alice and Charlie prefer A over B, so A wins 2-1

• A vs. C: Bob and Charlie prefer C over A, so C wins 2-1

• B vs. C: Alice and Bob prefer B over C, so B wins 2-1

So the majority prefers A > B; B > C; C > A

This creates a paradox or inconsistency since transitive logic would require that A > B, B > C, and C > A is impossible.

The Arrow impossibility theorem builds on this idea and makes an even stronger statement about the difficulty of aggregating individual preferences into coherent group choices. In essence, it proves that aggregating individual preferences into a rational collective preference ordering is impossible when there are three or more options and two or more people. This implies no perfect voting system; all democratic voting methods involve trade-offs between fairness criteria. For more on Arrow’s theorem, read this.

Does this mean giving up on any transaction ordering is the only solution? In “Credible Decentralized Exchange Design via Verifiable Sequencing Rules,” Ferreira et al. show that if one aims to design a sequencing rule where the miner can never obtain risk-free profits (risk-free profits meaning the miner is sure to receive some tokens for free), such a goal is unattainable (As far as deterministic sequencing rules are concerned). They also show that some sequencing rules increase social welfare for unsophisticated agents (normal protocol users).

Social welfare functions are mathematical models used to aggregate individual preferences into a single measure that represents the "well-being" of a group. This paper's authors believe that Ordering's impact on AMMs is only possible partly due to the convexity of the payoff function of an AMM. If social welfare functions can restrict orderings to mitigate the adverse welfare effects of MEV, a natural question is, what is a generalized way of constructing such orderings? The authors try to generalize these rules to a larger class of payoff functions.

Formal Definition: The Heisenberg Uncertainty Principle in quantum mechanics is usually stated as follows:

ΔxΔp ≥ ℏ/2 ​

Here, Δx is the uncertainty in position, Δp is the uncertainty in momentum, and ℏ is the reduced Planck constant, approximately 1.054571 × 10^(−34)  m^2kg/s.

In Simpler Words, Imagine you're trying to look at a tiny particle, like an electron, under a super-microscope. The Heisenberg Uncertainty Principle says that you can't know both where the particle is (its position) and how fast and in what direction it's moving (its momentum) with perfect accuracy at the same time. It's like trying to watch a fast-moving hummingbird; if you focus on capturing its speed, you can't pinpoint its exact location, and vice versa.

The uncertainty principle generally states that there are inherent limitations in our ability to measure or know pairs of complementary properties/functions at the same time. The general mathematical form often takes the shape of an inequality, like

where C(f) and C(Lf) are measures of "complexity" or "uncertainty" for a function f and its transformed version Lf, c is a constant greater than zero, and L is the linear transform. This inequality tells us that if one of the measures is small (i.e. if we know one property very precisely), the other must be large enough to satisfy the inequality, meaning the other property cannot be known with arbitrary precision.

In the case of the Heisenberg uncertainty principle, one of the attributes is indeed related to the Fourier transform of the other. Specifically, the position x and momentum p are Fourier transform pairs. In quantum mechanics, the wave function ψ(x) in position space can be transformed into momentum space ϕ(p) using the Fourier transform.

This paper aims to construct complexity measures C representing the fairness of payoff functions f. The complexity measures will connect the sizes of particular subsets of permutations (basically transaction orderings) to C(f). These subsets are outputs of sequencing rules (hence, they also allow us to talk about different “kinds” of orderings in general).

Blockchains are decentralized systems that maintain a sequence of blocks containing state transitions and come to a consensus on a particular state. Each block consists of transactions that mutate the state from the previous block. Users submit transactions via a peer-to-peer network and pay fees to include them in a block. Validators or miners collect transactions, validate blocks, and add these to the global ledger. Validators lock up resources to participate in the overall consensus protocol and are incentivized by fees and block rewards. A key aspect of blockchains is that they allow asynchronous communication about a shared (global) state, with protocols designed to make it costly for validators to deviate from consensus. While adding blocks to the blockchain, a temporary monopoly is given to a single validator in many consensus protocols.

This temporary monopoly of allowing validators to reorder or censor transactions and earn fees and profit from this practice is called Miner extractable value.

This paper assumes that there is a fixed set of transactions T_1, …, T_n and a payoff function f (T_1, …, T_n) that yields profit to the validator. This paper does not consider the difference between the allocation/split of the profit between the validator and searchers (entities that search for profitable orderings and submit them to the validator).

The payoff function f is a mapping from transactions to a payoff. Since we consider a fixed set of transactions for reordering MEV, the payoff to validators from executing transactions in a particular order can be modeled as a function f that maps permutations of the transaction set to real numbers.

Some notation

• 𝑆ₙ → set of permutations of n elements

• 𝜋 → permutation; 𝜋(i) → index where ith element is moved

The function f: 𝑆ₙ → ℝ is a payoff function that takes a transaction ordering and gives a payoff. Concretely, for a function g: 𝑇ⁿ → ℝ, we have

The Ordering is the optimal monopoly profit achievable via reordering MEV. Here, the max denotes the permutation out of the set of permutations of n transactions that gives us the maximum payoff.

Constant Function Market Makers: Let’s think about the trades in an AMM briefly. Users submit transactions and are then added to a block. How is MEV extracted around these? Sandwich attacks are the most common form of MEV extraction. In a sandwich trade, an order is placed before and after the submitted transaction by the user, and the slight price difference (impact) is booked as the profit. The order in which user trades are executed changes the profitability. So, the payoff function f(π) depends on the permutation π of user trades.

The payoff function for CFMMs is given by:

𝜟_i denotes the transaction by the user, and p_i is the price obtained after the execution of the user transaction. This payoff is not permutation invariant. Some permutations are clearly better than others.

Liquidations: Liquidations allow protocols to close positions that have become undercollateralized due to price changes. For example, a user borrows asset Y by posting asset X as collateral at an initial price ratio of p0. If the price of X in terms of Y later drops to p* (the liquidation price), liquidators can profitably close the position.

Liquidation is generally very permutation sensitive, i.e., for some orderings (maybe even most), there might not be a liquidation at all. For a permutation π of trades, define pi(π) as the price after trades π(1),...,π(i) have executed. Some permutations will not reach the liquidation price threshold, while others will.

Let A be the liquidatable set:

where p_i(π) is the price after executing 𝜟_π(1)…𝜟_π(I) and p_0 - c is the liquidation threshold. As we noted, some permutations don’t reach the liquidation threshold.

The liquidation payoff function is:

Where 1𝐴(π) is an indicator function that equals one if π is in set A and 0 otherwise, intuitively, it’s like choosing the permutations that liquidate the position.

Generally, we can use liquidations and auctions to construct any payoffs in the form of 1𝐵. Here

Where the summation is overall A ⊂ 𝑆ₙ, and f^(A) are the coefficients.

So, any payoff function f can be written as a linear combination of liquidation payoff functions 1𝐴. In this sense, the liquidation payoffs 1𝐴 form a basis for the set of functions f: 𝑆ₙ -> ℝ. (Similar to a basis for Vector spaces ^_^)

Now that we have established Ordering and payoffs, we move to fairness functionals. These are ways of measuring the fairness of an ordering scheme since we might want to talk about how certain orderings are fairer than others.

Given a payoff function f: 𝑆ₙ -> ℝ, we aim to measure the "fairness" of an ordering scheme that generates a set of orderings, i.e., a set A ⊂ 𝑆ₙ of valid orderings.

A global fairness function is defined as a map: 𝐿¹(𝑆ₙ) -> ℝ, which takes a payoff of a set of transactions and returns the difference (deviation) between the maximum payoff and the average payoff.

A short deviation into L1 norms:

In mathematics, the L1 norm is a way to measure the "size" of a function. For a function that takes in values and spits out numbers, the L1 norm sums up the absolute values of the function over its entire input domain.

For example, suppose we have a function f that takes in integers as input and outputs numbers. The L1 norm of f, written ||f||1, is defined as:

||f|| = sum of |f(x)| for all integer inputs x

Where |f(x)| is the absolute value of f(x).

So if f(1) = 3, f(2) = -2, and f(3) = 5, then the L1 norm of f is:

||f|| = |3| + |-2| + |5| = 10

The L1 norm captures the maximum magnitude the function f reaches over all inputs.

Now, in the context of the paper, The payoff function f maps permutations of the transaction set to real numbers.The L1 norm ||f|| sums the absolute values of f over all possible input permutations.

||f||_∞ refers to the L∞ norm, also called the supremum norm, defined as:

||f||_∞ = maxπ |f(π)|

So, the L∞ norm takes the maximum absolute value of f over all permutations π.

||f||_1 refers to the standard L1 norm, defined as:

||f||_1 = ∑π |f(π)|

So, the L1 norm sums the absolute values of f over all permutations.

The key difference is:

• The L∞ norm ||f||_∞ takes the maximum value

• The L1 norm ||f||_1 sums all values

For some more intuition on L_1 norms and more, check this out.

One can think of two natural global fairness functionals: the difference between the maximum and average and the multiplicative difference, which would quantify the magnitude of the maximum payoff in terms of the average. So we have:

1. 𝜦⁺Measures additive unfairness: - Defined as the difference between the max and average payoff of f over A, it captures the additive gap between best and typical case.

2. 𝜦*: Measures multiplicative unfairness: - Defined as the ratio between the max and average payoff of f over A, it Captures the multiplicative gap between best and typical case.

We move ahead with using 𝜦⁺ because it’s neater to work with and has some desirable properties.

So when 𝜦⁺(f) = 0, this would mean that the difference between the maximum payoff possible and the average payoff possible is 0. We can interpret this as being perfectly fair. Maximal unfairness occurs when f = 1π for some π, saturating the upper bound. Intuitively, this payoff function f = 1π returns one only for a single "jackpot" permutation π and 0 for all other inputs.

Now that we have defined these things in the global set of orderings, we will restrict them to the subset A ⊂ 𝑆ₙ (in some, localize them to a subset of the larger space we just explored)

In an earlier paper, “Towards a theory of MEV: CFMMs,” the authors show that 𝜦*(f) = O(log n), given sufficient liquidity, basically as long as there’s enough liquidity, the worst case payoff only grows logarithmically in comparison to the average case in the case of constant function market makers.

So, we now have fairness functions that measure the gap between optimal and average payoffs under a set of allowable permutations. Relating the permutation set restrictions to the complexity of the payoff function yields both upper and lower bounds on the fairness functionals. These characterize the relationship between sequencing rules, payoff complexity, and fairness guarantees.

This defines the localized fairness functional 𝜦⁺(f, A) for a payoff function f and a set of permutations A.

Specifically:

• max_π∈A f(π) is the maximum payoff achievable over all permutations π in the set A. This represents the optimal strategy for an extractor trying to maximize their profit.

• E[f1𝐴] is the expected value of f over the uniform distribution on A. 1𝐴 is the indicator function equal to 1 for π ∈ A and 0 otherwise.

• Their difference maxπ∈A f(π) - E[f 1𝐴] measures the gap between the best and average cases for f when restricted to A.

Rearranging, we find that 𝜦⁺(f, A) can be written in terms of 𝜦*( f, A); we will first construct a bound for 𝜦* and then bound 𝜦⁺ with it. Again, bounding this means we are trying to find how fair a certain set of orderings is.

This section introduces mathematical tools to analyze how much the maximum and average payoffs of a function f can differ. If we only have black-box access to f: 𝑆ₙ -> ℝ, how can we determine if the max and expected values deviate?

We saw in the liquidation example that any payoff can be constructed as the sum of indicator functions. We want to know within this set of “basis”/indicator functions which influences the payoff function f.

How could we go about doing this? One way to do this is if we could magically decompose every payoff f: 𝑆ₙ -> ℝ into a sum of indicator functions and then measure the size of the coefficients.

Recall the equation for the construction of any payoff

Here, f̂(A) are the coefficients of the indicator functions, and quantifying them would tell us which subset of the Ordering contributes most to the payoff function.

We first try to establish this for the construction of payoff that we’ve already seen; since we can construct payoff functions of any kind if the form is 1𝐵, we explore various properties. But since this form, 1𝐵, does not capture all the payoff types; we then look at other methods, which let us talk about the generalized form of payoff and then explore their properties.

A very brief look into what these are.

The Fourier Transform is a mathematical tool that decomposes a signal (or function) into its constituent frequencies. Imagine you have a complex sound wave; the Fourier Transform helps you determine what "pure tones" (sine and cosine waves) make up that complex sound.

The Fourier Transform of a function f(t) is given by

Here, F(ω) tells you the amplitude and phase of the sine and cosine waves at each frequency ω that, when added up, reconstruct f(t). The Fourier Transform takes you from the time domain (where you describe signals as functions of time t) to the frequency domain (where you describe signals as functions of frequency ω).

Imagine you're listening to an orchestra. Your ear receives a complex mixture of sounds from various instruments, each playing at different frequencies. The Fourier Transform is like having the superpower to instantly "hear" each individual instrument's pure tone, separating it from the orchestra's collective sound. Later, you can combine these unique tones to recreate the original complex sound of the orchestra.

The Fourier Transform breaks down complex signals into their basic frequency components, much like identifying individual instruments in an orchestra. It's a way to move from the time domain, where you see how a signal changes over time, to the frequency domain, where you know what frequencies make up that signal.

Fourier Walsh Transform: The Fourier-Walsh Transform is a specialized form of the Fourier Transform that uses Walsh functions instead of the usual sine and cosine functions as the basis set. Walsh functions are piecewise constant functions that take on values of +1 or -1, making them particularly well-suited for digital or binary signals.

Although the Discrete Fourier Transform (DFT) already exists as a discrete analog of the continuous Fourier Transform. The Fourier-Walsh Transform serves a different purpose and is tailored for different kinds of data. While the DFT is a discrete analog of the Fourier Transform for sampled, continuous signals, the Fourier-Walsh Transform is a specialized discrete analog for Boolean functions and binary signals.

If f were a boolean function, f:{-1,1}ⁿ → ℝ, then the expansion

It is called the Fourier-Walsh transform.

Where 1_A(x) = 1 if x_i = 1 for all i in A, and 0 otherwise and the f̂(A) are called the Fourier coefficients and quantify the influence of the set A on the function value. The Fourier-Walsh transform helps us prove statements that tie the global behavior of the function f to properties about the sets A that it is supported on. If A has a small size but a large f̂(A), then the variables in A have an outsized influence on f.

We can thus interpret the relationship between |A| (the size of the set) and f̂(A) (the magnitude of the coefficients) as seeing how flat or sharp the function is.

The Plancherel theorem for the Fourier transform has a vital significance: it relates the overall "size" of a function f to the sizes of its Fourier coefficients f̂(A). There is a Plancherel theorem relating the L2 norms of f and its Fourier transform:

This means the L2 norm of f (its "energy") equals the L2 norm of its Fourier transform f̂. Intuitively, if a small number of Fourier coefficients f̂(A) contain most of the L2 norm of f̂, then the function f is mainly influenced by those sets A. For example, if 90% of Σ_A |f̂(A)|^2 comes from 5 sets A, we can say f "mostly depends" on just those five sets. In transaction orderings, the Plancherel theorem allows us to identify which sets of permutations A significantly influence the payoff function f. If the payoff depends heavily on just a few sets of orderings A, we can design sequencing rules or auctions to preserve those orderings. So basically, the Plancherel theorem lets us quantify which orderings matter most for the payoff f. It provides a precise way to measure how much freedom is needed in the allowable orderings A to capture the behavior of f.

We now define the boolean degree deg(f) is defined as:

For boolean functions f: {-1,1}ⁿ → ℝ, the boolean degree deg(f) measures the size of the largest input subset that significantly influences f. It is defined based on the Fourier-Walsh decomposition. Large Fourier coefficients on small sets ⊆ [n] indicate that f depends strongly on those inputs.

T measures the size of the largest set A that influences f. We can also define the degree-t part f_≤t as:

So f_≤t restricts f to sets A of size ≤ t. The degree gives a precise way to measure how "complex" a boolean function is.

Now that we have established all the properties we are interested in for the indicator function, we look at more generalized payoffs.

The symmetric group 𝑆ₙ:

• This contains all possible permutations (orderings) of n elements.

• For transaction orders, Sn would be all possible orderings of n transactions.

• The size of Sn is n! (factorial of n).

In the case of abelian groups, indicator functions can often be represented as vectors because the group operation is commutative. However, the non-commutativity complicates things for non-abelian groups like the symmetric group. Here, a more complex representation is needed, and that's where matrices come in.'

Therefore, instead of having indicator functions 1A:{-1,1}ⁿ → ℝ, we have representations. A representation of a group G is a way to represent the elements of G as linear transformations on a vector space V. Intuitively, it shows how G acts on V.

A representation ρ of 𝑆ₙ:

GL(V^d) is the general linear group of invertible matrices acting on a vector space V of dimension d.

Irreducible representations are the basic building blocks - they cannot be decomposed into smaller representations. It is a fact that finite groups have a finite number of irreducible representations. Representations will serve as the analog of indicator functions for non-abelian groups.

The Fourier transform and representation theory allows analyzing functions on non-commutative groups like Sn analogously to Fourier analysis of processes on Rn. The Fourier transform f̂(ρ) of a function f: 𝑆ₙ -> ℝ is given by

The Fourier transform decomposes a function f: 𝑆ₙ -> ℝ into irreducible representations. The λth Fourier coefficient fˆ(ρλ) is a matrix capturing how f acts on Vλ. Note that this is a sum of matrices.

As we saw earlier, we have a planche rel theorem in this case, too, defined by

To define the boolean degree, we need an analog, though. Ultimately, the boolean degree in the indicator function case gave us an idea of how much influence the largest subsets of inputs had on f. In this case, we need a better way of talking about the representations of 𝑆ₙ.

Every permutation in 𝑆ₙ​ can be decomposed into cycles. These cycles correspond to partitions of [n], and each partition describes an irreducible representation of 𝑆ₙ. The function f is expanded using the inverse Fourier transform. The sum involves traces of matrices corresponding to irreducible representations, weighted by some degree d.

Where Tr is the matrix trace and dλ = dim(Vλ) is the dimension of ρλ.

It turns out that the set of partitions of [n] serves to index the irreducible representations of the symmetric group 𝑆ₙ. The representations ρ are indexed by partitions λ of n. This is a way to express functions on 𝑆ₙ in terms of invariant basis functions under certain permutations. This set is called the Specht module and allows one to decompose 𝑆ₙ.

Thus, the sum in the equation (in the case of expanded f) represents the projection of f to each Specht module.

All of this helps us ultimately to define the boolean degree of this function f, as:

Where λ |- n means λ is a partition of n. Where λ1 is the largest part of λ, this measures the complexity of f on 𝑆ₙ.

So, in summary, the Fourier analysis generalizes to non-abelian groups like 𝑆ₙ while still providing ways to analyze the complexity of functions via representations and boolean degrees. The same high-level goals apply regarding quantifying the influence of sets and relating degrees of f and f̂.

Let’s imagine a small example:

Suppose we have n=3 transactions in our blockchain: A, B, C.

The symmetric group S3 would contain all possible orderings of these three transactions:

S3 = {ABC, ACB, BAC, BCA, CAB, CBA}

So S3 has size 3! = 6.

Now suppose our payoff function f assigns a profit to each Ordering:

f(ABC) = 6 f(ACB) = 2 f(BAC) = 3 f(BCA) = 4f(CAB) = 2 f(CBA) = 5

If we take the Fourier transform of f over S3, it will decompose f into frequency components based on cycle types:

There are three cycle types:

1. 3-cycles: CAB, BCA

2. 2-cycles: ACB, BAC, CBA

3. 1-cycles: ABC

The transform would reveal how much each cycle type contributes to the payoff f:

f(3-cycle) = 3 (average of CAB, BCA payoffs)

f(2-cycle) = 4 (average of ACB, BAC, CBA)

f(1-cycle) = 6 (just ABC)

Here, we see the 1-cycle orderings rely mostly on specific orders, while 3-cycles don't rely on order much.

In this case, the boolean degree deg(f) would be one since the full payoff relies on a 1-cycle (specific order matters).

A cycle refers to how many elements are permuted or swapped in the Ordering.

So in S3:

• A 1-cycle means only one element is being moved.

• A 2-cycle means two elements are swapped. Like ACB, where C and B are swapped compared to ABC.

• A 3-cycle means all three elements are permuted. Like BCA, where A, B, and C are all moved compared to ABC.

In general, an k-cycle in 𝑆ₙ means k of the n elements have their positions changed or cycled.

So, in our example:

• 1-cycle orderings like ABC rely heavily on that specific order to achieve the payoff. A small change breaks it.

• 3-cycle orderings like BCA are not dependent on the order much. You can change the order and still get similar payoff.

The Fourier transform shows the 3-cycle orderings contribute a moderate amount to the payoff f, while the 1-cycle contributes the most. This shows the payoff relies on one specific ordering.

As we saw earlier, Uncertainty principles relate a function f to properties of its Fourier transform f̂. They state that f and f̂ cannot both be highly concentrated or "spiky" - there is an inherent trade-off, i.e., they cannot be localized simultaneously. The paper mentions, “One can also view these as saying if f is concentrated on a small set S of values, then f̂ cannot be concentrated on a set of values more than some decreasing function.”

Now we look at the following equation, which connects the norm of a function and its Fourier transform:

This relates to the L1 norms of f and f̂, measuring their concentrations.

If G =𝑆ₙ,

The significance of this inequality is:

• It upper bounds the gap between the max and average value of f in terms of f̂

• If f̂ is spread out, the gap is small, meaning randomness provides good fairness

• If f̂ is concentrated, the gap can be large, so complex rules are needed for fairness

• The degree s of f appears in k(n,s), relating the complexity of f to the required freedom in ordering rules

So, in essence, this uncertainty principle allows translating the complexity of a payoff function f to guarantee the fairness of random/limited orderings in terms of properties of its Fourier transform f̂.

The goal is to formalize the notions of "small" and "large" sets of permutations A about the payoff function f. This is done using the concept of t-intersecting sets - sets A where every pair of permutations in A share at least t pairwise elements that are mapped to the same points. Formally, A is t-intersecting if for all π,π' in A, there exist t pairs (i1,j1),...,(it,jt) with π(ik) = π'(ik) = jk.

Recent results show t-intersecting sets have size bounded by (n-t)! [KLMS23]. Moreover, if |A| = Ω((n-t)!), fixed points are shared by all π in A. This implies indicator functions 1A for such A have degree ≥ t.

The t-intersecting sets concept is relevant for "fair ordering" protocols that validators use to agree on a set of valid transaction orderings A. These protocols work by having validators reach a consensus on a directed acyclic graph (DAG) G representing order precedence. A valid ordering is any topological sort of G. However, issues like the Condorcet paradox can still arise.

This results in cycles in G that are conserved across all topological sorts. So the set of valid orderings A ends up being t-intersecting for some minimal t < n, as orderings keep some cycles fixed.

The value of t depends on the level of agreement among validators:

• t close to 0 means validators had nearly evenly split votes on order for most transactions

• t close to n means almost total agreement on a full precedence ordering

So, t quantifies the order flexibility resulting from the fair ordering protocol.

In summary, t-intersecting sets are a natural model for the constraints on orderings from fair ordering protocols, allowing the application of the fairness results we now see.

There are two key results - an upper and lower bound on the fairness functionals for a payoff function f and set of orderings A.

Upper bound: If A is t-intersecting and t ≥ deg(f), there is a non-trivial upper bound on the unfairness:

Where s = deg(f). This means randomness provides some fairness if A has sufficient overlap relative to f's complexity.

Lower bound: If t < deg(f) and |A| is sufficiently large, there is a non-trivial lower bound:

This means that if A omits critical orderings, significant unfairness is guaranteed.

Together, these relate worst-case unfairness to the interplay of t, deg(f), and |A|.

So, t-intersecting sets "bandlimit" functions to degree ≥ t. The degree of f relative to t now allows formalizing "small" and "large":

• If t < deg(f), A is "small" and may omit critical orderings → lower bound

• If t ≥ deg(f), A is "large" and captures the complexity of f → upper bound

So, t-intersecting sets allow connecting the size and overlap of A to the complexity of f via degrees.

The notion of a "bandlimit" arises from signal processing and Fourier analysis. In that context, bandlimiting refers to limiting a function's Fourier transform to only low frequencies below some threshold. In the context of this work on transaction orderings, the idea of bandlimiting comes up when considering t-intersecting sets of permutations A.

Specifically:

• T-intersecting sets A have the property that permutations in A share at least t fixed point pairs (i,j) (t transactions for our understanding)

• This means A limits permutations to those with sufficient overlap in their structure. (maybe a fair ordering)

• In terms of Fourier analysis on the symmetric group Sn, this restriction ends up filtering out representations indexed by partitions λ with λ1 > n - t

• So A only includes "low degree" Fourier modes of degree < t

In signal processing, this is analogous to low-pass filtering - allowing low frequencies to pass while blocking high frequencies. Hence, t-intersecting sets effectively "bandlimit" functions on Sn by restricting permutations to those sharing t fixed points. This band-limiting property connects the overlap of A to the complexity of payoff functions f. If deg(f) < t, A omits critical orderings needed to capture f. If deg(f) ≥ t, A retains enough overlap to represent f. So, in summary, t-intersecting sets provide a way to bandlimit or restrict complexity in a precise way connected to Fourier analysis on Sn. This is then leveraged in the main proofs bounding fairness functionals.|.

Implications on MEV:

• Simple payoff functions like CFMMs have low degree → simple sequencing gives good fairness/high welfare

• Complex payoffs like liquidations have a high degree → complex rules needed for fairness

• Like a Nyquist sampling rate theorem for fairness

Implications on Fair Ordering:

• If t < deg(f), unfairness lower bound applies → paradoxes cause unfairness

• If t ≥ deg(f), upper bound applies → high agreement gives fairness

Overall, the bounds clarify how properties of A interact with the complexity of f to limit fairness.

The paper's conclusion is as follows: “Consensus-enforced ordering rules need to be constructed on an application-level basis.” this follows from the fact that, as we saw, different payoff functions have different degrees, so they need different sequencing rules to achieve high welfare/fairness.

We can think of this paper as giving sampling rules:

• The payoff function f is like the continuous signal. It has varying levels of complexity.

• The Fourier transform fˆ represents the frequency decomposition. Boolean degree = highest freq.

• Restricting to A is like sampling the permutation space. T-intersecting is like the sampling rate.

• If t ≥ deg(f), it's like sampling above the Nyquist rate. Capture complexity gives a fairness guarantee.

• If t < deg(f), it's like under-sampling. Fails to capture full complexity, allows unfairness.

• So, in essence, t relative to deg(f) is like the sampling rate close to signal frequency content.

Look at this talk by Tarun Chitra for more.

Exploring the second part of the Theory of MEV. :D

Blockchain systems rely on decentralized networks of participants to maintain a global shared state and execute transactions (in the case of ethereum, validators). A core challenge is dealing with varying incentives and strategic behavior by different network participants. In particular, validators who produce blocks have temporary power to reorder or include transactions, enabling profit at the expense of others. This phenomenon of excessive profits extractable by temporary inclusion monopolists by reordering or inserting transactions is known as Maximal Extractable Value (MEV).

In an earlier work, “Towards a Theory of MEV I,” Kulkarni et al. study the game theoretic properties of MEV, explicitly answering questions about how reordering impacts the price of sandwich attacks and how sandwich attacks affect routing MEV. They find that of reordering MEV, the maximum price impact caused by reordering of sandwich attacks on the order of O(log n) where n is the number of user trades and that in the case of routing MEV, the existence of MEV degrades and counterintuitively improves the routing quality. For a quick recap, you can look at a talk by Tarun Chitra and my blog.

In this blog, I cover the work “Towards a Theory of MEV II: Uncertainty.” While the first paper focused on analyzing MEV for constant function market makers specifically, this work aims to develop a more general theory around payoffs (more on what payoffs are later).

Ultimately, blockchain users encounter a variety of uncertainty; as the image shows, it’s on a spectrum. This article only covers the first part and is about Ordering Uncertainty. Ultimately, MEV can be viewed as sophisticated participants capturing profits from user uncertainty, and one more way of looking at it is capturing profits from user inefficiencies.

This paper provides a quantitative trade-off between the freedom to reorder transactions and the payoffs in decentralized networks. The results can be viewed as an analog of sampling theorems, showing simple rules suffice for simple payoffs, but more complexity is necessary to limit unfairness for arbitrary payoffs. The technical core involves Fourier analysis of the symmetric group, representation theory, and uncertainty principles. These characterize the relationship between sequencing rules, payoff complexity, and fairness guarantees.

Fair Ordering has been introduced as a solution to handle MEV mitigation. These methods propose changing blockchain consensus, forcing validators to adhere to a particular order of transactions. This order can be determined by time or some other rules. One common form of Transaction ordering is FCFS (first come, first serve), where validators note the times of the transactions they receive, and the one that comes earlier appears early in the order as per the fair ordering protocol. In two recent papers, “Order-Fair Consensus in the Permissionless Setting,” Kelkar et al. and “Themis: Fast, Strong Order-Fairness in Byzantine Consensus,” Kelkar et al. propose ways to achieve such fair Ordering.

However, research in social choice theory renders such attempts moot. How? Social choice theory is a field of economics and political science that deals with creating frameworks that explore how individual preferences can be aggregated to make collective decisions. Two important results in Social choice theory make it hard to design universal fair ordering protocols.

The Condorcet paradox demonstrates that majority preferences can be inconsistent under certain conditions because of the intransitive preferences of choices among voters. For example:

Suppose there are three voters - Alice, Bob, and Charlie. They are trying to decide among three options - A, B, and C. Their preferences are:

Alice: A > B > C Bob: B > C > A Charlie: C > A > B

If we tally the votes between each pair of options:

• A vs. B: Alice and Charlie prefer A over B, so A wins 2-1

• A vs. C: Bob and Charlie prefer C over A, so C wins 2-1

• B vs. C: Alice and Bob prefer B over C, so B wins 2-1

So the majority prefers A > B; B > C; C > A

This creates a paradox or inconsistency since transitive logic would require that A > B, B > C, and C > A is impossible.

The Arrow impossibility theorem builds on this idea and makes an even stronger statement about the difficulty of aggregating individual preferences into coherent group choices. In essence, it proves that aggregating individual preferences into a rational collective preference ordering is impossible when there are three or more options and two or more people. This implies no perfect voting system; all democratic voting methods involve trade-offs between fairness criteria. For more on Arrow’s theorem, read this.

Does this mean giving up on any transaction ordering is the only solution? In “Credible Decentralized Exchange Design via Verifiable Sequencing Rules,” Ferreira et al. show that if one aims to design a sequencing rule where the miner can never obtain risk-free profits (risk-free profits meaning the miner is sure to receive some tokens for free), such a goal is unattainable (As far as deterministic sequencing rules are concerned). They also show that some sequencing rules increase social welfare for unsophisticated agents (normal protocol users).

Social welfare functions are mathematical models used to aggregate individual preferences into a single measure that represents the "well-being" of a group. This paper's authors believe that Ordering's impact on AMMs is only possible partly due to the convexity of the payoff function of an AMM. If social welfare functions can restrict orderings to mitigate the adverse welfare effects of MEV, a natural question is, what is a generalized way of constructing such orderings? The authors try to generalize these rules to a larger class of payoff functions.

Formal Definition: The Heisenberg Uncertainty Principle in quantum mechanics is usually stated as follows:

ΔxΔp ≥ ℏ/2 ​

Here, Δx is the uncertainty in position, Δp is the uncertainty in momentum, and ℏ is the reduced Planck constant, approximately 1.054571 × 10^(−34)  m^2kg/s.

In Simpler Words, Imagine you're trying to look at a tiny particle, like an electron, under a super-microscope. The Heisenberg Uncertainty Principle says that you can't know both where the particle is (its position) and how fast and in what direction it's moving (its momentum) with perfect accuracy at the same time. It's like trying to watch a fast-moving hummingbird; if you focus on capturing its speed, you can't pinpoint its exact location, and vice versa.

The uncertainty principle generally states that there are inherent limitations in our ability to measure or know pairs of complementary properties/functions at the same time. The general mathematical form often takes the shape of an inequality, like

where C(f) and C(Lf) are measures of "complexity" or "uncertainty" for a function f and its transformed version Lf, c is a constant greater than zero, and L is the linear transform. This inequality tells us that if one of the measures is small (i.e. if we know one property very precisely), the other must be large enough to satisfy the inequality, meaning the other property cannot be known with arbitrary precision.

In the case of the Heisenberg uncertainty principle, one of the attributes is indeed related to the Fourier transform of the other. Specifically, the position x and momentum p are Fourier transform pairs. In quantum mechanics, the wave function ψ(x) in position space can be transformed into momentum space ϕ(p) using the Fourier transform.

This paper aims to construct complexity measures C representing the fairness of payoff functions f. The complexity measures will connect the sizes of particular subsets of permutations (basically transaction orderings) to C(f). These subsets are outputs of sequencing rules (hence, they also allow us to talk about different “kinds” of orderings in general).

Blockchains are decentralized systems that maintain a sequence of blocks containing state transitions and come to a consensus on a particular state. Each block consists of transactions that mutate the state from the previous block. Users submit transactions via a peer-to-peer network and pay fees to include them in a block. Validators or miners collect transactions, validate blocks, and add these to the global ledger. Validators lock up resources to participate in the overall consensus protocol and are incentivized by fees and block rewards. A key aspect of blockchains is that they allow asynchronous communication about a shared (global) state, with protocols designed to make it costly for validators to deviate from consensus. While adding blocks to the blockchain, a temporary monopoly is given to a single validator in many consensus protocols.

This temporary monopoly of allowing validators to reorder or censor transactions and earn fees and profit from this practice is called Miner extractable value.

This paper assumes that there is a fixed set of transactions T_1, …, T_n and a payoff function f (T_1, …, T_n) that yields profit to the validator. This paper does not consider the difference between the allocation/split of the profit between the validator and searchers (entities that search for profitable orderings and submit them to the validator).

The payoff function f is a mapping from transactions to a payoff. Since we consider a fixed set of transactions for reordering MEV, the payoff to validators from executing transactions in a particular order can be modeled as a function f that maps permutations of the transaction set to real numbers.

Some notation

• 𝑆ₙ → set of permutations of n elements

• 𝜋 → permutation; 𝜋(i) → index where ith element is moved

The function f: 𝑆ₙ → ℝ is a payoff function that takes a transaction ordering and gives a payoff. Concretely, for a function g: 𝑇ⁿ → ℝ, we have

The Ordering is the optimal monopoly profit achievable via reordering MEV. Here, the max denotes the permutation out of the set of permutations of n transactions that gives us the maximum payoff.

Constant Function Market Makers: Let’s think about the trades in an AMM briefly. Users submit transactions and are then added to a block. How is MEV extracted around these? Sandwich attacks are the most common form of MEV extraction. In a sandwich trade, an order is placed before and after the submitted transaction by the user, and the slight price difference (impact) is booked as the profit. The order in which user trades are executed changes the profitability. So, the payoff function f(π) depends on the permutation π of user trades.

The payoff function for CFMMs is given by:

𝜟_i denotes the transaction by the user, and p_i is the price obtained after the execution of the user transaction. This payoff is not permutation invariant. Some permutations are clearly better than others.

Liquidations: Liquidations allow protocols to close positions that have become undercollateralized due to price changes. For example, a user borrows asset Y by posting asset X as collateral at an initial price ratio of p0. If the price of X in terms of Y later drops to p* (the liquidation price), liquidators can profitably close the position.

Liquidation is generally very permutation sensitive, i.e., for some orderings (maybe even most), there might not be a liquidation at all. For a permutation π of trades, define pi(π) as the price after trades π(1),...,π(i) have executed. Some permutations will not reach the liquidation price threshold, while others will.

Let A be the liquidatable set:

where p_i(π) is the price after executing 𝜟_π(1)…𝜟_π(I) and p_0 - c is the liquidation threshold. As we noted, some permutations don’t reach the liquidation threshold.

The liquidation payoff function is:

Where 1𝐴(π) is an indicator function that equals one if π is in set A and 0 otherwise, intuitively, it’s like choosing the permutations that liquidate the position.

Generally, we can use liquidations and auctions to construct any payoffs in the form of 1𝐵. Here

Where the summation is overall A ⊂ 𝑆ₙ, and f^(A) are the coefficients.

So, any payoff function f can be written as a linear combination of liquidation payoff functions 1𝐴. In this sense, the liquidation payoffs 1𝐴 form a basis for the set of functions f: 𝑆ₙ -> ℝ. (Similar to a basis for Vector spaces ^_^)

Now that we have established Ordering and payoffs, we move to fairness functionals. These are ways of measuring the fairness of an ordering scheme since we might want to talk about how certain orderings are fairer than others.

Given a payoff function f: 𝑆ₙ -> ℝ, we aim to measure the "fairness" of an ordering scheme that generates a set of orderings, i.e., a set A ⊂ 𝑆ₙ of valid orderings.

A global fairness function is defined as a map: 𝐿¹(𝑆ₙ) -> ℝ, which takes a payoff of a set of transactions and returns the difference (deviation) between the maximum payoff and the average payoff.

A short deviation into L1 norms:

In mathematics, the L1 norm is a way to measure the "size" of a function. For a function that takes in values and spits out numbers, the L1 norm sums up the absolute values of the function over its entire input domain.

For example, suppose we have a function f that takes in integers as input and outputs numbers. The L1 norm of f, written ||f||1, is defined as:

||f|| = sum of |f(x)| for all integer inputs x

Where |f(x)| is the absolute value of f(x).

So if f(1) = 3, f(2) = -2, and f(3) = 5, then the L1 norm of f is:

||f|| = |3| + |-2| + |5| = 10

The L1 norm captures the maximum magnitude the function f reaches over all inputs.

Now, in the context of the paper, The payoff function f maps permutations of the transaction set to real numbers.The L1 norm ||f|| sums the absolute values of f over all possible input permutations.

||f||_∞ refers to the L∞ norm, also called the supremum norm, defined as:

||f||_∞ = maxπ |f(π)|

So, the L∞ norm takes the maximum absolute value of f over all permutations π.

||f||_1 refers to the standard L1 norm, defined as:

||f||_1 = ∑π |f(π)|

So, the L1 norm sums the absolute values of f over all permutations.

The key difference is:

• The L∞ norm ||f||_∞ takes the maximum value

• The L1 norm ||f||_1 sums all values

For some more intuition on L_1 norms and more, check this out.

One can think of two natural global fairness functionals: the difference between the maximum and average and the multiplicative difference, which would quantify the magnitude of the maximum payoff in terms of the average. So we have:

1. 𝜦⁺Measures additive unfairness: - Defined as the difference between the max and average payoff of f over A, it captures the additive gap between best and typical case.

2. 𝜦*: Measures multiplicative unfairness: - Defined as the ratio between the max and average payoff of f over A, it Captures the multiplicative gap between best and typical case.

We move ahead with using 𝜦⁺ because it’s neater to work with and has some desirable properties.

So when 𝜦⁺(f) = 0, this would mean that the difference between the maximum payoff possible and the average payoff possible is 0. We can interpret this as being perfectly fair. Maximal unfairness occurs when f = 1π for some π, saturating the upper bound. Intuitively, this payoff function f = 1π returns one only for a single "jackpot" permutation π and 0 for all other inputs.

Now that we have defined these things in the global set of orderings, we will restrict them to the subset A ⊂ 𝑆ₙ (in some, localize them to a subset of the larger space we just explored)

In an earlier paper, “Towards a theory of MEV: CFMMs,” the authors show that 𝜦*(f) = O(log n), given sufficient liquidity, basically as long as there’s enough liquidity, the worst case payoff only grows logarithmically in comparison to the average case in the case of constant function market makers.

So, we now have fairness functions that measure the gap between optimal and average payoffs under a set of allowable permutations. Relating the permutation set restrictions to the complexity of the payoff function yields both upper and lower bounds on the fairness functionals. These characterize the relationship between sequencing rules, payoff complexity, and fairness guarantees.

This defines the localized fairness functional 𝜦⁺(f, A) for a payoff function f and a set of permutations A.

Specifically:

• max_π∈A f(π) is the maximum payoff achievable over all permutations π in the set A. This represents the optimal strategy for an extractor trying to maximize their profit.

• E[f1𝐴] is the expected value of f over the uniform distribution on A. 1𝐴 is the indicator function equal to 1 for π ∈ A and 0 otherwise.

• Their difference maxπ∈A f(π) - E[f 1𝐴] measures the gap between the best and average cases for f when restricted to A.

Rearranging, we find that 𝜦⁺(f, A) can be written in terms of 𝜦*( f, A); we will first construct a bound for 𝜦* and then bound 𝜦⁺ with it. Again, bounding this means we are trying to find how fair a certain set of orderings is.

This section introduces mathematical tools to analyze how much the maximum and average payoffs of a function f can differ. If we only have black-box access to f: 𝑆ₙ -> ℝ, how can we determine if the max and expected values deviate?

We saw in the liquidation example that any payoff can be constructed as the sum of indicator functions. We want to know within this set of “basis”/indicator functions which influences the payoff function f.

How could we go about doing this? One way to do this is if we could magically decompose every payoff f: 𝑆ₙ -> ℝ into a sum of indicator functions and then measure the size of the coefficients.

Recall the equation for the construction of any payoff

Here, f̂(A) are the coefficients of the indicator functions, and quantifying them would tell us which subset of the Ordering contributes most to the payoff function.

We first try to establish this for the construction of payoff that we’ve already seen; since we can construct payoff functions of any kind if the form is 1𝐵, we explore various properties. But since this form, 1𝐵, does not capture all the payoff types; we then look at other methods, which let us talk about the generalized form of payoff and then explore their properties.

A very brief look into what these are.

The Fourier Transform is a mathematical tool that decomposes a signal (or function) into its constituent frequencies. Imagine you have a complex sound wave; the Fourier Transform helps you determine what "pure tones" (sine and cosine waves) make up that complex sound.

The Fourier Transform of a function f(t) is given by

Here, F(ω) tells you the amplitude and phase of the sine and cosine waves at each frequency ω that, when added up, reconstruct f(t). The Fourier Transform takes you from the time domain (where you describe signals as functions of time t) to the frequency domain (where you describe signals as functions of frequency ω).

Imagine you're listening to an orchestra. Your ear receives a complex mixture of sounds from various instruments, each playing at different frequencies. The Fourier Transform is like having the superpower to instantly "hear" each individual instrument's pure tone, separating it from the orchestra's collective sound. Later, you can combine these unique tones to recreate the original complex sound of the orchestra.

The Fourier Transform breaks down complex signals into their basic frequency components, much like identifying individual instruments in an orchestra. It's a way to move from the time domain, where you see how a signal changes over time, to the frequency domain, where you know what frequencies make up that signal.

Fourier Walsh Transform: The Fourier-Walsh Transform is a specialized form of the Fourier Transform that uses Walsh functions instead of the usual sine and cosine functions as the basis set. Walsh functions are piecewise constant functions that take on values of +1 or -1, making them particularly well-suited for digital or binary signals.

Although the Discrete Fourier Transform (DFT) already exists as a discrete analog of the continuous Fourier Transform. The Fourier-Walsh Transform serves a different purpose and is tailored for different kinds of data. While the DFT is a discrete analog of the Fourier Transform for sampled, continuous signals, the Fourier-Walsh Transform is a specialized discrete analog for Boolean functions and binary signals.

If f were a boolean function, f:{-1,1}ⁿ → ℝ, then the expansion

It is called the Fourier-Walsh transform.

Where 1_A(x) = 1 if x_i = 1 for all i in A, and 0 otherwise and the f̂(A) are called the Fourier coefficients and quantify the influence of the set A on the function value. The Fourier-Walsh transform helps us prove statements that tie the global behavior of the function f to properties about the sets A that it is supported on. If A has a small size but a large f̂(A), then the variables in A have an outsized influence on f.

We can thus interpret the relationship between |A| (the size of the set) and f̂(A) (the magnitude of the coefficients) as seeing how flat or sharp the function is.

The Plancherel theorem for the Fourier transform has a vital significance: it relates the overall "size" of a function f to the sizes of its Fourier coefficients f̂(A). There is a Plancherel theorem relating the L2 norms of f and its Fourier transform:

This means the L2 norm of f (its "energy") equals the L2 norm of its Fourier transform f̂. Intuitively, if a small number of Fourier coefficients f̂(A) contain most of the L2 norm of f̂, then the function f is mainly influenced by those sets A. For example, if 90% of Σ_A |f̂(A)|^2 comes from 5 sets A, we can say f "mostly depends" on just those five sets. In transaction orderings, the Plancherel theorem allows us to identify which sets of permutations A significantly influence the payoff function f. If the payoff depends heavily on just a few sets of orderings A, we can design sequencing rules or auctions to preserve those orderings. So basically, the Plancherel theorem lets us quantify which orderings matter most for the payoff f. It provides a precise way to measure how much freedom is needed in the allowable orderings A to capture the behavior of f.

We now define the boolean degree deg(f) is defined as:

For boolean functions f: {-1,1}ⁿ → ℝ, the boolean degree deg(f) measures the size of the largest input subset that significantly influences f. It is defined based on the Fourier-Walsh decomposition. Large Fourier coefficients on small sets ⊆ [n] indicate that f depends strongly on those inputs.

T measures the size of the largest set A that influences f. We can also define the degree-t part f_≤t as:

So f_≤t restricts f to sets A of size ≤ t. The degree gives a precise way to measure how "complex" a boolean function is.

Now that we have established all the properties we are interested in for the indicator function, we look at more generalized payoffs.

The symmetric group 𝑆ₙ:

• This contains all possible permutations (orderings) of n elements.

• For transaction orders, Sn would be all possible orderings of n transactions.

• The size of Sn is n! (factorial of n).

In the case of abelian groups, indicator functions can often be represented as vectors because the group operation is commutative. However, the non-commutativity complicates things for non-abelian groups like the symmetric group. Here, a more complex representation is needed, and that's where matrices come in.'

Therefore, instead of having indicator functions 1A:{-1,1}ⁿ → ℝ, we have representations. A representation of a group G is a way to represent the elements of G as linear transformations on a vector space V. Intuitively, it shows how G acts on V.

A representation ρ of 𝑆ₙ:

GL(V^d) is the general linear group of invertible matrices acting on a vector space V of dimension d.

Irreducible representations are the basic building blocks - they cannot be decomposed into smaller representations. It is a fact that finite groups have a finite number of irreducible representations. Representations will serve as the analog of indicator functions for non-abelian groups.

The Fourier transform and representation theory allows analyzing functions on non-commutative groups like Sn analogously to Fourier analysis of processes on Rn. The Fourier transform f̂(ρ) of a function f: 𝑆ₙ -> ℝ is given by

The Fourier transform decomposes a function f: 𝑆ₙ -> ℝ into irreducible representations. The λth Fourier coefficient fˆ(ρλ) is a matrix capturing how f acts on Vλ. Note that this is a sum of matrices.

As we saw earlier, we have a planche rel theorem in this case, too, defined by

To define the boolean degree, we need an analog, though. Ultimately, the boolean degree in the indicator function case gave us an idea of how much influence the largest subsets of inputs had on f. In this case, we need a better way of talking about the representations of 𝑆ₙ.

Every permutation in 𝑆ₙ​ can be decomposed into cycles. These cycles correspond to partitions of [n], and each partition describes an irreducible representation of 𝑆ₙ. The function f is expanded using the inverse Fourier transform. The sum involves traces of matrices corresponding to irreducible representations, weighted by some degree d.

Where Tr is the matrix trace and dλ = dim(Vλ) is the dimension of ρλ.

It turns out that the set of partitions of [n] serves to index the irreducible representations of the symmetric group 𝑆ₙ. The representations ρ are indexed by partitions λ of n. This is a way to express functions on 𝑆ₙ in terms of invariant basis functions under certain permutations. This set is called the Specht module and allows one to decompose 𝑆ₙ.

Thus, the sum in the equation (in the case of expanded f) represents the projection of f to each Specht module.

All of this helps us ultimately to define the boolean degree of this function f, as:

Where λ |- n means λ is a partition of n. Where λ1 is the largest part of λ, this measures the complexity of f on 𝑆ₙ.

So, in summary, the Fourier analysis generalizes to non-abelian groups like 𝑆ₙ while still providing ways to analyze the complexity of functions via representations and boolean degrees. The same high-level goals apply regarding quantifying the influence of sets and relating degrees of f and f̂.

Let’s imagine a small example:

Suppose we have n=3 transactions in our blockchain: A, B, C.

The symmetric group S3 would contain all possible orderings of these three transactions:

S3 = {ABC, ACB, BAC, BCA, CAB, CBA}

So S3 has size 3! = 6.

Now suppose our payoff function f assigns a profit to each Ordering:

f(ABC) = 6 f(ACB) = 2 f(BAC) = 3 f(BCA) = 4f(CAB) = 2 f(CBA) = 5

If we take the Fourier transform of f over S3, it will decompose f into frequency components based on cycle types:

There are three cycle types:

1. 3-cycles: CAB, BCA

2. 2-cycles: ACB, BAC, CBA

3. 1-cycles: ABC

The transform would reveal how much each cycle type contributes to the payoff f:

f(3-cycle) = 3 (average of CAB, BCA payoffs)

f(2-cycle) = 4 (average of ACB, BAC, CBA)

f(1-cycle) = 6 (just ABC)

Here, we see the 1-cycle orderings rely mostly on specific orders, while 3-cycles don't rely on order much.

In this case, the boolean degree deg(f) would be one since the full payoff relies on a 1-cycle (specific order matters).

A cycle refers to how many elements are permuted or swapped in the Ordering.

So in S3:

• A 1-cycle means only one element is being moved.

• A 2-cycle means two elements are swapped. Like ACB, where C and B are swapped compared to ABC.

• A 3-cycle means all three elements are permuted. Like BCA, where A, B, and C are all moved compared to ABC.

In general, an k-cycle in 𝑆ₙ means k of the n elements have their positions changed or cycled.

So, in our example:

• 1-cycle orderings like ABC rely heavily on that specific order to achieve the payoff. A small change breaks it.

• 3-cycle orderings like BCA are not dependent on the order much. You can change the order and still get similar payoff.

The Fourier transform shows the 3-cycle orderings contribute a moderate amount to the payoff f, while the 1-cycle contributes the most. This shows the payoff relies on one specific ordering.

As we saw earlier, Uncertainty principles relate a function f to properties of its Fourier transform f̂. They state that f and f̂ cannot both be highly concentrated or "spiky" - there is an inherent trade-off, i.e., they cannot be localized simultaneously. The paper mentions, “One can also view these as saying if f is concentrated on a small set S of values, then f̂ cannot be concentrated on a set of values more than some decreasing function.”

Now we look at the following equation, which connects the norm of a function and its Fourier transform:

This relates to the L1 norms of f and f̂, measuring their concentrations.

If G =𝑆ₙ,

The significance of this inequality is:

• It upper bounds the gap between the max and average value of f in terms of f̂

• If f̂ is spread out, the gap is small, meaning randomness provides good fairness

• If f̂ is concentrated, the gap can be large, so complex rules are needed for fairness

• The degree s of f appears in k(n,s), relating the complexity of f to the required freedom in ordering rules

So, in essence, this uncertainty principle allows translating the complexity of a payoff function f to guarantee the fairness of random/limited orderings in terms of properties of its Fourier transform f̂.

The goal is to formalize the notions of "small" and "large" sets of permutations A about the payoff function f. This is done using the concept of t-intersecting sets - sets A where every pair of permutations in A share at least t pairwise elements that are mapped to the same points. Formally, A is t-intersecting if for all π,π' in A, there exist t pairs (i1,j1),...,(it,jt) with π(ik) = π'(ik) = jk.

Recent results show t-intersecting sets have size bounded by (n-t)! [KLMS23]. Moreover, if |A| = Ω((n-t)!), fixed points are shared by all π in A. This implies indicator functions 1A for such A have degree ≥ t.

The t-intersecting sets concept is relevant for "fair ordering" protocols that validators use to agree on a set of valid transaction orderings A. These protocols work by having validators reach a consensus on a directed acyclic graph (DAG) G representing order precedence. A valid ordering is any topological sort of G. However, issues like the Condorcet paradox can still arise.

This results in cycles in G that are conserved across all topological sorts. So the set of valid orderings A ends up being t-intersecting for some minimal t < n, as orderings keep some cycles fixed.

The value of t depends on the level of agreement among validators:

• t close to 0 means validators had nearly evenly split votes on order for most transactions

• t close to n means almost total agreement on a full precedence ordering

So, t quantifies the order flexibility resulting from the fair ordering protocol.

In summary, t-intersecting sets are a natural model for the constraints on orderings from fair ordering protocols, allowing the application of the fairness results we now see.

There are two key results - an upper and lower bound on the fairness functionals for a payoff function f and set of orderings A.

Upper bound: If A is t-intersecting and t ≥ deg(f), there is a non-trivial upper bound on the unfairness:

Where s = deg(f). This means randomness provides some fairness if A has sufficient overlap relative to f's complexity.

Lower bound: If t < deg(f) and |A| is sufficiently large, there is a non-trivial lower bound:

This means that if A omits critical orderings, significant unfairness is guaranteed.

Together, these relate worst-case unfairness to the interplay of t, deg(f), and |A|.

So, t-intersecting sets "bandlimit" functions to degree ≥ t. The degree of f relative to t now allows formalizing "small" and "large":

• If t < deg(f), A is "small" and may omit critical orderings → lower bound

• If t ≥ deg(f), A is "large" and captures the complexity of f → upper bound

So, t-intersecting sets allow connecting the size and overlap of A to the complexity of f via degrees.

The notion of a "bandlimit" arises from signal processing and Fourier analysis. In that context, bandlimiting refers to limiting a function's Fourier transform to only low frequencies below some threshold. In the context of this work on transaction orderings, the idea of bandlimiting comes up when considering t-intersecting sets of permutations A.

Specifically:

• T-intersecting sets A have the property that permutations in A share at least t fixed point pairs (i,j) (t transactions for our understanding)

• This means A limits permutations to those with sufficient overlap in their structure. (maybe a fair ordering)

• In terms of Fourier analysis on the symmetric group Sn, this restriction ends up filtering out representations indexed by partitions λ with λ1 > n - t

• So A only includes "low degree" Fourier modes of degree < t

In signal processing, this is analogous to low-pass filtering - allowing low frequencies to pass while blocking high frequencies. Hence, t-intersecting sets effectively "bandlimit" functions on Sn by restricting permutations to those sharing t fixed points. This band-limiting property connects the overlap of A to the complexity of payoff functions f. If deg(f) < t, A omits critical orderings needed to capture f. If deg(f) ≥ t, A retains enough overlap to represent f. So, in summary, t-intersecting sets provide a way to bandlimit or restrict complexity in a precise way connected to Fourier analysis on Sn. This is then leveraged in the main proofs bounding fairness functionals.|.

Implications on MEV:

• Simple payoff functions like CFMMs have low degree → simple sequencing gives good fairness/high welfare

• Complex payoffs like liquidations have a high degree → complex rules needed for fairness

• Like a Nyquist sampling rate theorem for fairness

Implications on Fair Ordering:

• If t < deg(f), unfairness lower bound applies → paradoxes cause unfairness

• If t ≥ deg(f), upper bound applies → high agreement gives fairness

Overall, the bounds clarify how properties of A interact with the complexity of f to limit fairness.

The paper's conclusion is as follows: “Consensus-enforced ordering rules need to be constructed on an application-level basis.” this follows from the fact that, as we saw, different payoff functions have different degrees, so they need different sequencing rules to achieve high welfare/fairness.

We can think of this paper as giving sampling rules:

• The payoff function f is like the continuous signal. It has varying levels of complexity.

• The Fourier transform fˆ represents the frequency decomposition. Boolean degree = highest freq.

• Restricting to A is like sampling the permutation space. T-intersecting is like the sampling rate.

• If t ≥ deg(f), it's like sampling above the Nyquist rate. Capture complexity gives a fairness guarantee.

• If t < deg(f), it's like under-sampling. Fails to capture full complexity, allows unfairness.

• So, in essence, t relative to deg(f) is like the sampling rate close to signal frequency content.

Look at this talk by Tarun Chitra for more.