Compatible signs exist on the Bruhat graph

Induct on $\mathrm{\ell }(w)$ to sign every cover in the principal ideal $I(w)=\{x:x\le w\}$ with product $-1$ on every diamond. For $w=1$ there are no covers. Choose a simple right descent $s$ of $w$ and put $J=I(ws)\subset I(w)$. By induction sign all edges in $J$. Every $x\in I(w)\setminus J$ descends under $s$: otherwise lifting $x\le w$ would give $x\le ws$. Moreover $xs\le ws$, by descent monotonicity. Set $\epsilon (x,xs)=1$ for these outside vertices. If $x⊳y$ is any other edge with $x$ outside, then $y$ also descends: if $ys>y$, lifting gives $ys\le x$, and equality of lengths forces $ys=x$, the excluded vertical edge. Thus $xs⊳ys$, both vertices lying in $J$, and $x,y,xs,ys$ is a diamond. Define $\epsilon (x,y)=-\epsilon (y,ys)\epsilon (xs,ys)$. The first factor is already defined, either by induction when $y\in J$, or as $1$ when $y$ is outside. This assigns each edge once and makes every such side diamond negative.

Let $D=(a,b,c,d)$ be a diamond in $I(w)$. If $a\in J$, all its vertices lie in $J$, so its product is $-1$ by induction. Suppose $a$ is outside. If neither $b$ nor $c$ equals $as$, both descend by step 1.1. Then $d$ descends too: if $ds>d$, lifting $d\le b,c$ gives $ds\le b,c$; equality of lengths forces $ds=b=c$, a contradiction. The four translated vertices $as,bs,cs,ds$ are distinct, lie in $J$, and form a diamond by descent monotonicity and their lengths. Each of the four side diamonds $(x,y,xs,ys)$ for the edges of $D$ has product $-1$: step 1.1 gives this if $x$ is outside, and induction gives it if $x\in J$. Multiplying these four products and the product of the translated diamond leaves exactly the product of $D$, because each vertical edge and each translated edge occurs twice. Hence its product is $(-1{)}^5=-1$.

The remaining case, after exchanging $b,c$, is $b=as$. Here $c\mathrm{\ne }as$ descends, and $cs\le as=b$; it has length $\mathrm{\ell }(d)$ and differs from $d$ unless $ds>d$. If $ds>d$, lifting against $c$ gives $ds=c$, so $cs=d$. Thus $D$ is precisely the side diamond for $a⊳c$, already made negative in step 1.1. If $ds<d$, the vertices $b,c,cs,d,ds$ give three diamonds: $(a,b,c,cs)$, $(c,d,cs,ds)$ and $(b,d,cs,ds)$. Indeed $b⊳cs$ follows from $cs\le b$ and the lengths, $cs⊳ds$ from descent monotonicity applied to $d\le c$, and $b⊳d$, $d⊳ds$, $c⊳cs$ are given covers. The first two are side diamonds, negative by step 1.1 or induction; the last lies in $J$ because $b\in J$. Multiplying their three products cancels all extra edges twice and leaves exactly the product of $D$. It is therefore $(-1{)}^3=-1$.

Steps 2.1 and 2.2 exhaust all diamonds, proving the induction. Every $x$ lies below the longest element: repeatedly append a simple reflection that increases length, producing Bruhat covers. Length is bounded on the finite group, so this stops at an element $v$ with $v{\alpha }_i<0$ for every simple root by the simple-reflection criterion. Every positive root is a nonnegative combination of simple roots, so $v$ reverses all positive roots and is the longest element by [F1]. Thus take $w$ to be that element to obtain a signing on all of $W$. In a diamond the two path products $P_1,P_2\in \{\pm 1\}$ satisfy $P_1{P}_2=-1$, hence $P_2=-P_1$, the required consequence. For $W=\{1\}$ the empty signing satisfies the assertion vacuously. The construction uses only recursion on a finite group and selection from finite sets, so no infinite Choice principle is used.

For the last assertion put $r(x,y)={\epsilon }^{\mathrm{\prime }}(x,y)\mathrm{/}\epsilon (x,y)$, whose product on each diamond is $1$. Induct on $\mathrm{\ell }(w)$ to find $c(e)=1$ and $r(x,y)=c(x)\mathrm{/}c(y)$ on $I(w)$. The identity ideal is immediate. With $s,J$ as in step 1.1, take the inductively supplied signs on $J$ and set $c(x)=r(x,xs)c(xs)$ for every $x$ outside $J$. This handles vertical edges. Every other edge $x⊳y$ with $x$ outside has the side diamond $(x,y,xs,ys)$ of step 1.1, with $xs,ys\in J$. Also $r(y,ys)=c(y)\mathrm{/}c(ys)$, either by induction when $y\in J$ or by the new definition otherwise. Its diamond identity gives $r(x,y)r(y,ys)=r(x,xs)r(xs,ys)$; substituting the known ratios yields $r(x,y)=c(x)\mathrm{/}c(y)$. All remaining edges lie in $J$. Taking $w$ to be the longest element completes this finite induction and proves the assertion.