<p>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:</p>

<ul>
<li>$I_0\subset I_1\subset\cdots \subset I_{n-1}\subset I_n=X$;</li>
<li>$f(I_0)\leq f(I_1)\leq\cdots\leq f(I_{n-1})\leq f(I_n)$; and</li>
<li>$|I_{i}|=|I_{i-1}|+1$ for all $i\in[1..n]$,</li>
</ul>

<p>where $\leq$ denotes the standard order on $\mathbb{R}$, and $|I_i|$ denotes the cardinality of $I_i$ (seen as a subset of $X$).</p>

<p>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 <em>exists</em> 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$ <em>and</em> satisfy other constraints. </p>

<p>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.</p>

<p><strong>Update</strong>: 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)&gt;0$. </p>

<p>Denote by $\bar I$ the complement $X\setminus I$ of a subset $I$ of $X$. </p>

<p>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 <strong>average</strong> 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\}$.</p>

<p>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</p>

<ul>
<li>$f(\emptyset)=\frac{5+3+2}{3}\asymp 3.33$</li>
<li>$f(\{a\})=\frac{3+2}{2}=2.5$, $f(\{b\})=\frac{5+2}{2}=3.5$ and $f(\{c\})=\frac{5+3}{2}=4$</li>
<li>$f(\{a,b\})=2$, $f(\{a,c\})=3$ and $f(\{b,c\})=5$</li>
<li>$f(\{a,b,c\})=5$.</li>
</ul>

<p>As counter example to monotonicity, simply take $\{a\}\subseteq \{a,b\}$ and observe that $f(\{a\})=2.5$, yet $f(\{a,b\})=2$.</p>

<p>Nevertheless, as can be observed from the example, this function  satisfies the property described earlier. </p>

<p>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)&gt; f(I)$ for every $j\in \bar I$. Then,
$$
f(I)=\frac{1}{|\bar I|}\sum_{j\in \bar I} g(j)&gt; \frac{|\bar I|}{|\bar I|} f(I)= f(I),$$
a contradiction.</p>

<p>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)&amp;=\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)\\
&amp;=\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)\\
&amp;=\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)\\
&amp;=\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) &amp;\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)&amp;\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)&amp;\leq \frac{1}{|\bar I|}\sum_{j\in \overline{I\cup \{j^\star\}}} g(j)\\
g(j^\star)&amp;\leq \frac{1}{|\bar I|-1}\sum_{j\in \overline{I\cup \{j^\star\}}} g(j)\\
g(j^\star)&amp;\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.</p>

<p><strong>Remark</strong> 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)$.</p>

CC BY-SA 3.0
2017-09-24T15:13:34.577Z
I don't see why this is such a natural condition. Do you have examples of natural functions that aren't monotone that satisfy this property?
Peter Shor 
CC BY-SA 3.0
2017-09-24T19:33:59.577Z
Thanks for you question. This condition pops up when considering averaging functions. I have updated the question with a general description of a class of functions satisfying this property, yet which are not necessarily monotone (also shown by example).
sirolf
<reference-request><optimization><terminology><lattice><function>
A class of functions on a lattice that are easy to optimize
sirolf
# A class of functions on a lattice that are easy to optimize

(Asked by: username_0 on 2017-09-23)

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)$.

**Tags:** reference-request, optimization, terminology, lattice, function

> **Comments:**
> **username_1**: I don't see why this is such a natural condition. Do you have examples of natural functions that aren't monotone that satisfy this property?  
> **username_0**: Thanks for you question. This condition pops up when considering averaging functions. I have updated the question with a general description of a class of functions satisfying this property, yet which are not necessarily monotone (also shown by example).  

---

## 0 answers

