Delta-Epsilon-Common Knowledge and Quantitative Agreement Theorems

This paper introduces a novel framework for $(\delta,\epsilon)$-common knowledge applicable to general probability spaces and provides quantitative extensions of Aumann's Agreement Theorem and related results to settings involving noisy communication and random variables.

The Gist

Imagine you and a friend are trying to guess the outcome of a mystery event, like whether it will rain tomorrow. You both have your own private information (maybe you checked the sky, your friend checked an app). In the perfect world of classic math theory, if you both know that you both know the answer, and you know that you know they know, and so on forever, you are forced to agree on the exact same number for your prediction. This is the famous "Agreement Theorem" by Robert Aumann.

However, the real world isn't perfect. We don't have infinite memory, our communication is sometimes fuzzy, and our information is rarely 100% complete. We are often in a state of "almost" knowing.

This paper, written by Pawlowitsch, Schrott, and Toneian, asks a simple but profound question: What happens to that agreement rule when we are only "almost" sure about things?

They introduce a new way to measure this "almost" using two simple numbers, like a dial on a machine: $\delta$ (delta) and $\epsilon$ (epsilon).

The Two Dials of "Almost"

The authors create a system to measure how close we are to perfect knowledge using two types of "fuzziness":

1. The $\delta$ Dial (The "Blurry Lens"): This measures how close your private information is to being perfectly clear. Imagine looking at a map through a slightly foggy window. If the fog is very thin ($\delta$ is small), you can almost see the road clearly. In math terms, this means your information is "nearly" contained in your knowledge.
2. The $\epsilon$ Dial (The "Leaky Bucket"): This measures how close your conclusion is to being perfectly true. Imagine you are trying to fill a bucket with water (the truth), but the bucket has tiny holes. If the holes are tiny ($\epsilon$ is small), you still have almost the right amount of water. In math terms, this means your belief is "nearly" a subset of the actual event.

The Main Discovery: You Still Agree (Mostly)

The paper's big news is that even with these two dials turned on (meaning you have blurry lenses and leaky buckets), you and your friend still cannot disagree wildly.

If you both know that you both almost know the answer (using these $\delta$ and $\epsilon$ definitions), then your final guesses will be very close to each other. The paper provides a mathematical formula that says: "The difference between your guess and my guess cannot be bigger than a specific number calculated from how blurry and leaky our situation is."

• The Analogy: Imagine two people trying to guess the weight of a watermelon. One is wearing glasses that are slightly dirty ($\delta$), and the other is using a scale that is slightly uncalibrated ($\epsilon$). Even though neither has a perfect view or a perfect scale, if they both know that the other is in this same "slightly imperfect" state, they will still end up guessing weights that are very close together. They won't guess 5 lbs and 50 lbs; they might guess 12 lbs and 13 lbs. The "noise" limits how far apart they can get.

From Events to Random Variables (The "Moving Target")

The paper also tackles a harder version of the problem. Instead of just guessing "Yes/No" (Will it rain?), what if you are trying to guess a number that changes, like the temperature or the stock price?

The authors extend their "blurry lens" and "leaky bucket" idea to these moving targets. They show that even when you are trying to agree on a complex, changing number, if your knowledge is "almost" shared, your estimates of that number will stay close together. They use a concept called "conditional variance" (a fancy way of saying "how much my guess might wiggle") to measure this closeness.

The "Noisy Phone" Scenario

The paper ends with a practical example involving a noisy phone call. Imagine you and a friend are on the phone, trying to figure out the temperature. Every time you speak, the phone adds a little bit of static noise to your voice.

• The Old View: If there is any noise, the math says you might never reach a perfect agreement.
• The New View: The authors show that even with this constant static, as long as the noise doesn't get too loud (the variance is bounded), your guesses will eventually settle down and stay very close to each other. You don't need a perfect, silent line to reach an agreement; you just need a line where the static isn't too bad.

Summary

In simple terms, this paper takes a rigid, perfect-world math rule ("If we know everything, we must agree") and softens it for the messy real world. It proves that imperfect knowledge doesn't lead to total chaos. As long as our imperfections are small and we know that the other person is also imperfect in a similar way, we are mathematically guaranteed to stay in the same ballpark. We might not agree on the exact decimal point, but we will definitely agree on the general idea.

Technical Summary

Technical Summary: Delta-Epsilon-Common Knowledge and Quantitative Agreement Theorems

Problem Statement
Fifty years after Aumann's seminal work, the field of common knowledge and agreement theorems faces two primary limitations in practical application. First, real-world scenarios often involve "almost" common knowledge rather than the strict, binary common knowledge defined by Aumann. Second, existing generalizations of Aumann's Agreement Theorem—specifically those moving from countable probability spaces to general (uncountable) spaces and from events to random variables (as done by Nielsen)—have not been adequately combined with the concept of approximate knowledge. While previous literature (e.g., Monderer and Samet, Geanakoplos, Morris) has addressed approximate agreement via "common $p$-belief," these results are largely restricted to countable probability spaces. There is a need for a framework that quantifies the distance to common knowledge applicable to general probability spaces and random variables, particularly in settings involving noisy communication.

