Permutation function based on subsets

Question

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.

Answer 1

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

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.