How to prove this problem about supermodularity function?

Question

The problem is as follows, and I have solved the subproblem (a), but haven't solved (b) yet. And for (b) the method I think about is proof by contradiction, but I get stuck before I could solve this. Anyone can prove (b)?

Answer 1

Your problem can be rephrased as $$\arg\max_y\{\sum_{r_1\in \Omega_1}p(r_1,s_2)u(y,r_1,s_2)\}\ge \arg\max_x\{\sum_{r_1\in \Omega_1}p(r_1,t_2)u(x,r_1,t_2)\}\text{ if }s_2>t_2.$$

Note that if $s_2>t_2$ and $x>y$, we will have $$u(x,r_1,s_2)-u(y,r_1,s_2)>u(x,r_1,t_2)-u(y,r_1,t_2).$$

Denote the left part to be $a_{r_1}$ and right part be $b_{r_1}$, from the maximality of $x$ we have$$\sum_{r_1\in \Omega_1}b_{r_1}p(r_1,t_2)\ge 0.$$

Since $\Omega_1$ is finite, we may sort all its elements to be $r_1 < r_2 < \cdots r_n$, and according to the increasing property of $u$ we have $b_{r_1}<b_{r_2}\cdots <b_{r_n}$.

We now claim that$$\sum_{i=1}^n b_{r_i}p(r_i,s_2)\ge 0.\qquad\qquad (1)$$

For simplicity, let $b_{r_i}=b_i,p(r_i,t_2)=t_i,p(r_i,s_2)=s_i$, we now prove $(1)$ by induction on $n$.

1. $n=1$ trivially holds.
2. We now from $n=k$ to prove $k+1$. From the induction hypothesis we have$$b_1s_1+b_2s_2+\cdots+b'_ks'_k\ge 0,$$where $\displaystyle b'_k=\frac{b_kt_k+b_{k+1}t_{k+1}}{t_k+t_{k+1}}$ and $s'_k=s_k+s_{k+1}$. One can easily observe that $b'_ks'_k\le b_ks_k+b_{k+1}s_{k+1}$, since it is equivalent to $b_kt_ks_{k+1}+b_{k+1}t_{k+1}s_{k}\le b_kt_{k+1}s_k+b_{k+1}t_{k}s_{k+1}$ and this follows form $t_ks_{k+1}\ge t_{k+1}s_{k}$ and $b_{k+1}>b_k$ by applying Rearrangement_inequality.

So, we have $a_1s_1+a_2s_2+\cdots+a_ns_n> b_1s_1+b_2s_2+\cdots+b_ns_n\ge 0$, which contradict to the maximality of $y$.