The duality property for proper configurations

Fix a metric space $M$, $k\ge1$ servers, an initial configuration $C_0$, a request sequence $\sigma$ and one further request $r$. Write $D(X)=\sum_i d(r,X_i)$, and call a configuration proper when it is injective and avoids $r$ — in the classical language, a $k$-element set not containing $r$.

Statement. Let $A$ be a proper configuration minimising $\widehat w_{t-1}(X)-D(X)$ among proper configurations. Then $A$ also minimises $\widehat w_t(X)-D(X)$ among proper configurations, and it maximises $\widehat w_t(X)-\widehat w_{t-1}(X)$ among all injective configurations.

Status (updated). The case $\#M = k+2$, which is the one the $(k+2)$-point argument needs, is settled: it is now a step inside the proof of refworkFnU_growth_card_add_two_inj, and the milestone refcard_add_two_competitive is proved. What remains open here is the statement above for an arbitrary metric space, which is strictly more than that argument gives.

How the $k+2$ case goes, and why it does not generalise. On a space with exactly $k+2$ points an injective configuration is the complement of a pair, so writing $W(u,v)=\widehat w(\{u,v\}^C)$ and

the recurrence collapses to an edge recurrence $W'(r,b)+d(r,b)=\min_c \mu(\{b,c\})$ — the two-evader problem. Let $e^\*=\{A,C\}$ minimise $\mu$ over the edges missing $r$. For $b\notin e^\*\cup\{r\}$ the four points $r,b,A,C$ are distinct, and quasiconvexity applied to the two injective configurations $\{r,b\}^C$ and $(e^\*)^C$ yields one of the two exchanges

from which $W'(r,b)-W(r,b)\le W'(r,z)-W(r,z)$ follows in one line. The essential point — and the answer to the difficulty recorded below — is that for these two configurations the quasiconvexity hybrids can be kept injective: they differ in exactly two points, so choosing the hybrid index set to be the complement of a reachability set under "the point I contribute is the point the other configuration contributes here" makes both hybrids injective, misses $r$ from one and $b$ from the other, and keeps every commonly occupied point in both.

That repair uses $\#M=k+2$ twice: it needs the two configurations to differ in exactly two points, and it needs the counting step that forces exactly one of $A,C$ to be missing from the first hybrid. On a larger space two injective configurations can differ in up to $k$ points and the hybrids genuinely fail to be injective, so the general statement still needs a different idea.

Why the unrestricted duality lemma does not suffice. In this model a configuration is a labelled map $\{1,\dots,k\}\to M$, so it may place two servers on the same point, and workFnU extends the classical work function from $k$-element sets to multisets. Exact dynamic programming shows that the minimum of $\widehat w_{t-1}(X)-D(X)$ over all configurations is sometimes attained only at multisets with a repeat: on $(k+2)$-point spaces this happened at roughly 2% of steps for $k=2$, 20% for $k=3$ and 28% for $k=4$. So the global minimiser is not in general the complement of an edge, and KServer.workFnU_duality cannot be quoted.

A neighbouring guess, that the global minimiser can always be taken injective and $r$-avoiding, is false, and instructively so: at $\sigma=\varnothing$ the work function is $\widehat w(X)=\mathrm{match}(C_0,X)$, whose only minimiser of $\widehat w-D$ is $C_0$ itself, so a non-injective $C_0$ is an immediate counterexample. Exact DP over non-injective $C_0$ confirms it (56–92 failing steps per $(k,n)$ cell tested), while the restricted statement above survived all $3920$ steps of the same sweep.

Formalization Note Both conclusions are stated as universally quantified inequalities rather than $\arg\min$ memberships, so no minimiser is asserted to exist; on a finite metric space, which is the case of interest, one does. A proof of the general case needs either a form of quasiconvexity whose hybrids stay injective for configurations differing in more than two points, or a route that does not pass through quasiconvexity at all.