Let $({\cal P}(X),\subseteq)$ be the subset lattice for a finite set $X$. Consider a function $f:{\cal P}(X)\to \mathbb{R}$ with the following property: Given any element $I_0\in {\cal P}(X)$, there is a sequence $I_1,\ldots,I_n$ of elements in ${\cal P}(X)$ such that the following holds:
- $I_0\subset I_1\subset\cdots \subset I_{n-1}\subset I_n=X$;
- $f(I_0)\leq f(I_1)\leq\cdots\leq f(I_{n-1})\leq f(I_n)$; and
- $|I_{i}|=|I_{i-1}|+1$ for all $i\in[1..n]$,
where $\leq$ denotes the standard order on $\mathbb{R}$, and $|I_i|$ denotes the cardinality of $I_i$ (seen as a subset of $X$).
Note that this does not imply that $f$ is monotone, i.e., for elements $I$ and $J$ in ${\cal P}(X)$ such that $I\subset J$, it does not necessarily hold that $f(I)\leq f(J)$. The condition mentioned above just implies that for every element $I$, different from $X$, there exists an element $J$ (of size $|J|=|I|+1$) such that $f(I)\leq f(J)$. One can thus follow a path from $I$ to $X$ (top element) with a non-decreasing $f$-score. This property can be used to locate elements in the lattice that maximize $f$ and satisfy other constraints.
My question is the following: Do such functions have a name? It seems a quite natural condition but haven't been able to find this condition in the literature.
Update: As an example of a class of functions with this property consider a positive function $g$ defined on the elements of $X$, i.e., for each $j\in X$, $g(j)>0$.
Denote by $\bar I$ the complement $X\setminus I$ of a subset $I$ of $X$.
Define $f$ on subsets $I$ of $X$ as follows: $$ f(I):=\frac{1}{|\bar I|}\sum_{j\in \bar I} g(j), $$ i.e., $f$ is just the average of the $g$-values of elements not in $I$. As a special case, when $I=X$, let $f(X):=\max\{ g(j)\mid j\in X\}$.
Such functions are not monotone. For example, let $X=\{a,b,c\}$ and consider $g(a)=5$, $g(b)=3$ and $g(c)=2$. We have that
- $f(\emptyset)=\frac{5+3+2}{3}\asymp 3.33$
- $f(\{a\})=\frac{3+2}{2}=2.5$, $f(\{b\})=\frac{5+2}{2}=3.5$ and $f(\{c\})=\frac{5+3}{2}=4$
- $f(\{a,b\})=2$, $f(\{a,c\})=3$ and $f(\{b,c\})=5$
- $f(\{a,b,c\})=5$.
As counter example to monotonicity, simply take $\{a\}\subseteq \{a,b\}$ and observe that $f(\{a\})=2.5$, yet $f(\{a,b\})=2$.
Nevertheless, as can be observed from the example, this function satisfies the property described earlier.
More generally, $f(I)\leq f(I\cup\{j\})$ whenever $g(j)\leq f(I)$. One can argue that such $j$ always exists when averages are concerned. Indeed, suppose that $g(j)> f(I)$ for every $j\in \bar I$. Then, $$ f(I)=\frac{1}{|\bar I|}\sum_{j\in \bar I} g(j)> \frac{|\bar I|}{|\bar I|} f(I)= f(I),$$ a contradiction.
Furthermore, let $j^\star\in \bar I$ such that $g(j^\star)\leq f(I)$. Observe that \begin{align*} f(I\cup\{j^\star\})-f(I)&=\frac{1}{|\bar I|-1}\sum_{j\in \overline{I\cup\{j^\star\}}} g(j)-\frac{1}{|\bar I|}\sum_{j\in \bar I} g(j)\\ &=\bigl(\frac{1}{|\bar I|-1}-\frac{1}{|\bar I|}\bigr)\sum_{j\in \overline{I\cup \{j^\star\}}} g(j) - \frac{1}{|\bar I|} g(j^\star)\\ &=\bigl(\frac{|\bar I|-|\bar I|+1}{(|\bar I|-1)|\bar I|}\bigr)\sum_{j\in \overline{I\cup \{j^\star\}}} g(j) - \frac{1}{|\bar I|} g(j^\star)\\ &=\frac{1}{|\bar I|}\bigl( f(I\cup\{j^\star\}) - g(j^\star)\bigr).\tag{1} \end{align*} It now suffices to observe that $g(j^\star)\leq f(I)$ implies that \begin{align*} g(j^\star) &\leq \frac{1}{|\bar I|}\sum_{j\in \overline{I\cup \{j^\star\}}} g(j) + \frac{1}{|\bar I|} g(j^\star)\\ g(j^\star)\bigl(1-\frac{1}{|\bar I|}\bigr)&\leq \frac{1}{|\bar I|}\sum_{j\in \overline{I\cup \{j^\star\}}} g(j)\\ g(j^\star)\bigl(\frac{|\bar I|-1}{|\bar I|}\bigr)&\leq \frac{1}{|\bar I|}\sum_{j\in \overline{I\cup \{j^\star\}}} g(j)\\ g(j^\star)&\leq \frac{1}{|\bar I|-1}\sum_{j\in \overline{I\cup \{j^\star\}}} g(j)\\ g(j^\star)&\leq f(I\cup\{j^\star\}).\tag{2} \end{align*} Combining (1) and (2) results in $f(I\cup\{j^\star\})\geq f(I)$, as desired.
Remark Instead of averaging over elements in $\bar I$, one could also average over elements in $I$ but then the property needs to be formulate wrt to the lattice $({\cal P}(X),\supseteq)$.
