ZoĆ© Christoff edited This_example_shows_that_direction__.tex  almost 8 years ago

Commit id: 3a469fd3e7cc683a3321706143e90e23d7537731

deletions | additions      

       

Beyond this simple example, we want to find out what happens with more complex constraints and what are the conditions for resistant BDPs to converge. Let us first show that direction $2)\Rightarrow 1)$ of Theorem \ref{theorem:opinion} still holds for resistant BDPs, that is, resistant BDPs without disagreement in their cycles always converge:  %\begin{comment}  \begin{theorem}\label{theorem:resistantsufficient}  Let $\G$ be an influence profile, $\O$ be an opinion profile, and $\C$ a set of constraints. Then the following holds:  \begin{enumerate}  \item[] If for  all $p\in \Atoms$, for all $S\subseteq\N$ such that $S$ is a cycle in $G_{p}$, and all $i,j\in S$: $O_i(p)=O_j(p)$, then \item[] the resistant BDP for $\O$, $\G$ and $\C$ converges in at most $k$ steps, where $k=max\{diam(G_p)|p\in P\}$.  \end{enumerate}  \end{theorem} 

%Let $k$ be the distance from $i$ to $l$, where $l$ is the closest agent in a cycle $S\subseteq\N$ of $G_p$.   Let $k_i(p)$ be the distance from $i$ to the closest agent in a cycle of $G_p$, and $k_i$ be the maximum in $\{k_i(p)|p\in P\}$. We show that for any $k_i\in\mathbb{N}$, $O^{k_i}_ i$ is stable.  \begin{itemize}  \item If $k_i=0$: $i$ is its only infuencer, therefore  $O_{i}$ is stable already. stable.  \item if If  $k_i=n+1$: Assume that for all agents $j$ such that $k_j=n$, $O^{k_j}_ j$ is stable. This implies that all influencers of $i$ are stable. We need to consider the following cases: \begin{enumerate}  \item If $\bigwedge_{p \in \Atoms} O^{m}_{R_p(i)}(p) \wedge \bigwedge_{\varphi \in \C}$ is not consistent, then it will never be: $O^{n}_i$ is stable.   \item If $\bigwedge_{p \in \Atoms} O^{m}_{R_p(i)}(p) \wedge \bigwedge_{\varphi \in \C}$ is consistent,