We have some subsets $A\_1,\dots,A\_k$ of $A=\{1,2,\dots,n\}$. For each permutation $\sigma$ of $A$, define $f(\sigma) = \sum\_{i=1}^k g(\sigma,A\_i)$, where if the earliest element of $A\_i$
in $\sigma$ appears in position $j$, then $g(\sigma,A\_i)= 1/j$. Let $\sigma\_1$ be the permutation maximizing $f(\sigma)$, breaking ties lexicographically.


Now, we add an element $r\not\in A\_1$ to $A\_1$, and let $\sigma\_2$ be the permutation maximizing $f(\sigma)$. Does it always hold that $r$ appears no later in $\sigma\_2$ than in $\sigma\_1$?


A natural approach is to show that if $r$ appears later in $\sigma\_2$ than in $\sigma\_1$, then upon adding $r$ to $A\_1$, $f(\sigma\_1)$ increases by at least as much as $f(\sigma\_2)$. But this may not be true, because there may already be an element in $A\_1$ that appears in $\sigma\_1$ before $r$. Still, it does not clearly lead to a counterexample either.



Permutation function based on subsets
I have a counterexample, showing that $r$ can appear later in $\sigma\_2$ than in $\sigma\_1$.


I'm going to write this counterexample with weights on the sets, but because the weights are rational it can easily be converted to an unweighted counterexample by duplicating sets.


Counterexample: 3x{AC}, 2x{AB}, 2x{BD}, 2x{CD}, 11/8x{C}, 1x{A}, 1x{D}.


[Calculations](https://docs.google.com/spreadsheets/d/1n9gYTRRKqtslAKpRfWEDv-NJaThpzIDMzTVNgmEQhW4/edit?usp=sharing)


The initial maximum value of $f$ is $215/24$, achieved by the permutations ADCB, CBAD, CBDA. By the tiebreaker, $\sigma\_1$ is ADCB.


Now, we will add the element D to the set {A}, changing it to the set {AD}.


The new maximum value of $f$ is $217/24$, achieved by the permutations CBDA, CDAB, CDBA. By the tiebreaker, $\sigma\_2$ is CBDA.


We added the element D to a set, but $\sigma\_1$ has D in position 2, while $\sigma\_2$ has D in position 3.




---


Note that while this counterexample relies on the tiebreaker, it can be lightly modified to not rely on the tiebreaker.


To do so, add the subsets {A} and {B} each with an equal weight $\epsilon$ to the set system, for some $\epsilon$ very close to 0. This increases the value of ADCB by $(5/4)\epsilon$, while CBAD and CBDA increase by $(5/6)\epsilon$ and $(3/4)\epsilon$, respectively. As a result, ADCB is $\sigma\_1$ without a tiebreaker needed.


The values of CDAB and CDBA increase by $(7/12)\epsilon$, which is smaller than CBDA's $(3/4)\epsilon$, so CBDA is $\sigma\_2$ with no tiebreaker needed.




---


The way I came up with the counterexample is by starting with the 2 element sets, which I designed to force the optimal permutation to start with either AD or CB. At this point, adding a D to an A subset would benefit a CBD permutation but not an AD permutation, which would make the CBD permutation the new optimum, and form a counterexample. I then futzed around with the weights on the single subsets to get the optima to work out right.