Methodology
The authors introduce a novel framework for quantifying approximate common knowledge, termed $(\delta, \varepsilon)$-common knowledge, defined on events within general probability spaces $(\Omega, \mathcal{F}, P)$. The methodology relies on two relaxations of elementary set-theoretic and measure-theoretic notions:

1. $\delta$-nearly containment in a $\sigma$-algebra: An event $B$ is $\delta$-nearly in a $\sigma$-algebra $\mathcal{G}$ if there exists $G \in \mathcal{G}$ such that $P(B \triangle G) \leq P(B)\delta$.
2. $\varepsilon$-nearly containment in an event: An event $B$ is $\varepsilon$-nearly a subset of $A$ if $P(B \setminus A) \leq P(B)\varepsilon$.

The paper defines knowledge and common knowledge "on an event $B$" rather than at a specific state $\omega$. This approach allows for the handling of null sets and continuous models where exact knowledge of specific posterior values is often impossible. The authors utilize conditional variances to quantify the "closeness" of knowing a random variable, extending Nielsen's work. They also employ the metric $d(\mathcal{G}_1, \mathcal{G}_2)$ between $\sigma$-algebras (based on Rogge) to establish continuity properties of conditional expectations.

Key Contributions and Results

1. Approximate Common Knowledge of an Event
The paper establishes that the $\sigma$-algebra-based definition of $(\delta, \varepsilon)$-common knowledge is equivalent to both a hierarchical definition (mutual knowledge of mutual knowledge) and an alternating hierarchical definition (individual 1 knows, individual 2 knows individual 1 knows, etc.). This generalizes Aumann's original equivalence proof to the approximate setting.

• Quantitative Agreement Theorem (Theorem 3.12 & 3.15): The authors prove that if two individuals have $(\delta, \varepsilon)$-common knowledge of their posteriors (for an event or a random variable $X \in [0,1]$) lying within specific intervals, the distance between their posteriors is uniformly bounded. Specifically, if the posteriors are $(\delta, \varepsilon)$-common knowledge, the difference $|q_1 - q_2|$ is bounded by $\frac{2\delta + \varepsilon}{1 + \delta}$. This result holds for general probability spaces, unlike previous results based on common $p$-belief which were limited to countable spaces.
• Relation to Common $p$-belief: The paper provides explicit conversion formulas (Propositions 3.18 and 3.19) between $(\delta, \varepsilon)$-common knowledge and weak common $p$-belief, demonstrating that the two concepts are interchangeable in terms of applicability, though $(\delta, \varepsilon)$-common knowledge offers a more robust structural equivalence in general spaces.

2. Approximate Common Knowledge of a Random Variable
Extending Nielsen's work, the authors define $(\delta, \varepsilon)$-common knowledge for random variables using conditional variances. A random variable $X$ is $(\delta, \varepsilon)$-common knowledge on $B$ if $B$ is $\delta$-nearly in both individuals' $\sigma$-algebras and the conditional variance of $X$ given the restricted $\sigma$-algebra is bounded by $\varepsilon$.

• Agreement Theorem for Random Variables (Theorem 4.21): The paper proves that if the posteriors of a random variable $X$ are $(\delta, \varepsilon)$-common knowledge on an event $B$, the $L^2$-distance between the posteriors on $B$ is bounded by a function of $\delta$ and $\varepsilon$:
  $$E_{P_B}[(E[X|\mathcal{G}_1] - E[X|\mathcal{G}_2])^2] \leq 64\delta \|X\|_{L^\infty}^2 + 4\sqrt{\varepsilon} \|X\|_{L^\infty}$$
  This result generalizes Nielsen's agreement theorem to approximate settings.

3. Dynamic Approximate Agreement
The authors extend the dynamic agreement results of Geanakoplos and Polemarchakis and Nielsen to noisy settings.

• Convergence with Noise (Theorem 5.2): In a dynamic setting where individuals exchange information over time, if the conditional variance of one individual's posterior given the other's future information converges to $\varepsilon$ (approximate common information), then the $L^2$-distance between their limiting posteriors is bounded by $2\sqrt{\varepsilon \text{Var}(X)}$.
• Application to Noisy Communication (Example 5.4): The paper illustrates this with a scenario where individuals communicate their posteriors through a noisy channel with uniformly bounded variance noise. The result guarantees that the disagreement at infinity is controlled solely by the noise variance $\varepsilon$, without requiring assumptions on the noise distribution shape.

Significance
The paper claims significance primarily in its conceptual generalization and quantitative precision:

1. General Probability Spaces: Unlike prior work on approximate agreement (e.g., Monderer and Samet, Geanakoplos, Morris) which relied on countable spaces, these results hold for arbitrary probability spaces, making them applicable to continuous models and infinite type spaces in Bayesian games.
2. Unified Framework: It unifies the study of approximate knowledge for both events and random variables under a single $(\delta, \varepsilon)$-framework, preserving the equivalence between $\sigma$-algebra definitions and hierarchical definitions.
3. Robustness: The results provide explicit quantitative bounds on disagreement, demonstrating that substantial disagreement is impossible even when common knowledge is only approximate. This is particularly relevant for modeling real-world scenarios involving noisy communication, where exact common knowledge is unattainable.

The authors maintain a modest tone, noting that while the constants in the bounds may not be tight, the existence of such bounds in general spaces and the ability to convert between different notions of approximate knowledge constitute the core theoretical advance.