Tsinghua Workshop on Social Network Logic
A max-flow / min-cut explanation of how to repair strict preference update in the Liang–Seligman peer-pressure model.
Xiaochen Chang
Slides redesigned and programmed by Ray
Strong update becomes transparent once we treat it as a path-cutting problem.
Motivation. Agents are influenced not only by what their friends believe, but also by how their friends rank alternatives.
Example: $F p$ means “all of agent $a$’s friends satisfy $p$ at the current world”.
Let $X = [[\phi \land \neg\psi ]]$ and $Y = [[\psi \land \neg\phi ]]$.
Make $Y$ at least as good as $X$.
$R_{new} = R \cup (X \times Y)$
Operation: Only add forward comparisons from $X$ to $Y$.
Make $Y$ strictly better than $X$.
$R_{new} = (R \cup (X \times Y)) \setminus (Y \times X)$
Operation: Add forward comparisons, and delete any existing reverse comparisons from $Y$ back to $X$.
Arc: a single edge, written $u\to v$.
Path: a directed route, written $u\leadsto v$.
If we add the strict edge $X\to Y$ while some old path $Y\leadsto X$ survives, then transitive closure recreates a forbidden comparison from $Y$ back to $X$.
So the real target is not one arc. We must destroy every old path from $Y$ to $X$.
Fact / Lemma.
If $R$ is a preorder and we delete the boundary cut
$C_U=R\cap (U\times(W\setminus U)),$
then
$D_U=R\setminus C_U$ is still a preorder.
This is why deleting a whole boundary cut is such a good move: it disconnects paths without destroying order-theoretic structure.
A candidate repair $T$ must satisfy three hard constraints:
We compare candidate repairs by the pair
$(|A_T|,|B_T|)$
where $A_T=R\setminus T$ are deleted old edges and $B_T=T\setminus(R\cup(X\times Y))$ are non-intended closure additions.
Claim.
$Y\not\leadsto_D X \iff TC(D\cup(X\times Y))\cap(Y\times X)=\varnothing.$
So preserving strictness after closure is exactly the same as blocking every old path from $Y$ to $X$ before we add $X\to Y$.
A legal split is any set $U\subseteq W$ with
$Y\subseteq U,\qquad X\cap U=\varnothing$.
Its boundary cut is
$C_U=R\cap(U\times(W\setminus U))$.
Then the repaired old relation is $D_U=R\setminus C_U$, and the full repair is
$T_U=TC(D_U\cup(X\times Y))$.
Every legal $U$ gives an admissible repair. Different $U$ can yield different repairs.
1.Start from any admissible repair $T$.
2.Take $U$ = all nodes reachable from $Y$ inside the old part $R \cap T$.
3.Then its boundary cut $C_{U}$ is never worse than $T$.
Lemma. For every admissible repair $T$, there exists a legal split $U$ such that
$T_U \preceq_R T$.
So we lose nothing by searching only among boundary-cut repairs.
This is the bridge from “all possible repairs” to “repairs indexed by U”. Without it, min-cut would solve the wrong problem.
Let
$P=Pred_R(X)=\{p\mid \exists x\in X,\ pRx\}$,
$S=Succ_R(Y)=\{z\mid \exists y\in Y,\ yRz\}$.
If $pD_Ux$, $x\in X$, $y\in Y$, and $yD_Uz$, then adding $x\to y$ forces a new closure edge $p\to z$.
$D_U\langle X,Y\rangle=\{(p,z)\mid \exists x\in X\,\exists y\in Y\, (pD_Ux \land yD_Uz)\}$.
A closure consequence has the form $p\to z$: after adding $X\to Y$, transitivity may force a new comparison from a predecessor of $X$ to a successor of $Y$.
$H=(Pred_R(X)\times Succ_R(Y))\setminus(R\cup(X\times Y))$
For each $(p,z)\in H$, add an artificial reverse edge $z\to p$ in the augmented graph.
Cost Marker: This is not a preference edge. If $z$ is on the source side and $p$ is on the sink side, the real repair will add the closure edge $p\to z$.
If this artificial edge overlaps with an old edge, its cost contribution is summed in Step 7.
We construct the network before the cut is chosen.
\(P=Pred_R(X)=\{p\in W\mid \exists x\in X,\ pRx\}\)
\(S=Succ_R(Y)=\{z\in W\mid \exists y\in Y,\ yRz\}\)
\(H=(P\times S)\setminus(R\cup(X\times Y))\)
\(E=R\cup\{(z,p)\mid(p,z)\in H\} \cup(\{s\}\times Y)\cup(X\times\{t\})\)
\(G'=(W\cup\{s,t\},E,c)\)
Capacity function.
\[ c((u,v))=\sum \begin{cases} M, & \text{if }(u,v)\in R,\\ 1, & \text{if }(v,u)\in H,\\ K, & \text{if }(u,v)\in(\{s\}\times Y)\cup(X\times\{t\}). \end{cases} \]
The sum is necessary: the same directed edge may be both an old edge and the reverse of a candidate closure edge.
\(M=|H|+1,\qquad K=M|R|+|H|+1.\)
\(M\) makes deletion of old edges the first priority. \(K\) forces \(Y\) to stay on the source side and \(X\) on the sink side.
For each legal split $U$, the cut capacity is
$cap(U)=M\cdot |R\setminus T_U| + |T_U\setminus(R\cup(X\times Y))|$.
So minimizing cut capacity is exactly minimizing our lexicographic repair cost.
When several minimum cuts exist, choose the canonical source-side minimum cut: the intersection of all minimum source sides.
By submodularity of the cut function, the intersection of minimum cuts is again a minimum cut.
| U | |A| | |B| | cap | status |
|---|
Thank you.