Let $R$ be a function that maps a set and a positive integer to a real positive number. We have that for any positive integer $t$ and $S \subseteq \{1, \ldots, t\}$, $R(S, t)$ satisfies:
- For all $t < t'$, $R(S, t) < R(S, t')$. For all $A \subset S$, $R(A, t) > R(S, t)$.
- For all $i < S_{[1]}$, $R(S, t) = R(S-i, t-i)$ where $S_{[1]}$ denotes the smallest element of $S$ and $S - i = \{s - i: s \in S\}$ .
- For all $A \subseteq B \subseteq S$, $i \in S \setminus B$, $$R(A \cup \{i\}, t) - R(A, t) \leq R(B \cup \{i\}, t) - R(B,t).$$ (Note that the above supermodularity is only valid for a given $t$, but not for different t. If it helps, one can think of $t$ as time and the set $S$ as some kind of consumption time stamps.)
Before going to the optimization objective, for notation simplicity, I will use $[T]$ to denote the set $\{1, \ldots, T\}$, $S_{[i]}$ to denote the $i-$th smallest element in $S$ and $S_{[i]:[j]}$ to denote the subset $\{s \in S: S_{[i]} \leq s \leq S_{[j]}\}$. Now, the goal is to maximize the below objective: for a given $T$,
$$\max_{S \subseteq [T]} \sum_{i=2}^{|S|} R(S_{[1]:[i-1]}, S_{[i]}) + \sum_{j=2}^{T - |S|} R(S^c_{[1]:[j-1]}, S^c_{[j]}),$$ where $S^c$ is the complement of $S$, i.e., $S^c = [T] \setminus S$.
I am quite confused about where to start to approach this problem. One suggestion I got is to try to first write the objective as a difference between two supermodular functions, but I am unsure how to come up with such decompositions. I would really appreciate any suggestions on where to start, how to think of this problem, relevant literature or good keywords to search for existing work on similar problems. Thanks in advance!
