I'm trying to understand Monderer and Samet's 1989 paper on approximate common knowledge.

I'm stuck in the last part of the proof of the "agreeing to disagree" Theorem A, where the upper bound of the posterior is established. The lower bound seems clear but I just cannot understand how one of the terms is written as (1-p). Am pasting a picture below of the part where I'm lost:

enter image description here

The last line which establishes the upper bound of r_i is unclear to me. Any help would be greatly appreciated. The link of the paper is :

https://ie.technion.ac.il/~dov/cpb_monderer_samet.pdf

(Theorem A is in page 180-181)

New contributor
Swaminathan B is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
up vote 1 down vote accepted

Showing the left-hand inequality

Let's rearrange the equation, $$ \begin{align*} x &= r_i \frac{\mu\left( B^p_i\left( E \right) \right)}{\mu\left( E \right)} - \frac{\mu\left( X \cap \left[ B^p_i\left( E \right) \setminus E \right] \right)}{\mu\left( E \right)} \\ & \iff \underbrace{x \mu\left( E \right) + \mu\left( X \cap \left[ B^p_i\left( E \right) \setminus E \right] \right)}_{\text{LHS}} = r_i \mu\left( B^p_i\left( E \right) \right). \end{align*} $$ Since all terms in $\text{LHS}$ are weakly positive, we can omit $\mu( X \cap [ B^p_i( E ) \setminus E ] )$ from $\text{LHS}$, giving $$ x \mu\left( E \right) \leq r_i \mu\left( B^p_i\left( E \right) \right). $$ Since $\mu( E ) \geq p \mu( B^p_i( E ) )$, this directly implies $x p \leq r_i$.

Showing the right-hand inequality

Since $\mu( E ) \leq \mu( B^p_i( E ) )$ and $x \geq 0$, we have $$ \begin{align*} &\frac{1}{\mu\left( E \right)} \left[ r_i \mu\left( B^p_i\left( E \right) \right) - \mu\left( X \cap \left[ B^p_i\left( E \right) \setminus E \right] \right) \right] \\ &\geq \frac{1}{\mu\left( B^p_i\left( E \right) \right)}\left[ r_i \mu\left( B^p_i\left( E \right) \right) - \mu\left( X \cap \left[ B^p_i\left( E \right) \setminus E \right] \right) \right] \\ &= \underbrace{r_i - \frac{\mu\left( X \cap \left[ B^p_i\left( E \right) \setminus E \right] \right)}{\mu\left( B^p_i\left( E \right) \right)}}_{\text{RHS}}. \end{align*} $$ It must be that $X \cap [ B^p_i( E ) \setminus E ] \subseteq B^p_i( E ) \setminus E$, so $$ \text{RHS} \geq r_i - \frac{\mu\left( B^p_i\left( E \right) \setminus E \right)}{\mu\left( B^p_i\left( E \right) \right)} = r_i - \frac{\mu\left( B^p_i\left( E \right) \right) - \mu\left( E \right)}{\mu\left( B^p_i\left( E \right) \right)} = r_i - \left( 1 - \mu\left( \left. E \right| B^p_i\left( E \right) \right) \right). $$ By definition (and this is inequality (9) in the text) $\mu( E | B^p_i( E ) ) \geq p$, thus $$ \text{RHS} \geq r_i - \left( 1 - p \right). $$ Noting that the original equality was $x = \text{RHS}$, we have $$ x \geq r_i - \left( 1 - p \right) \;\; \iff \;\; r_i \leq x + 1 - p. $$

Your Answer

Swaminathan B is a new contributor. Be nice, and check out our Code of Conduct.
 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.