Proof sketch. For simplicity, suppose that we want to maximize the buyer surplus through market segmentation. Suppose that the maximum buyer surplus possible is \(B^*\). The full generality of extremal markets implies that there is an extremal market decomposition \(\boldsymbol{\alpha}\) whose induced maximum buyer surplus is \(B^*\), which can further be turned into \((\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z})\) satisfying the exact composition and flow conservation. As a result, there exists \((\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z})\) whose induced maximum buyer surplus is \(B^*\). Conversely, take any \((\boldsymbol{x}^*, \boldsymbol{y}^*, \boldsymbol{z}^*)\) satisfying exact composition, flow conservation, and proper domination, whose induced buyer surplus is \(B^{**} \ge B^*\). There is a procedure that transforms \((\boldsymbol{x}^*, \boldsymbol{y}^*, \boldsymbol{z}^*)\) into a way to segment \(F^*\), whose induced buyer surplus is \(B^{**}\), which cannot be larger than the maximum buyer surplus \(B^*\) achievable through segmentation. As a result, \(B^* = B^{**}\). ◻

Proof of 3. Given the market \(F\) and the cost \(c_j\), we denote the largest element in the optimal price set by \(r_j\) (\(r_j = \max Q_j(F)\)) and the smallest element in the optimal price set by \(l_j\) (\(l_j = \min Q_j(F)\)). Given \(r_j\) and \(l_{j+1}\), which are the optimal price of \(c_j\) and \(c_{j+1}\) separately, we have \[\label{eq:oprimal32price32set32monotonicity32-321} F(r_j)\cdot(r_j - c_{j+1}) \le F(l_{j+1}) \cdot (l_{j+1} - c_{j+1})\tag{1}\] and \[\label{eq:oprimal32price32set32monotonicity32-322} F(r_j) \cdot (r_j - c_j) \ge F(l_{j+1}) \cdot (l_{j+1} - c_{j})~.\tag{2}\] We can further derive that \[c_{j+1}\cdot (F(l_{j+1}) - F(r_j)) \le l_{j+1}\cdot F(l_{j+1}) - r_j \cdot F(r_j) \le c_j \cdot ( F(l_{j+1}) - F(r_j))~.\] Since \(c_j < c_{j+1}\), then \(F(l_{j+1}) - F(r_j) \le 0\). Let us discuss the potential value of \(F(l_{j+1})\) and \(F(r_j)\) in these two cases.

• If \(F(l_{j+1}) = F(r_j)\), the assumption \(\max_v(v-c_j)\cdot F(v) > 0\) indicates that \(F(r_j) > 0\), then \(F(l_{j+1})>0\) as well. Combining with 1 and 2 , we can derive \(l_{j+1} = r_j\), then \[\max Q_j(F) = \min Q_{j+1}(F)~;\]

• if \(F(l_{j+1}) - F(r_j) < 0\), we have \(r_j < l_{j+1}\), then \[\max Q_j(F) < \min Q_{j+1}(F)~.\]

Therefore, we have proved the monotonicity of \(Q_j(F)\). ◻

Proof of 4. Given a fixed \(\alpha \in [0,1]\), \(Q_j(\alpha F) = \operatorname*{argmax}_v(v- c_j) \cdot \alpha F(v) = \operatorname*{argmax}_v(v- c_j) \cdot F(v) = Q_j(F)\). We conclude the lemma. ◻

Proof of [lem:optimal95price95for95extremal95market]. We separate our proof based on whether \(q_j= \infty\) or \(q_j \ne \infty\).

When \(q_j= \infty\), it satisfies \(v_i \notin S, \forall v_i \in \{v \in \mathcal{V}: v> c_j\}.\) Therefore, we have \(F(v) = 0\) for all \(v\in \{v\in \mathcal{V}: v> c_j\}\), we could derive that the maximum seller surplus of \(c_j\) is 0. Therefore, the optimal price set is \(Q_j(F_{q, S}) = \{v\in \mathcal{V}: F_{q, S}(v) = 0 \}\) and the optimal price \(q_j(F) = q_j = \infty\).

When \(q_j \ne \infty\), if we prove for any \(s \in [q_j , q_{j + 1}] \cap S\), \[\begin{align} F_{q, S}(s) \cdot (s - c_j) = F_{q, S}(v_i) \cdot (v_i - c_j), \quad & v\in [q_j , q_{j + 1}] \cap S~, \\ F_{q, S}(s) \cdot (s - c_j) > F_{q, S}(v_i) \cdot (v_i - c_j), \quad & v\notin [q_j , q_{j + 1}] \cap S~, \end{align}\] then we prove the optimal set \(Q_j(F_{q, S}) = [q_j, q_{j+1}] \cap S\) and the minimum optimal price \(q_j(F_{q, S}) = q_j\). The first equality can be easily observed from the definition of the extremal market. For the inequality, fix \(j \in [m]\). For any \(v\notin [q_j , q_{j + 1}] \cap S\) we discuss three cases:

• if \(v\in [q_j, q_{j+1}]\). Since \(v\notin [q_j , q_{j + 1}] \cap S\), \(v\notin S\). Therefore, \(F_{q, S}(v) = F_{q, S}(v^{+})\), where \(v^{+} = \min \{v'\in S: v'> v\}\), therefore, \[F_{q, S}(v) \cdot (v- c_{j}) = F_{q, S}(v^{+}) \cdot (v- c_{j}) < F_{q, S}(v^{+}) \cdot (v^{+} - c_{j})~;\]

• if \(v> s\): we assume \(v\in S\) without loss.¹⁶ We would like to prove for all \(k \in [j+1: m]\), it has \(F_{q, S}(s) \cdot (s - c_j) > F_{q, S}(v) \cdot (v- c_j), \forall v\in (q_k , q_{k + 1}] \cap S\) (recall that \(q_{m + 1} = \infty\)). We prove it by induction:

  1. Given \(k = j+1\) and \(v\in (q_{j+1} , q_{j + 2}] \cap S\), such equality \(F_{q, S}(q_{j+1}) \cdot (q_{j+1} - c_{j+1}) = F_{q, S}(v) \cdot (v- c_{j+1})\) holds.

     Since \(v> q_{j+1} >c_{j+1} > c_{j} \ge 0\) and the function \(h(c) = (v-c)/(q_{j+1} - c)\) is increasing in \(c\) with \(c < q_{j+1}\), then \(\frac{v- c_{j+1}}{q_{j+1} - c_{j+1}} > \frac{v- c_{j}}{q_{j+1} - c_{j}}\). We can derive that \[F_{q, S}(q_{j+1}) \cdot (q_{j+1} - c_{j}) > F_{q, S}(v) \cdot (v- c_{j})~.\] Thus, given \(s \in [q_j, q_{j+1}] \cap S\), we can prove that \[\begin{align} F_{q, S}(s) \cdot (s - c_{j}) > F_{q, S}(v) \cdot (v- c_{j})~. \end{align}\]

  2. Suppose given \(k \ge j+1\), it has \(F_{q, S}(s) \cdot (s - c_j) > F_{q, S}(v) \cdot (v- c_j), ~\forall v\in (q_k , q_{k + 1}] \cap S\), we prove it also holds for \(k+1\). Given \(v\in (q_{k+1}, q_{k+2}] \cap S\), we have \[F_{q, S}(q_{k+1}) \cdot (q_{k+1} - c_{k+1}) = F_{q, S}(v) \cdot (v- c_{k+1})~.\] Similarly, since \(\frac{r - c_{k+1}}{q_{k+1} - c_{k+1}} > 1\) and \(c_{k+1} > c_{j} \ge 0\), we have \(\frac{v- c_{k+1}}{q_{k+1} - c_{k+1}} > \frac{r - c_{j}}{q_{k+1} - c_{j}}\). Then \[F_{q, S}(q_{k+1}) \cdot (q_{k+1} - c_{j}) > F_{q, S}(v) \cdot (v- c_{j})~.\] Since we know \[F_{q, S}(s) \cdot (s- c_{j}) > F_{q, S}(q_{k+1}) \cdot (q_{k+1} - c_{j})~, \quad \forall s\in [q_j, q_{j+1}] \cap S~.\] Thus, given \(s \in [q_j, q_{j+1}] \cap S\), we can prove that \[\begin{align} F_{q, S}(s) \cdot (s - c_{j}) > F_{q, S}(v) \cdot (v- c_{j})~. \end{align}\]

  Thus, we can prove that for the inequality holds for all \(s \in [q_j , q_{j + 1}] \cap S, v\notin [q_j , q_{j + 1}] \cap S\) and \(v>s\);

• if \(v< s\): we assume \(v> c_j\) and \(v\in S\) without loss. We would like to prove for all \(k \in [1, j-1]\), it has \(F_{q, S}(s) \cdot (s - c_j) > F_{q, S}(v) \cdot (v- c_j), ~\forall s \in [q_j , q_{j + 1}] \cap S, v\in [q_k , q_{k + 1}) \cap S\). We prove it by backward induction:

  1. Given \(k = j-1\), for every \(v\in [q_{j-1} , q_{j}) \cap S\) we have \[F_{q, S}(q_j) \cdot (q_j - c_{j-1}) = F_{q, S}(v) \cdot (v- c_{j-1})~,\] based on the first identity. Since \(0<\frac{v- c_{j-1}}{q_j - c_{j-1}} < 1\) and \(0\le c_{j-1} < c_{j}\), we have \(\frac{v- c_{j-1}}{q_j - c_{j-1}} > \frac{v- c_{j}}{q_j - c_{j}}\). Then \[\label{eq:extremal95market95property95proof952} F_{q, S}(q_j) \cdot (q_j - c_{j}) > F_{q, S}(v) \cdot (v- c_{j})~.\tag{3}\] Thus, given \(s \in [q_j, q_{j+1}] \cap S\), we can prove that \[\begin{align} F_{q, S}(s) \cdot (s - c_{j}) > F_{q, S}(v) \cdot (r - c_{j})~. \end{align}\]

  2. Suppose given \(k\), it has \(F_{q, S}(s) \cdot (s - c_j) > F_{q, S}(v) \cdot (v- c_j), ~\forall v\in [q_k , q_{k + 1}) \cap S\), we prove it also holds for \(k-1\). Given \(v\in [q_{k-1}, q_{k}) \cap S\), we have \[F_{q, S}(q_{k}) \cdot (q_{k} - c_{k-1}) = F_{q, S}(v) \cdot (v- c_{k-1})~.\] Similarly, since \(0< \frac{v- c_{k-1}}{q_{k} - c_{k-1}} < 1\) and \(0\le c_{k-1} < c_{j}\), we have \(\frac{v- c_{k-1}}{q_{k} - c_{k-1}} > \frac{v- c_{j}}{q_{k} - c_{j}}\). Then \[F_{q, S}(q_{k}) \cdot (q_{k} - c_{j}) > F_{q, S}(v) \cdot (v- c_{j})~.\] We have the assumption that \[F_{q, S}(s) \cdot (s - c_{j}) > F_{q, S}(q_{k}) \cdot (q_{k} - c_{j}), \quad \forall s\in [q_j, q_{j+1}] \cap S.\] Thus, given \(s \in [q_j, q_{j+1}] \cap S\), we can prove that \[\begin{align} F_{q, S}(s) \cdot (s- c_{j}) > F_{q, S}(q_{k}) \cdot (q_{k} - c_{j}) > F_{q, S}(v) \cdot (v- c_{j})~. \end{align}\]

  Therefore, we conclude that the inequality holds for all \(v\notin [q_j , q_{j + 1}] \cap S\) and \(v< s\).

In summary, when \(q_j \ne \infty\), both the equality and inequality hold. Therefore, the optimal price set \(Q_j(F_{q, S}) = [q_j, q_{j+1}] \cap S\) and the minimum optimal price \(q_j(F_{q, S}) = q_j\). ◻

Proof of 6. In the algorithm we assign \(q_j = q_j(F)\) and recall that 5 proves \(q_j(F_{q, S}) = q_j\), so these three notation stands for the same value. We denote them as \(q_j\) in the remaining proof to simplify the notation. We discuss \(c_j\) in different cases and in each case we prove \(Q_j(F) \subseteq Q_j(\alpha_{q, S} \cdot F_{q, S})\) and \(Q_j(F) \subseteq Q_j(F- \alpha_{q, S} \cdot F_{q, S})\) separately.

7.0.0.1 Suppose \(\max_v(v- c_j ) \cdot F(v) = 0\).

The optimal price set of \(c_j\) in the market \[Q_j(F) = \{v\in \mathcal{V}: (v- c_j) \cdot F(v) = 0\}~.\]

For any \(v> c_j\), since \(F(v) = 0\), then \(v\) is not in the support set of \(F\); thus, \(v\notin S\). Then for any \(v> c_j\), it has \(F_{q, S}(v) = 0\). We can get the optimal set of \(c_j\) in the extremal market \[Q_j(F_{q, S}) = \{v\in \mathcal{V}: (v- c_j) \cdot F_{q, S}(v) = 0\}~.\] We just need to prove if \(F(v) = 0\), then \(F_{q, S}(v) = 0\). When \(F(v) = 0\), it implies for any \(v' > v\), \(F(v') = 0\) also holds; thus, \(F_{q, S}(v) = 0\) also holds. Therefore, for every \(v\in Q_j(F)\), we can derive \(v\in Q_j(F_{q, S})\), which proves \(Q_j(F) \subseteq Q_j(F_{q, S})\).

Since for every \(v\ge c_j\), \(0 \le (v- c_j ) \cdot (F(v) - \alpha_{q, S} \cdot F_{q, S}(v)) \le (v- c_j ) \cdot F(v)\), \(\max_v(v- c_j ) \cdot (F(v) - \alpha_{q, S} \cdot F_{q, S}(v)) = 0\) also holds. Therefore, \[Q_j(F- \alpha_{q, S} \cdot F_{q, S}) = \{v\in \mathcal{V}: (v- c_j) \cdot \left(F(v) - \alpha_{q, S} \cdot F_{q, S}(v)\right) = 0\}~.\] If \(F(v) = 0\), then \(F_{q, S}(v) = 0\), and thus \(F(v) - \alpha_{q, S} \cdot F_{q, S}(v) = 0\). Therefore, for every \(v\in Q_j(F)\), we have \(F(v_i) - \alpha_{q, S} \cdot F_{q, S}(v_i) = 0\). We can derive that \(Q_j(F) \subseteq Q_j(F- \alpha_{q, S} \cdot F_{q, S})\).

7.0.0.2 Suppose \(\max_v(v- c_j ) \cdot F(v) > 0\).

Part 1: we prove \(Q_j(F) \subseteq Q_j(\alpha_{q, S} \cdot F_{q, S})\). Since \(\max_v(v- c_j ) \cdot F(v) \ne 0\), we have \(q_j \in S\). Due to the monotonicity of \(Q_j(F)\), we have \(\max Q_j(F) \le \min Q_{j+1}(F) \le q_{j+1}\) (considering \(q_{j+1}\) is either \(\min Q_{j+1}(F)\) or \(\infty\)). Therefore, \(Q_j(F) \subseteq [q_j, q_{j+1}]\). For any value \(v\in \{v' \in \mathcal{V}: v' \in [q_j, q_{j+1}], v' \notin S\}\), \(F(v) =F(v^{+})\), where \(v^{+} = \min\{v' \in S: v' > v\}\).¹⁷ The seller surplus of \(c_j\) when setting price as \(v\) is \((v-c_j)\cdot F(v) = (v-c_j)\cdot F(v^{+}) <(v^{+} -c_j)\cdot F(v^{+})\), which shows \(v\) is not the optimal price of \(c_j\). Therefore, if the value \(v\in \{v' \in \mathcal{V}: v' \in [q_j, q_{j+1}], v' \notin S\}\), which is not in the support set \(S\), \(v_i \notin Q_j(F)\) as well. Therefore, \(Q_j(F)\subseteq [q_j, q_{j+1}] \cap S= Q_j(F_{q, S})\). We conclude that \(Q_j(F)\subseteq Q_j(F_{q, S})\).

Part 2: we prove \(Q_j(F) \subseteq Q_j(F- \alpha_{q, S} \cdot F_{q, S})\).

Recall that \(q_j \in Q_j(F)\) when the optimal seller revenue is not \(0\), for any \(s \in S\), if \(s \in Q_j(F)\), \[F(q_j)(q_j-c_j) = F(s)(s-c_j)~,\] if \(s \notin Q_j(F)\) \[F(q_j)(q_j-c_j) > F(s)(s-c_j)~.\] Since \(q_j \in Q_j(F)\), we also know that given \(\alpha_{q, S} \in [0,1]\), for all \(s \in Q_j(\alpha_{q, S} \cdot F_{q, S})\), it has \(F_{q, S}(q_j)(q_j-c_j) = F_{q, S}(s)(s-c_j)\). Thus, we can derive that if \(s \in Q_j(\alpha_{q, S} \cdot F_{q, S})\) \[\label{eq:lemma95subset95proof951} (F(q_j) - \alpha_{q, S} \cdot F_{q, S}(q_j)) (q_j - c_j) \ge (F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s-c_j)~,\tag{4}\] where the equality holds if and only if \(s \in Q_j(F)\).
We discuss different cases of \(\alpha\) in the while loop.

• Case 1: \(\alpha = \alpha_{\text{runout}} < \alpha_{\text{shift}}\). Then all the minimum optimal prices \(q_j\), where \(j \in [m]\), remain them same. Thus, \(q(F- \alpha_{q, S} \cdot F_{q, S}) = q(F)\). This indicates that \(q_j(F) \in Q_j(F- \alpha_{q, S} \cdot F_{q,S})\) since we have proved that for all \(s \in Q_j(F)\) \[(F(q_j) - \alpha_{q, S} \cdot F_{q, S}(q_j)) (q_j - c_j) = (F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s-c_j)~,\] we conclude that \(s \in Q_j(F- \alpha_{q, S}\cdot F_{q,S}), ~\forall s \in Q_j(F)\). Thus, \(Q_j(F) \subseteq Q_j(F- \alpha_{q, S}\cdot F_{q,S})\).

• Case 2: \(\alpha = \alpha_{\text{shift}} \le \alpha_{\text{runout}}\). This indicates that some minimum optimal price(s) \(q_j\), where \(j \in [n]\) have been shifted.

  We prove it by contradiction. Assume that for a specific cost \(c_j\), \(Q_j(F) \nsubseteq Q_j(F- \alpha_{q, S} \cdot F_{q, S})\) and \(\max_v(v- c_j) F(v) > 0\). 4 shows that if there exists an element \(s \in Q_j(F)\) and \(s \notin Q_j(F- \alpha_{q, S} \cdot F_{q, S})\), all elements \(s \in Q_j(F)\) satisfies \(s \notin Q_j(F- \alpha_{q, S} \cdot F_{q, S})\). This indicates that there exists a \(s^*\) such that \(s^*\in Q_j(F- \alpha_{q, S} \cdot F_{q, S})\) and \((F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s - c_j) < (F(s^*) - \alpha_{q, S} \cdot F_{q, S}(s^*)) (s^*-c_j)~~ \forall s \in Q_j(F)\). This further implies \(s^* \in S\) and \(F(s^*) - \alpha_{q, S} \cdot F_{q, S}(s^*) > 0\).

  We discuss the possible \(s^*\) by considering different cases:

  • Suppose \(s^* \in [q_j, q_{j+1}] \cap S\). From 4 , we know that \(\forall s \in Q_j(\alpha_{q, S} \cdot F_{q, S})\) \[(F(q_j) - \alpha_{q, S} \cdot F_{q, S}(q_j)) (q_j - c_j) \ge (F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s-c_j)~,\] and \(Q_j(\alpha_{q, S} \cdot F_{q, S}) = [q_j, q_{j+1}] \cap S\), therefore, it is impossible that \(s^* \in [q_j, q_{j+1}]\cap S\).

  • Suppose \(s^* \in (q_{j+1}, + \infty) \cap S\). We would like to prove for all \(k \in [j+1, m]\) it has \((F(q_j) - \alpha_{q, S} \cdot F_{q, S}(q_j))(q_j - c_j) > (F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s-c_j), \forall s \in (q_k, q_{k+1}] \cap S\), therefore, \(s^* \notin (q_{j+1}, + \infty) \cap S\). We prove it by induction.

    1. Given \(s \in(q_{j+1}, q_{j+2}] \cap S\subseteq Q_{j+1}(\alpha_{q, S} \cdot F_{q, S})\) and \(F(s) - \alpha_{q, S} \cdot F_{q, S}(s) > 0\),¹⁸ according to 4 , \[(F(q_{j+1}) - \alpha_{q, S} F_{q, S}(q_{j+1})) (q_{j+1} - c_{j+1}) \ge (F(s) - \alpha_{q, S} F_{q, S}(s)) (s-c_{j+1})~,\] and \[(F(q_j) - \alpha_{q, S} \cdot F_{q, S}(q_j))(q_j - c_j) \ge (F(q_{j+1}) - \alpha_{q, S} \cdot F_{q, S}(q_{j+1}))(q_{j+1} - c_j)~.\] Since \(s-c_{j+1} > q_{j+1} - c_{j+1} > 0\) and \(c_{j+1} > c_{j} \ge 0\), we observe that \(\frac{s-c_{j+1}}{q_{j+1} - c_{j+1}} > \frac{s-c_j}{q_{j+1} - c_{j}}\) \[\frac{F(q_{j+1}) - \alpha_{q, S} \cdot F_{q, S}(q_{j+1})}{F(s) - \alpha_{q, S} \cdot F_{q, S}(s)} \ge \frac{s-c_{j+1}}{q_{j+1} - c_{j+1}} > \frac{s-c_j}{q_{j+1} - c_{j}}~.\]

       Then we can derive that for all \(s \in (q_{j+1}, q_{j+2}] \cap S\) \[\label{eq:lemma95subset95proof952} \begin{align} (F(q_j) - \alpha_{q, S} \cdot F_{q, S}(q_j))(q_j - c_j) & \ge (F(q_{j+1}) - \alpha_{q, S} \cdot F_{q, S}(q_{j+1}))(q_{j+1} - c_j) \\ & > (F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s-c_j)~. \end{align}\tag{5}\]

    2. Suppose given \(k\), it has \((F(q_j) - \alpha_{q, S} \cdot F_{q, S}(q_j))(q_j - c_j) > (F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s-c_j)~, ~~\forall s \in (q_k, q_{k+1}] \cap S\), we prove it also holds for \(k+1\).

       Given \(s \in(q_{k+1}, q_{k+2}] \cap S\subseteq Q_{k+1}(\alpha_{q, S} \cdot F_{q, S})\) and \(F(s) - \alpha_{q, S} \cdot F_{q, S}(s) > 0\), then we have \[(F(q_{k+1}) - \alpha_{q, S} \cdot F_{q, S}(q_{k+1}))(q_{k+1} - c_{k+1}) \ge (F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s-c_{k+1})~.\] Similarly, since \(s-c_{k+1} > q_{k+1} - c_{k+1}\) and \(c_{k+1} > c_j\), we have \(\frac{s-c_{k+1}}{q_{k+1} - c_{k+1}} > \frac{s-c_j}{q_{k+1} - c_{j}} > 0\). Then \[(F(q_{k+1}) - \alpha_{q, S} \cdot F_{q, S}(q_{k+1}))(q_{k+1} - c_{j}) > (F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s-c_{j})~.\] Therefore, \[\begin{align} (F(q_j) - \alpha_{q, S} \cdot F_{q, S}(q_j))(q_j - c_j) & > (F(q_{j+2}) - \alpha_{q, S} \cdot F_{q, S}(q_{j+2}))(q_{j+2} - c_j) \\ & > (F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s-c_j)~. \end{align}\]

    For all \(s \in (q_j, + \infty) \cap S\), we have \[\begin{align} (F(q_j) - \alpha_{q, S} \cdot F_{q, S}(q_j))(q_j - c_j) > (F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s-c_j)~. \end{align}\] That implies we could not find \(s^* > q_{j+1}\) such that \((F(q_j) - \alpha_{q, S} \cdot F_{s, S}(s)) (q_j - c_j) < (F(s^*) - \alpha_{q, S} \cdot F_{q, S}(s^*)) (s^*-c_j)\).

  • Suppose \(s^* < q_j\). We assume \(s^* > c_j\) without loss, then \[F_{q,S}(s)(s-c_{j}) < F_{q,S}(q_{j})(q_{j}- c_{j}), ~~ \forall s \in (c_j,q_j) \cap S.\] Given \(s \in (c_j,q_j) \cap S\), we define a function \[g(\alpha) = \frac{(F(q_{j}) - \alpha_{q, S} \cdot F_{q, S}(q_{j})) (q_j - c_j)}{(F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s - c_j)}~.\] We also assume that \(F(s) - \alpha_{q, S} \cdot F_{q, S}(s) > 0\),. Since \(F_{q, S}(s) \ge F_{q, S}(q_j) > 0\) the monotonicity of the function can be discussed in different cases for different \(s\):

    • If \(\frac{F_{q, S}(q_{j})}{F_{q, S}(s)} \le \frac{F(q_{j})}{F(s)}\), \(g(\alpha)\) is non-decreasing when \(\alpha\) increases continuously from \(0\). Therefore, \(g(\alpha) \ge \frac{F(q_{j}) (q_j - c_j)}{F(s) (s - c_j)} > 1\). This shows for any \(\alpha\), \((F(q_{j}) - \alpha_{q, S} \cdot F_{q, S}(q_{j})) (q_j - c_j)> (F(s^*) - \alpha_{q, S} \cdot F_{q, S}(s)) (s - c_j)\) holds.

    • If \(\frac{F_{q, S}(q_{j})}{F_{q, S}(s)} > \frac{F(q_{j})}{F(s)}\), \(g(\alpha)\) is monotonically decreasing from \(\frac{F(q_{j}) (q_j - c_j)}{F(s) (s - c_j)} > 1\). When we increase \(\alpha\) continuously from \(0\) till we find \(\alpha_{q,S}\) satisfying \[(F(q_{j}) - \alpha_{q, S} \cdot F_{q, S}(q_{j})) (q_j - c_j) = (F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s - c_j)~,\] for some \(s \in (c_j,q_j) \cap S\). When this occurs, it triggers the 2(b) since \(q_j(F-\alpha^*\cdot F_{q,S})\) changes to \(s\) and \(\alpha\) stops increasing. Therefore, it still satisfies for all \(s \in (c_j,q_j) \cap S\) \[(F(q_{j}) - \alpha_{q, S} \cdot F_{q, S}(q_{j})) (q_j - c_j) \ge (F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s - c_j)~.\]

    Thus, we could not find a \(s^* \in (c_j, q_j) \cap S\) such that \((F(s) - \alpha_{q, S} \cdot F_{q, S}(s)) (s - c_j) < (F(s^*) - \alpha_{q, S} \cdot F_{q, S}(s^*)) (s^*-c_j)\) for any \(s \in Q_j(F)\).

  Since we can not find \(s^* \in S\) satisfying the condition we give, that indicates that \(Q_j(F) \subseteq Q_j(F- \alpha_{q, S} \cdot F_{q, S})\).

Combining \(Q_j(F) \subseteq Q_j(\alpha_{q, S} \cdot F_{q, S})\) and \(Q_j(F) \subseteq Q_j(F- \alpha_{q, S} \cdot F_{q, S})\), we complete the proof. ◻

Proof of 7. There are two conditions that could trigger \(\alpha_{q,S}\) stopping increasing. We analyze the number of iteration for those two cases of \(\alpha\) separately:

• if \(\alpha = \alpha_{\text{runout}} \le \alpha_{\text{shift}}\): Probability runs out at some \(v\): \(\alpha_{q, S} \cdot f_{q, S}(v) = f(v)\) for some \(v \in \mathcal{V}\), it could happen at most \(n = |\mathcal{V}|\) times;

• if \(\alpha = \alpha_{\text{shift}} < \alpha_{\text{runout}}\): In iteration \(k = 1,\dots, K\), we denote the targeted market as \(F^{(k)}\), the extremal market as \(F_{q^{(k)}, S^{(k)}}\) and its corresponding weight as \(\alpha_{q^{(k)}, S^{(k)}}\). Then \(F^{(1)} \leftarrow F\). For a specific \(c_j\), where its seller surplus in the original market \(\max_v(v-c_{j})\cdot F(v) \ne 0\), assume \(q_j\) shifts at iteration \((j_1, j_2,\dots, j_{K_j}, j_{K_{j+1}})\), where the iteration \(j_{K_{j+1}}\) is when \(q_j\) becomes \(\infty\). Since \(q_j = \infty\) also satisfies the first case ( probability at some values runs out), it is not counted in the current situation. Then \(K_j\) the number of shifts of \(q_j\) before becoming \(\infty\). This implies throughout iterations \(k \in \{j_1, j_2,\dots, j_{K_j}\}\), the seller surplus of all \(c_{j'}\) where \(j' \le j\) satisfies \(\max_v(v-c_{j'})\cdot F^{(k)}(v) > 0\). Due to the monotonicity of \(Q_{j-1}(F)\), \[\max Q_{j-1}(F^{(k)}) \le \min Q_{j}(F^{(k)}),~~ \forall k \in \{j_1, j_2,\dots, j_{K_j}\}~.\] Recall that we prove the optimal price set weakly expands in 6, we have \[Q_{j-1}(F)= Q_{j-1}(F^{(1)}) \subseteq \dots \;Q_{j-1}(F^{(j_{K_j})})~.\] Then in all iterations \(k \in \{j_1, j_2,\dots, j_{K_j}\}\), \(\max Q_{j-1}(F) \in Q_{j-1}(F^{(k)})\) always holds and further \[\max Q_{j-1}(F) \le \max Q_{j-1}(F^{(j_{K_j})}) \le \min Q_j(F^{(j_{K_j})})~.\] Therefore, the number of iteration \(K_j\) is bounded by \[K_j \le \left|\bigl[\max Q_{j-1}(F), \min Q_{j}(F)\bigr)\cap \mathcal{V}\right|~.\] Summing over all \(j\), we can derive that the upper bound of the total number of iterations \[\sum\nolimits_j{K_j} \le \sum\nolimits_j \left|\bigl[\max Q_{j-1}(F), \min Q_{j}(F)\bigr)\cap \mathcal{V}\right| \le |\mathcal{V}| = n~.\]

Combining these two situations, we can prove that it takes at most \(2n\) iterations to decompose a market \(F\) into extremal markets. ◻

Proof of 3. We prove that the decomposition procedure described in 2 is a way to construct \(F\) and it preserves both the seller surplus and the buyer surplus. In iteration \(k = 1,\dots, K\), we denote the targeted market by \(F^{(k)}\), the extremal market by \(F_{q^{(k)}, S^{(k)}}\) and its corresponding weight by \(\alpha_{q^{(k)}, S^{(k)}}\). \(F^ 1 \leftarrow F\). Therefore, we could decompose \(F\) into \(\sum_{k=1}^K\alpha_{q^{(k)}, S^{(k)}} \cdot F_{q^{(k)}, S^{(k)}}\) and \(K \le 2n\) since 7 have proved that there are at most \(2n\) iterations.

7.0.0.3 The seller surplus and buyer surplus is preserved in the decomposition procedure.

Recall 6 we have \[Q_j(F^{(k)}) \subseteq Q_j\left(\alpha_{q^{(k)}, S^{(k)}} \cdot F_{q^{(k)}, S^{(k)}}\right) \cap Q_j\left(F^{(k+1)}\right)~.\] Then given the market \(F\), \[Q_j(F) \subseteq \bigcap_{k\in[K]} Q_j\left(\alpha_{q^{(k)}, S^{(k)}} \cdot F_{q^{(k)}, S^{(k)}}\right) = \bigcap_{k\in[K]} Q_j\left(F_{q^{(k)}, S^{(k)}}\right)~,\] Since the procedure ends when the remaining market is zero, for \(v\in \mathcal{V}\), it satisfies \[F(v) = \sum\nolimits_{k\in[K]} \alpha_{q^{(k)}, S^{(k)}} \cdot F_{q^{(k)}, S^{(k)}}(v)~,\] and \[f(v) = \sum\nolimits_{k\in[K]} \alpha_{q^{(k)}, S^{(k)}} \cdot f_{q^{(k)}, S^{(k)}}(v)~.\] If we choose optimal price \(\mu_j\) for cost \(c_j\) in \(F\), then \(\mu_j> c_j\) and \(\mu_j\in Q_j(F)\). Thus, \[\mu_j \in Q_j(F_{q^{(k)}, S^{(k)}}), ~ k=1,2,\dots, K~.\] This indicates that we can choose \(\mu_j\) as the optimal price for each extremal market \(F_{q^{(k)}, S^{(k)}}, ~ k=1,2,\dots, K\) to get the seller surplus \(\textsf{SS}(F_{q^{(k)}, S^{(k)}}) = \sum\nolimits_{j}g(c_j) \cdot (\mu_j - c_j)F_{q^{(k)}, S^{(k)}}(\mu_j)\), where \(g(c_j)\) is the probability of \(c_j\). Then the seller surplus of \(F\), denoted as \(\textsf{SS}(F)\), is \[\begin{align} \textsf{SS}(F) & = \sum\nolimits_{j}g(c_j) \cdot (\mu_j - c_j)\cdot F(\mu_j)\\ & = \sum\nolimits_{j}g(c_j) \cdot (\mu_j - c_j)\sum\nolimits_{k\in[K]} \alpha_{q^{(k)}, S^{(k)}} \cdot F_{q^{(k)}, S^{(k)}}(\mu_j)\\ & = \sum\nolimits_{k\in[K]} \alpha_{q^{(k)}, S^{(k)}} \sum\nolimits_{j}g(c_j) \cdot (\mu_j - c_j) \cdot F_{q^{(k)}, S^{(k)}}(\mu_j) \\ & = \sum\nolimits_{k\in[K]} \alpha_{q^{(k)}, S^{(k)}}\cdot \textsf{SS}(F_{q^{(k)}, S^{(k)}})~. \end{align}\]

Similarly, the buyer surplus of \(F\), denoted as \(\textsf{BS}(F)\), is \[\begin{align} \textsf{BS}(F) & = \sum\nolimits_j g(c_j) \sum\nolimits_{v_i > \mu_j}(v_i - \mu_j)\cdot f(v_i) \\ & = \sum\nolimits_jg(c_j) \sum\nolimits_{v_i > \mu_j}(v_i - \mu_j)\sum\nolimits_{k\in[K]} \alpha_{q^{(k)}, S^{(k)}} \cdot f_{q^{(k)},S^{(k)}}(v_i)\\ & = \sum\nolimits_{k\in[K]} \alpha_{q^{(k)}, S^{(k)}} \sum\nolimits_jg(c_j)\sum\nolimits_{v_i > \mu_j}(v_i - \mu_j) \cdot f_{q^{(k)},S^{(k)}}(v_i) \\ & = \sum\nolimits_{k\in[K]} \alpha_{q^{(k)}, S^{(k)}}\cdot \textsf{BS}(F_{q^{(k)}, S^{(k)}})~. \end{align}\] We conclude that the convex combination of extremal markets \(F=\sum_{k\in[K]} \alpha_{q^{(k)}, S^{(k)}} F^{(k)}_{q, S}\) preserve both the seller surplus and the buyer surplus. ◻

Proof of 8. Given a \({\bar F}_{q, S, j}\) obtained by an extremal market \(F_{q, S}\) and the corresponding cost \(c_j\), define \(w_{q, S, j} := F_{q,S}(q_{j})\) and \(T:= S\cap [q_j, q_{j+1})\). Assume \(w_{q, S, j} > 0\).¹⁹ It satisfies \((q_j - c_j)\cdot F_{q, S}(q_j) = (v- c_j)\cdot F_{q, S}(v) \; \forall v\in T\cup \{q_{j+1}\}\), according to [lem:optimal95price95for95extremal95market].

For any \(v\in T\), we find \(v^{+}\) such that \(v^{+} = \min \{v' \in T\cup \{q_{j+1}\}: v' > v\}\), \(f_{q, S}(v) = F_{q, S}(v) - F_{q, S}(v^{+})\). \[\begin{align} {\bar f}_{q, S}(v) = \frac{f_{q, S}(v)}{w_{q, S, j}} = \frac{F_{q, S}(v)}{F_{q,S}(q_{j})} - \frac{F_{q, S}(v^{+})}{F_{q,S}(q_{j})} = \frac{q_j - c_j}{v- c_j} - \frac{q_j - c_j}{v^{+} - c_j}~. \end{align}\] Thus, \[\begin{align} {\bar F}_{q, S, j}(v) = \sum\nolimits_{v' \ge v} {\bar f}_{q, S}(v') = \frac{q_j - c_j}{v- c_j} - \frac{q_j - c_j}{q_{j+1} - c_j}~. \end{align}\]

We observe that \({\bar F}_{q, S, j}(v)\) and \({\bar f}_{q, S}(v)\) are uniquely determined by \(q_j\), \(q_{j+1}\) \(c_j\), and \(v\). Therefore, the fragment \({\bar F}_{q, S, j}\) is determined by the triple \((q_j, q_{j+1}, T)\). ◻

Proof of 9. Seller surplus induced by \(\boldsymbol{\alpha}\). Given an extremal market \(F_{q, S}\) in an extremal market decomposition \(\boldsymbol{\alpha}= (\alpha_{q, S})\) and a specific cost \(c_j\), the contribution to the seller surplus is \(\alpha_{q, S} \cdot g(c_j) \cdot (q_j - c_j) \cdot F(q_j)\). According to the fragment decomposition of the extremal market defined in 3, \(w_{j, \ell, r, T}^{q, S} = F(q_j)\) when \(v_\ell = q_j, v_r = q_{j+1}\) and \(T = S\cap [q_j, q_{j+1})\). Otherwise, 0 Then we can charge the seller surplus induced by the pair \((F_{q, S}, c_j)\) to the specific fragment \({\bar F}_{j, \ell, r, T}\) with the number \(\alpha_{q, S} \cdot g(c_j) \cdot (q_j - c_j) \cdot w_{j, \ell, r, T}^{q, S}\), where \(v_\ell = q_j, v_r = q_{j+1}\) and \(T = S\cap [q_j, q_{j+1})\).

Therefore, we can define the seller surplus contribution of the quadruple \((j, \ell, r, T)\) induced by each extremal market \(F_{q, S}\) as \(\alpha_{q, S} \cdot g(c_j) \cdot (v_\ell - c_j) \cdot w_{j, \ell, r, T}^{q, S}\). Note that the contribution is \(0\) when either \(v_\ell \ne q_j\) or \(v_r \ne q_{j+1}\) or \(T\ne S\cap [q_j, q_{j+1})\), since \(w_{j, \ell, r, T}^{q, S} = 0\).

The overall seller surplus of \(\boldsymbol{\alpha}\), denoted by \(\textsf{SS}(\boldsymbol{\alpha})\), is \[\label{eq:32seller32surplus32of32fragment32decomposition} \begin{align} \textsf{SS}(\boldsymbol{\alpha}) & = \sum\nolimits_{q, S}\sum\nolimits_j \alpha_{q, S} \cdot g(c_j) \cdot (q_{j} - c_j)\cdot F_{q, S}(q_j) \\ & = \sum\nolimits_{q, S} \sum\nolimits_{j, \ell, r, T} \alpha_{q, S} \cdot g(c_j) \cdot (q_j - c_j) \cdot w_{j, \ell, r, T}^{q, S} \\ & = \sum\nolimits_{j, \ell, r, T} g(c_j) \cdot (v_\ell - c_j)\sum\nolimits_{q, S} \alpha_{q, S} \cdot w_{j, \ell, r, T}^{q, S} \\ & = \sum\nolimits_{j, \ell, r, T} g(c_j)\cdot (v_\ell - c_j) \cdot w_{j, \ell, r, T} ~. \end{align}\tag{6}\] We can prove that the seller surplus \(\textsf{SS}(\boldsymbol{\alpha})\) is linear to \(\boldsymbol{w}\).

Buyer surplus induced by \(\boldsymbol{\alpha}\).Since the buyer surplus of the extremal market decomposition \(\boldsymbol{\alpha}\), denoted by \(\textsf{BS}(\boldsymbol{\alpha})\), is the difference between social welfare \(\textsf{SW}(\boldsymbol{\alpha})\) and seller surplus \(\textsf{SS}(\boldsymbol{\alpha})\), we prove that the maximum/minimum buyer surplus is linear to \(\boldsymbol{w}\) by proving the maximum/minimum social welfare is linear to \(\boldsymbol{w}\). For social welfare, if we choose optimal price \(\mu_{q, S, j}\) for cost \(c_j\) in the extremal market \(F_{q, S}\), where \(\mu_{q, S, j} \in Q_j(F_{q, S}) = S\cap [q_j, q_{j+1}]\), then \[\begin{align} \textsf{SW}(\boldsymbol{\alpha}) & = \sum\nolimits_{q, S} \alpha_{q, S} \sum\nolimits_j g(c_j) \sum\nolimits_{v\ge \mu_{q, S, j}} (v- c_j) \cdot f_{q, S}(v)~. \end{align}\] We get maximum social welfare when \(\mu_{q, S, j} = q_j\), which is the minimum optimal price, for each cost in all extremal markets. The maximum social welfare is equal to \[\begin{align} \textsf{SW}_{\text{max}}(\boldsymbol{\alpha}) = \sum\nolimits_{q, S} \alpha_{q, S} \sum\nolimits_j g(c_j) \sum\nolimits_{v\ge q_j} (v- c_j) \cdot f_{q, S}(v)~. \end{align}\] Fix an extremal market \(F_{q, S}\) in extremal market decomposition \(\boldsymbol{\alpha}\) and a specific cost \(c_j\), then the contribution to the maximum social welfare is \[\begin{align} & \alpha_{q, S} \cdot g(c_j) \sum\nolimits_{v\ge q_j} (v- c_j) \cdot f_{q, S}(v) \\ = ~& \sum\nolimits_{j'\ge j} \alpha_{q, S} \cdot g(c_j) \sum\nolimits_{v\in[q_{j'}, q_{j'+1})} (v- c_j) \cdot f_{q, S}(v)\\ = ~ & \sum\nolimits_{j'\ge j} \alpha_{q, S} \cdot g(c_j) \sum\nolimits_{v\in T_{j'}} (v- c_j) \cdot w_{j', \ell_{j'}, r_{j'}, T_{j'}}^{q, S} \cdot {\bar f}_{j', \ell_{j'}, r_{j'}, T_{j'}}(v)~, \end{align}\] where \(v_{\ell_{j'}} = q_{j'}\), \(v_{r_{j'}} = q_{j'+1}\), and \(T_{j'} = S\cap [q_{j'}, q_{j'+1})\) for each \(j'\). Then we charge the social welfare to each fragment \({\bar F}_{j', \ell_{j'}, r_{j'}, T_{j'}}\) where \(j' \ge j\), with the amount \(\alpha_{q, S} \cdot g(c_j) \sum\nolimits_{v\in T_{j'}} (v- c_j) \cdot w_{j', \ell_{j'}, r_{j'}, T_{j'}}^{q, S} \cdot {\bar f}_{j', \ell_{j'}, r_{j'}, T_{j'}}(v)\). This can be expanded for other \((j', \ell, r, T)\) where \(v_\ell \ne q_{j'}\) or \(v_r \ne q_{j'+1}\) or \(T\ne S\cap [q_{j'}, q_{j'+1})\) since \(w_{j', \ell, r, T}^{q, S} = 0\) and the social welfare charged is \(0\). Thus, \[\begin{align} \alpha_{q, S} \cdot g(c_j) \sum\nolimits_{v\ge q_j} (v- c_j) \cdot f_{q, S}(v) = \sum\nolimits_{j'\ge j} \alpha_{q, S} \cdot g(c_j) \sum\nolimits_{\ell, r, T} \sum\nolimits_{v\in T} (v- c_j) \cdot w_{j', \ell, r, T}^{q, S} \cdot {\bar f}_{j', \ell, r, T}(v)~, \end{align}\] Now we consider the social welfare charged to each fragment \({\bar F}_{j, \ell,r, T}\). Given a quadruple \((j, \ell,r, T)\), we sum over the social welfare induced by all extremal markets \(F_{q, S}\) and \(c_{j'}, j' \le j\), the value is \(\sum_{q, S} \sum_{j' \le j}\alpha_{q, S} \cdot g(c_{j'}) \sum_{v\in T}(v- c_{j'}) \cdot {\bar f}_{j, \ell, r, T}(v) \cdot w_{j, \ell, r, T}^{q, S}\). Therefore, we can rewrite the maximum social welfare as \[\label{eq:32maximum32social32welfare32of32fragment32decomposition} \begin{align} \textsf{SW}_{\text{max}}(\boldsymbol{\alpha}) & = \sum\nolimits_{j, \ell,r, T} \sum\nolimits_{q, S} \sum\nolimits_{j' \le j}\alpha_{q, S} \cdot g(c_{j'}) \sum\nolimits_{v\in T}(v- c_{j'}) \cdot {\bar f}_{j, \ell, r, T}(v) \cdot w_{j, \ell, r, T}^{q, S} \\ & = \sum\nolimits_{j, \ell,r, T} \sum\nolimits_{j' \le j}\sum\nolimits_{v\in T}g(c_{j'}) \cdot (v- c_{j'}) \cdot {\bar f}_{j, \ell, r, T}(v) \sum\nolimits_{q, S} \alpha_{q, S} \cdot w_{j, \ell, r, T}^{q, S}\\ & = \sum\nolimits_{j, \ell,r, T} \sum\nolimits_{j' \le j}\sum\nolimits_{v\in T}g(c_{j'}) \cdot (v- c_{j'}) \cdot {\bar f}_{j, \ell, r, T}(v) \cdot w_{j, \ell, r, T}~. \end{align}\tag{7}\] Thus, \(\textsf{SW}_{\text{max}}(\boldsymbol{\alpha})\) is a linear combination of \(\boldsymbol{w}\). Since \(\textsf{BS}_{\text{max}}(\boldsymbol{\alpha}) = \textsf{SW}_{\text{max}}(\boldsymbol{\alpha}) - \textsf{SS}(\boldsymbol{\alpha})\), \(\textsf{BS}_{\text{max}}(\boldsymbol{\alpha})\) is also linear to \(\boldsymbol{w}\).

Similarly, we get minimum social welfare when \(\mu_{q, S, j} = q_{j+1}\) for each cost in all extremal markets: \[\begin{align} \textsf{SW}_{\text{min}}(\boldsymbol{\alpha}) = \sum\nolimits_{q, S} \alpha_{q, S} \sum\nolimits_j g(c_j) \sum\nolimits_{v\ge q_{j+1}} (v- c_j) \cdot f_{q, S}(v)~. \end{align}\] Fix an extremal market \(F_{q, S}\) in extremal market decomposition \(\boldsymbol{\alpha}= (\alpha_{q, S})\) and a specific cost \(c_j\), the contribution to the minimum social welfare is \[\begin{align} & \alpha_{q, S} \cdot g(c_j) \sum\nolimits_{v\ge q_{j+1}} (v- c_j) \cdot f_{q, S}(v) \\ = ~& \sum\nolimits_{j' \ge j+1} \alpha_{q, S} \cdot g(c_j) \sum\nolimits_{v\in[q_{j'}, q_{j'+1})} (v- c_j) \cdot f_{q, S}(v)\\ = ~ & \sum\nolimits_{j'\ge j+1} \alpha_{q, S} \cdot g(c_j) \sum\nolimits_{v\in T_{j'}} (v- c_j) \cdot w_{j', \ell_{j'}, r_{j'}, T_{j'}}^{q, S} \cdot {\bar f}_{j', \ell_{j'}, r_{j'}, T_{j'}}(v)~, \end{align}\] where \(v_{\ell_{j'}} = q_{j'}\), \(v_{r_{j'}} = q_{j'+1}\), and \(T_{j'} = S\cap [q_{j'}, q_{j'+1})\) for each \(j'\), \(\ell_{j'}\). Then we charge the social welfare to each fragment \({\bar F}_{j', \ell_{j'}, r_{j'}, T_{j'}}\) where \(j' \ge j+1\), with the amount \(\alpha_{q, S} \cdot g(c_j) \sum\nolimits_{v\in T_{j'}} (v- c_j) \cdot w_{j', \ell_{j'}, r_{j'}, T_{j'}}^{q, S} \cdot {\bar f}_{j', \ell_{j'}, r_{j'}, T_{j'}}(v)\). This can be expanded for other \((j', \ell, r, T)\) where \(\ell \ne q_{j'}\) or \(r \ne q_{j'+1}\) or \(T\ne S\cap [q_{j'}, q_{j'+1})\) since \(w_{j', \ell, r, T}^{q, S} = 0\) and the social welfare charged is \(0\). Thus, \[\begin{align} \alpha_{q, S} \cdot g(c_j) \sum\nolimits_{v\ge q_{j+1}} (v- c_j) \cdot f_{q, S}(v) = \sum\nolimits_{j'\ge j+1} \alpha_{q, S} \cdot g(c_j) \sum\nolimits_{\ell, r, T} \sum\nolimits_{v\in T} (v- c_j) \cdot w_{j', \ell, r, T}^{q, S} \cdot {\bar f}_{j', \ell, r, T}(v)~, \end{align}\]

When we consider the overall minimum social welfare charged to each fragment \({\bar F}_{j, \ell, r, T}\), we sum over the social welfare charged from all extremal markets and \(c_{j'}, j' < j\) (strictly less than), the value is \(\sum\nolimits_{q, S} \sum\nolimits_{j' < j}\alpha_{q, S} \cdot g(c_{j'}) \sum\nolimits_{v\in T}(v- c_{j'}) \cdot {\bar f}_{j,\ell, r, T}(v) \cdot w_{j, \ell, r, T}^{q, S}\). Therefore, we can rewrite the minimum social welfare as \[\label{eq:32minimum32social32welfare32of32fragment32decomposition} \begin{align} \textsf{SW}_{\text{min}}(\boldsymbol{\alpha}) & = \sum\nolimits_{j, \ell, r, T} \sum\nolimits_{q, S} \sum\nolimits_{j' <j}\alpha_{q, S} \cdot g(c_{j'}) \sum\nolimits_{v\in T}(v- c_{j'}) \cdot {\bar f}_{j,\ell, r, T}(v) \cdot w_{j, \ell, r, T}^{q, S} \\ & = \sum\nolimits_{j, \ell,r, T} \sum\nolimits_{j' < j}\sum\nolimits_{v\in T}g(c_{j'}) \cdot (v- c_{j'}) \cdot {\bar f}_{j,\ell, r, T}(v) \sum\nolimits_{q, S} \alpha_{q, S} \cdot w_{j, \ell, r, T}^{q, S}\\ & = \sum\nolimits_{j, \ell,r, T} \sum\nolimits_{j' < j}\sum\nolimits_{v\in T}g(c_{j'}) \cdot (v- c_{j'}) \cdot {\bar f}_{j,\ell, r, T}(v) \cdot w_{j, \ell, r, T}~. \end{align}\tag{8}\] Thus, \(\textsf{SW}_{\text{min}}(\boldsymbol{\alpha})\) is a linear combination of \(\boldsymbol{w}\). Since \(\textsf{BS}_{\text{min}}(\boldsymbol{\alpha}) = \textsf{SW}_{\text{min}}(\boldsymbol{\alpha}) - \textsf{SS}(\boldsymbol{\alpha})\), \(\textsf{BS}_{\text{min}}(\boldsymbol{\alpha})\) is also linear to \(\boldsymbol{w}\). ◻

Proof of 10. According to the definition of undominated fragment \({\bar F}_{j, \ell, r}\), where \(j \in [m]\), \(\ell \in [n]\) and \(r\in [n+1]\), there are at most \(O(mn^2)\) possible undominated fragments. ◻

Proof of 11. Given a fragment \({\bar F}_{j, \ell, r, T}\), recall the tail function of the fragment in 8, \[{\bar F}_{j, \ell, r, T}(v) = \frac{v_\ell - c_j}{v- c_j} - \frac{v_\ell - c_j}{v_r - c_j}, \quad \forall v\in T~.\]

The undominated fragment \({\bar F}_{j, \ell, r}\) is also a fragment with the same \(j, \ell, r\), while its support set is \(\mathcal{V}\cap [v_l, v_r)\). Thus, \[{\bar F}_{j, \ell, r}(v) = \frac{v_\ell - c_j}{v- c_j} - \frac{v_\ell - c_j}{v_r - c_j}, \quad \forall v\in \mathcal{V}\cap [v_l, v_r)~.\] Since \(T\subseteq \mathcal{V}\cap [v_\ell, v_r)\), given \(v\in \mathcal{V}\cap [v_l, v_r)\) it has two cases:

• \(v\in T\), then \({\bar F}_{j, \ell, r, T}(v) = {\bar F}_{j, \ell, r}(v)\)

• \(v\notin T\), then \({\bar F}_{j, \ell, r, T}(v) = {\bar F}_{j, \ell, r, T}(v^{+}) = {\bar F}_{j, \ell, r}(v^{+}) < {\bar F}_{j, \ell, r}(v)\), where \(v^{+} = \min \{v' \in T\cap [v_\ell, v_r): v' > v\}\). ²⁰

Therefore, we can prove that \({\bar F}_{j, \ell, r}\) first-order stochastically dominates \({\bar F}_{j, \ell, r, T}\). ◻

Proof of 12. Recall that the fragment \({\bar F}_{j,\ell,r}\) has support on \(\{v_i:\, i\in [\ell, r)\}\) and the induced market \(F^{z}_{j,\ell,r}\)’s support is the subset of \(\{v_i:\, i\in [\ell, r)\}\). Moreover, for \(v\ge v_r\), both sides are \(0\) and for \(v< v_\ell\) both sides equal their total masses. Therefore, it suffices to prove the inequality for \(v=v_i\) with \(i \in [\ell, r)\). Then for any \(i \in [\ell: r)\), \[\begin{align} F^{z}_{j, \ell, r}(v_i) & = \sum\nolimits_{i' \in [i: r)} z_{j, \ell, r, i'} \\ & = \sum\nolimits_{i' \in [i: r)} \sum_{ T\subseteq \mathcal{V}\cap [v_\ell, v_r)} w_{j, \ell, r, T} \cdot {\bar f}_{j, \ell, r, T}(v_{i'}) \\ & = \sum\nolimits_{ T\subseteq \mathcal{V}\cap [v_\ell, v_r)} w_{j, \ell, r, T} \sum\nolimits_{i' \in [i: r)} {\bar f}_{j, \ell, r, T}(v_{i'}) \\ & = \sum\nolimits_{ T\subseteq \mathcal{V}\cap [v_\ell, v_r)} w_{j, \ell, r, T} \cdot {\bar F}_{j, \ell, r, T}(v_{i})~. \end{align}\] We invoke the domination relationship between the fragment \({\bar F}_{j, \ell, r, T}\) and the reduced fragment \({\bar F}_{j, \ell, r}\) in 11 to get \[\sum\nolimits_{ T\subseteq \mathcal{V}\cap [v_\ell, v_r)} w_{j, \ell, r, T} \cdot {\bar F}_{j, \ell, r, T}(v_{i}) \le \sum\nolimits_{ T\subseteq \mathcal{V}\cap [v_\ell, v_r)} w_{j, \ell, r, T} \cdot {\bar F}_{j, \ell, r}(v_{i}) = x_{j, \ell, r} \cdot {\bar F}_{j,\ell,r}(v_{i})~.\] Thus, for any \(i \in [\ell: r)\) , it has \(F^{z}_{j, \ell, r}(v_i) \le x_{j, \ell, r} \cdot {\bar F}_{j,\ell,r}(v_{i})\). Therefore, the induced \(F^{z}_{j, \ell, r}\) is weakly dominated by the fragment \({\bar F}_{j,\ell,r}\) scaled by \(x_{j, \ell, r}\).

According to the definition of fragment \({\bar F}_{j, \ell, r, T}\) (in 2), the point mass \({\bar f}_{j, \ell, r, T}( v) = 0\) when \(v\notin [v_\ell, v_r)\). Then \[\begin{align} \sum\nolimits_{i \in [n]}z_{j, \ell, r, i} & = \sum\nolimits_{i \in [n]}\sum\nolimits_{ T\subseteq \mathcal{V}\cap [v_\ell, v_r)} w_{j, \ell, r, T} \cdot {\bar f}_{j, \ell, r, T}(v_i) \\ & = \sum\nolimits_{i \in [\ell: r)}\sum\nolimits_{ T\subseteq \mathcal{V}\cap [v_\ell, v_r)} w_{j, \ell, r, T} \cdot {\bar f}_{j, \ell, r, T}(v_i)\\ & = \sum\nolimits_{ T\subseteq \mathcal{V}\cap [v_\ell, v_r)} w_{j, \ell, r, T} \sum\nolimits_{i \in T} {\bar f}_{j, \ell, r, T}(v_i)\\ & = \sum\nolimits_{ T\subseteq \mathcal{V}\cap [v_\ell, v_r)} w_{j, \ell, r, T} \cdot (1- \frac{v_\ell - c_j}{v_r - c_j})\\ & = \frac{v_r - v_\ell}{v_r - c_j}\cdot x_{j, \ell, r}~. \end{align}\] We complete the proof. ◻

Proof of 1. Fix an extremal market decompoisition \(\boldsymbol{\alpha}\). Let \(\boldsymbol{w}= (w_{j, \ell, r, T})\) be its corresponding fragment decomposition and \((\boldsymbol{x}, \boldsymbol{z})\), where \(\boldsymbol{x}= (x_{j,\ell, r})\) and \(\boldsymbol{z}=(z_{j, \ell, r, i})\), be the reduced fragment decomposition. According to 9 and 6 , the seller surplus of fragment decomposition induced by \(\boldsymbol{\alpha}\) is linear to \(\boldsymbol{w}\). Specifically, the seller surplus \(\textsf{SS}(\boldsymbol{\alpha}) = \sum_{j, \ell, r, T} g(c_j) \cdot (v_\ell - c_j) \cdot w_{j, \ell, r, T}\). Since the fragment \({\bar F}_{j, \ell, r, T}\) is defined only for \(T\subseteq \mathcal{V}\cap [v_\ell, v_r)\) by 1; otherwise, \({\bar F}_{j, \ell, r, T}\) is not defined and \(w_{j, \ell, r, T}\) does not exist, the seller surplus \(\textsf{SS}(\boldsymbol{\alpha})\) equals \[\label{eq:32seller32surplus32charged32by32x} \begin{align} \textsf{SS}(\boldsymbol{\alpha}) & = \sum\nolimits_{j, \ell, r, T} g(c_j) \cdot (v_\ell - c_j) \cdot w_{j, \ell, r, T} \\ & = \sum\nolimits_{j, \ell, r} g(c_j) \cdot (v_\ell - c_j) \sum\nolimits_{{ T\subseteq \mathcal{V}\cap [v_\ell, v_r)}} w_{j, \ell, r, T}\\ & = \sum\nolimits_{j, \ell, r} g(c_j) \cdot (v_\ell - c_j) \cdot x_{j, \ell, r}~. \end{align}\tag{9}\] We can prove that \(\textsf{SS}(\alpha)\) is linear to \(\boldsymbol{x}\).

For the maximum social welfare, according to 9 and 7 , the maximum social welfare induced by \(\boldsymbol{\alpha}\) is linear to \(\boldsymbol{w}\), and specifically, \[\label{eq:32maximum32social32welfare32charged32by32z} \begin{align} \textsf{SW}_{\text{max}}(\boldsymbol{\alpha}) & = \sum\nolimits_{j, \ell, r, T} \sum\nolimits_{j' \le j}\sum\nolimits_{v\in T} g(c_{j'}) \cdot (v- c_{j'}) \cdot {\bar f}_{j, \ell, r, T}(v) \cdot w_{j, \ell, r, T}\\ & = \sum\nolimits_{j, \ell, r} \sum\nolimits_{T\subseteq \mathcal{V}\cap [v_\ell, v_r)} \sum\nolimits_{j' \le j}\sum\nolimits_{i \in [\ell: r)} g(c_{j'}) \cdot (v_i - c_{j'}) {\bar f}_{j,\ell, r, T}(v_i) \cdot w_{j, \ell, r, T} \\ & = \sum\nolimits_{j, \ell, r} \sum\nolimits_{j' \le j}\sum\nolimits_{i \in [\ell: r)} g(c_{j'}) \cdot (v_i - c_{j'}) \sum\nolimits_{{T\subseteq \mathcal{V}\cap [v_\ell, v_r)}} {\bar f}_{j,\ell, r, T}(v_i) \cdot w_{j, \ell, r, T} \\ & = \sum\nolimits_{j, \ell,r} \sum\nolimits_{j' \le j}\sum\nolimits_{i \in [\ell: r)} g(c_{j'}) \cdot (v_i - c_{j'}) \cdot z_{j, \ell, r, i}~. \end{align}\tag{10}\] In the second step, fix an index triple \((j, \ell, r)\), the fragment \({\bar F}_{j, \ell, r, T}\) is defined only for \(T\subseteq \mathcal{V}\cap [v_\ell, v_r)\) by 1. Given a support set \(T\subseteq \mathcal{V}\cap [v_\ell, v_r)\) , when \(i \in [\ell: r)\) but \(v_i \notin T\), the mass at \(v_i\) is zero. Thus, we can expand \(v\in T\) to \(v_i \in \{v_i \in \mathcal{V}: i \in [\ell, r)\}\) without changing the equality in the second step.

Therefore, the maximum social welfare is linear to \(\boldsymbol{z}\). Moreover, the maximum buyer surplus \(\textsf{BS}_{\text{max}}(\boldsymbol{\alpha}) = \textsf{SW}_{\text{max}}(\boldsymbol{\alpha}) - \textsf{SS}(\boldsymbol{\alpha})\) is linear to \((\boldsymbol{x}, \boldsymbol{z})\).

Similarly, the minimum social welfare \(\textsf{SW}_{\text{min}}(\boldsymbol{\alpha})\) is linear to \(\boldsymbol{w}\) in 8 , and specifically \[\label{eq:32minimum32social32welfare32charged32by32z} \begin{align} \textsf{SW}_{\text{min}}(\boldsymbol{\alpha}) & = \sum\nolimits_{j, \ell, r, T} \sum\nolimits_{j' < j}\sum\nolimits_{v\in T} g(c_{j'}) \cdot (v- c_{j'}) \cdot {\bar f}_{j,\ell, r, T}(v) \cdot w_{j, \ell, r, T}\\ & = \sum\nolimits_{j, \ell, r} \sum\nolimits_{T\subseteq \mathcal{V}\cap [v_\ell, v_r)} \sum\nolimits_{j' < j}\sum\nolimits_{i \in [\ell: r)} g(c_{j'}) \cdot (v_i - c_{j'}) {\bar f}_{j,\ell, r, T}(v_i) \cdot w_{j, \ell, r, T} \\ & = \sum\nolimits_{j, \ell, r} \sum\nolimits_{j' < j}\sum\nolimits_{i \in [\ell: r)} g(c_{j'}) \cdot (v_i - c_{j'}) \sum\nolimits_{{T\subseteq \mathcal{V}\cap [v_\ell, v_r)}} {\bar f}_{j,\ell, r, T}(v_i) \cdot w_{j, \ell, r, T} \\ & = \sum\nolimits_{j, \ell, r} \sum\nolimits_{j' < j}\sum\nolimits_{i \in [\ell: r)} g(c_{j'}) \cdot (v_i - c_{j'}) \cdot z_{j, \ell, r,i}~, \end{align}\tag{11}\] which is linear to \(\boldsymbol{z}\). Therefore, the minimum buyer surplus \(\textsf{BS}_{\text{min}}(\boldsymbol{\alpha}) = \textsf{SW}_{\text{min}}(\boldsymbol{\alpha}) - \textsf{SS}(\boldsymbol{\alpha})\) is also linear to \((\boldsymbol{x}, \boldsymbol{z})\). ◻

Proof of 4. Suppose the segmentation \((\alpha, F)\) induces the overall seller surplus \(\textsf{SS}\) and the overall buyer surplus \(\textsf{BS}\). In light of [lem:32full32generality32of32extremal32markets], there exists an extremal market segmentation \((\alpha_{q, S}, F_{q, S})\) such that the overall seller surplus \(\textsf{SS}(\boldsymbol{\alpha}) = \textsf{SS}\), the buyer surplus satisfies \(\textsf{BS}_{\text{min}}(\boldsymbol{\alpha}) \le \textsf{BS}\le \textsf{BS}_{\text{max}}(\boldsymbol{\alpha})\). We can decompose \(\boldsymbol{\alpha}\) into fragments with weight \(\boldsymbol{w}\) (\(\boldsymbol{\alpha}\to \boldsymbol{w}\) as in 3) and further find the reduced fragment decomposition \((\boldsymbol{x}, \boldsymbol{z})\) (\(\boldsymbol{\alpha}\to (\boldsymbol{x}, \boldsymbol{z})\) as in 5) such that the proper domination (12) is satisfied. In 1, we proved the seller surplus and (maximum / minimum) buyer surplus induced by an extremal market decomposition \(\boldsymbol{\alpha}\) are linear in its reduced fragment decomposition \((\boldsymbol{x}, \boldsymbol{z})\). If we charge the seller surplus and the maximum/minimum buyer surplus as 6, then \[\textsf{SS}((\boldsymbol{x}, \boldsymbol{z})) = \textsf{SS}(\alpha) = \textsf{SS}~,\] and \[\textsf{BS}_{\text{min}}((\boldsymbol{x}, \boldsymbol{z})) = \textsf{BS}_{\text{min}}(\alpha) \le \textsf{BS}\le \textsf{BS}_{\text{max}}(\alpha) = \textsf{BS}_{\text{max}}((\boldsymbol{x}, \boldsymbol{z}))~.\] Moreover, 14 proves the existence of \(\boldsymbol{y}\) such that \((\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z})\) satisfies exact composition and flow conservation. Therefore, we can prove if the segmentation exists with seller surplus \(\textsf{SS}\) and buyer surplus \(\textsf{BS}\), then the reduced fragment decomposition \((\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z})\) also exists satisfying \(\textsf{SS}((\boldsymbol{x}, \boldsymbol{z})) = \textsf{SS}\) and \(\textsf{BS}_{\text{min}}((\boldsymbol{x}, \boldsymbol{z})) \le \textsf{BS}\le \textsf{BS}_{\text{max}}((\boldsymbol{x}, \boldsymbol{z}))\).

Suppose there exists \((\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z})\) satisfying constraints with induced seller surplus \(\textsf{SS}((\boldsymbol{x}, \boldsymbol{z}))\) and maximum/minimum buyer surplus \(\textsf{BS}_{\text{max}}((\boldsymbol{x}, \boldsymbol{z}))\) or \(\textsf{BS}_{\text{min}}((\boldsymbol{x}, \boldsymbol{z}))\) defined in 6. 16 shows that there exists a way to segment the aggregate market \(F^*\) which induces the same seller surplus and maximum/minimum buyer surplus as \((\boldsymbol{x}, \boldsymbol{z})\). Then this proves the existence of segmentation with the overall seller surplus \(\textsf{SS}\) such that \(\textsf{SS}= \textsf{SS}((\boldsymbol{x}, \boldsymbol{z}))\) and the overall buyer surplus \(\textsf{BS}\) such that \(\textsf{BS}_{\text{min}}((\boldsymbol{x}, \boldsymbol{z})) \le \textsf{BS}\le \textsf{BS}_{\text{max}}((\boldsymbol{x}, \boldsymbol{z}))\). We complete the proof. ◻

Proof of 13. According to 3, \(w_{j, \ell, k, T_j} = F_{q, S}(v_\ell)\) and \(w_{j + 1, \ell, k, T_{j+1}} = F_{q, S}(v_k)\). Since both \(v_\ell\) and \(v_k\) are optimal prices for \(c_j\) in the extremal market \(F_{q, S}\), \((v_\ell - c_j) \cdot F_{q, S}(v_\ell) = (v_k - c_j) \cdot F_{q, S}(v_k)\). Then \[\frac{w_{j + 1, k, r, T_{j+1}}^{q, S}}{w_{j, \ell, k, T_{j}}^{q, S}} = \frac{F_{q, S}(v_k)}{F_{q, S}(v_\ell)} = \frac{v_\ell - c_j}{v_k - c_j}~.\] Therefore, \(\frac{w_{j + 1, k, r, T_{j+1}}^{q, S}}{w_{j, \ell, k, T_{j}}^{q, S}}\) depends only on \(j\), \(\ell\), and \(k\). ◻

Proof of 14. Since \(F\to (\boldsymbol{x}, \boldsymbol{z})\), there exists \(\boldsymbol{\alpha}= (\alpha_{q, S})\) and \(\boldsymbol{w}= (w_{j, \ell, r, T})\) such that a chain of decompositions by \(F \to \boldsymbol{\alpha}\to \boldsymbol{w}\to (\boldsymbol{x}, \boldsymbol{z})\) exists.

Exact composition. Fix \(j \in [m]\) and \(\ell, r \in [n]\). For each \(i \in [\ell, r)\), \(z_{j, \ell, r, i} = \sum_{T\subseteq \mathcal{V}\cap [v_\ell, v_r)} w_{j, \ell, r, T} \cdot {\bar f}_{j, \ell, r, T}(v_i)\), where \({\bar f}_{j, \ell, r, T}\) is the mass function of the fragment \({\bar F}_{j, \ell, r, T}\) and \(w_{j, \ell, r, T}\) is the corresponding weight in fragment decomposition. By 1, the fragment \({\bar F}_{j, \ell, r, T}\) is defined only for \(T\subseteq \mathcal{V}\cap [v_\ell, v_r)\). Then \[\begin{align} f(v_i) & = \sum\nolimits_{j, \ell, r, T} w_{j, \ell, r, T} \cdot {\bar f}_{j, \ell, r, T}(v_i) = \sum\nolimits_{j, \ell, r} \sum\nolimits_{T\subseteq \mathcal{V}\cap [v_\ell, v_r)} w_{j, \ell, r, T} \cdot {\bar f}_{j, \ell, r, T}(v_i) = \sum\nolimits_{j, \ell, r} z_{j, \ell, r, i}~. \end{align}\] The exact composition is proved.

Outgoing flow conservation. Fix \(j \in [m]\) and \(\ell, r \in [n]\). Recall \(x_{j, \ell, k}\) defined in 5 and \(w_{j, \ell, k, T}\) defined in \(\Cref{def:fragment-decomposition}\), \[\begin{align} x_{j, \ell, k} & = \sum\nolimits_{T_j \subseteq \mathcal{V}\cap [v_\ell, v_k)} w_{j, \ell, k, T_j} \\ & = \sum\nolimits_{T_j \subseteq \mathcal{V}\cap [v_\ell, v_k)} \sum\nolimits_{q, S} \alpha_{q, S} \cdot w_{j, \ell, k, T_j}^{q, S} \\ & = \sum\nolimits_{T_j \subseteq \mathcal{V}\cap [v_\ell, v_k)} \sum\nolimits_{q, S: q_j = v_\ell, q_{j+1} = v_k, S\cap [v_\ell, v_k) = T_j} \alpha_{q, S} \cdot w_{j, \ell, k, T_j}^{q, S} \\ & = \sum\nolimits_{q, S: q_j = v_\ell, q_{j+1} = v_k}\alpha_{q, S} \cdot w_{j, \ell, k, S\cap [v_\ell, v_k)}^{q, S} \\ & = \sum\nolimits_{q, S: q_j = v_\ell, q_{j+1} = v_k} \sum\nolimits_r \sum\nolimits_{q_{j+2} = v_r}\alpha_{q, S} \cdot \frac{w_{j+1, k, r, S\cap [v_k, v_r)}^{q, S}}{d_{j, \ell, k}} \\ & = \sum\nolimits_r \sum\nolimits_{q, S: q_j = v_\ell, q_{j+1} = v_k, q_{j+2} = v_r} \alpha_{q, S} \cdot w_{j, \ell, k,S\cap [v_\ell, v_k)}^{q, S}~, \end{align}\] where \(w_{j, \ell, k, T_j}^{q, S}\) is weight of \({\bar F}_{j, \ell, k, T_j}\) in fragment decomposition of the extremal market \(F_{q, S}\).

Given \(T_j \subseteq \mathcal{V}\cap [v_\ell, v_k)\), \(w_{j, \ell, k, T_{j}}^{q, S} = 0\) when \(q_j \ne v_\ell\) or \(q_{j+1} \ne v_k\) or \(T_j \ne S\cap [v_\ell, v_k)\). Thus, in the third step, for each \(T_j \subseteq \mathcal{V}\cap [v_\ell, v_k)\), we can consider the pair \((q, S)\) in the set \(\{(q, S): q_j = v_\ell, q_{j+1} = v_k, T_{j} = S\cap [v_\ell, v_k)\}\) only. In the forth step, when we sum over all \(T_j \subseteq \mathcal{V}\cap [v_\ell, v_k)\), we can get the set \(\{(q, S): q_j = v_\ell, q_{j+1} = v_k\}\) for the pair \((q, S)\) since \(S\subseteq \mathcal{V}\). In the fifth step, we invoke the discount factor \(d_{j, \ell, k} = w_{j+1, k, r, T_{j+1}}^{q, S}/ w_{j, \ell, k, T_j}^{q, S}\), where \(v_r = q_{j+1}\) and \(T_{j+1} = S\cap [v_k, v_r)\), for each extremal market \((q, S)\) that satisfies \(q_j = v_\ell\), \(q_{j+1} = v_k\). Thus, in the last step we sum over all possible \(r\) and only consider \((q, S)\) that satisfies \(q_j = v_\ell\), \(q_{j+1} = v_k\) and \(q_{j+2} = v_r\).

Incoming flow conservation. Similarly, fix \(j \in [m]\) and \(\ell, r \in [n]\). For \(x_{j+1, k, r}\), \[\begin{align} x_{j+1, k, r} & = \sum\nolimits_{T_{j+1} \subseteq \mathcal{V}\cap [v_k, v_r)} w_{j+1, k, r, T_{j+1}} \\ & = \sum\nolimits_{q, S: q_{j+1} = v_k, q_{j+2} = v_r} \alpha_{q, S} \cdot w_{j+1, k, r, S\cap [v_k, v_r)}^{q, S} \\ & = \sum\nolimits_{q, S: q_{j+1} = v_k, q_{j+2} = v_r} \sum\nolimits_\ell \sum\nolimits_{q_j = v_\ell}\alpha_{q, S}\cdot d_{j, \ell, k} \cdot w_{j, \ell, k,S\cap [v_\ell, v_k)}^{q, S} \\ & = \sum\nolimits_\ell d_{j, \ell, k} \sum\nolimits_{q, S: q_j = v_\ell, q_{j+1} = v_k, q_{j+2} = v_r} \alpha_{q, S} \cdot w_{j, \ell, k, S\cap [v_\ell, v_k)}^{q, S}~. \end{align}\] Therefore, if there exists \(\boldsymbol{\alpha}\) and \(\boldsymbol{w}\) such that we can find a chain of decomposition \(F\to \boldsymbol{\alpha}\to \boldsymbol{w}\to (\boldsymbol{x}, \boldsymbol{z})\) (i.e., \(F\to (\boldsymbol{x}, \boldsymbol{z})\)), and we define \(y_{j, \ell, k, r} = \sum_{q, S: q_j = v_\ell, q_{j+1} = v_k, q_{j+2} = v_r} \alpha_{q, S} \cdot w_{j, \ell, k,S\cap [v_\ell, v_k)}^{q, S}\), then it satisfies the outgoing flow conservation \(x_{j, \ell, k} = \sum_r y_{j, \ell, k, r}\) and the ingoing flow conservation \(x_{j+1, k, r} = \sum_\ell d_{j, \ell, k} \cdot y_{j, \ell, k, r}\). The outgoing flow conservation and ingoing flow conservation are proved. ◻

Proof of 17. For each \(i \in [n]\), \(f_{d}^{(t)}(v_i) = \frac{1}{\alpha^{(t)}}\sum_{j \in [j^{(t)}]} z_{j, i_j^{(t)}, i_{j + 1}^{(t)}, i}^{(t)} \cdot p_j^{(t)} / x_{j, i_j^{(t)}, i_{j + 1}^{(t)}}^{(t)}\), where \(\alpha^{(t)} = p_1^{(t)}\). We observe that \(z_{j, i_j, i_{j + 1}, i} = 0\) if \(i \notin [i_j^{(t)}, i_{j + 1}^{(t)})\). Thus, \[\begin{align} F_{d}^{(t)}(v_{i_j^{(t)}}) & = \sum_{i \ge {i_j^{(t)}}} f_{d}^{(t)}(v_i) \\ & = \sum_{i \ge {i_j^{(t)}}} \frac{1}{\alpha}\sum_{j'\in [j^{(t)}]} \frac{z_{j', i_{j'}, i_{j' + 1}, i}^{(t)} \cdot p_{j'}^{(t)}}{x_{j', i_{j'}, i_{j' + 1}}^{(t)}}\\ & = \frac{1}{\alpha^{(t)}}\sum_{j' \in [j: j^{(t)}]} \frac{p_{j'}^{(t)}}{x_{j', i_{j'}^{(t)}, i_{j' + 1}^{(t)}}^{(t)}}\sum_{i \in [i_{j'}^{(t)}: i_{j'+1}^{(t)})} z_{j', i_{j'}^{(t)}, i_{j' + 1}^{(t)}, i}^{(t)}\\ & = \frac{1}{\alpha^{(t)}}\sum_{j' \in [j: j^{(t)}]} \frac{p_{j'}^{(t)}}{x_{j', i_{j'}^{(t)}, i_{j' + 1}^{(t)}}^{(t)}}\cdot \frac{v_{i_{j'+1}^{(t)}} - v_{i_{j'}^{(t)}}}{v_{i_{j'+1}^{(t)}} - c_{j'}} \cdot {x_{j', i_{j'}^{(t)}, i_{j' + 1}^{(t)}}^{(t)}} \\ & = \frac{1}{\alpha^{(t)}} \sum_{j' \in [j: j^{(t)}]} p_{j'}^{(t)}\cdot \frac{v_{i_{j'+1}^{(t)}} - v_{i_{j'}^{(t)}}}{v_{i_{j'+1}^{(t)}} - c_{j'}}~. \end{align}\] Now we would like to prove \(\sum_{j' \in [j: j^{(t)}]} p_{j'}^{(t)}\cdot (v_{i_{j'+1}^{(t)}} - v_{i_{j'}^{(t)}})/(v_{i_{j'+1}^{(t)}} - c_{j'}) = p_j^{(t)}\). We prove it by deduction.

1. When \(j = j^{(t)}\), since \(v_{i_{j^{(t)}+1}^{(t)}} = \infty\) and \(v_{i_{j^{(t)}}^{(t)}} < \infty\), \[\sum_{j' \in [j: j^{(t)}]} p_{j'}^{(t)}\cdot \frac{v_{i_{j'+1}^{(t)}} - v_{i_{j'}^{(t)}}}{v_{i_{j'+1}^{(t)}} - c_{j'}} = p_{j^{(t)}}^{(t)} \cdot (1- \frac{v_{i_{j^{(t)}}^{(t)}} - c_{j^{(t)}}}{v_{i_{j^{(t)}+1}^{(t)}} - c_{j^{(t)}}} ) = p^{t}_{j^{(t)}} ~;\]

2. assume \(\sum_{j' \in [j+1: j^{(t)}]} p_{j'}^{(t)}\cdot (v_{i_{j'+1}^{(t)}} - v_{i_{j'}^{(t)}}) / (v_{i_{j'+1}^{(t)}} - c_{j'}) = p_{j+1}^{(t)}\). Since \(p_{j+1}^{(t)} / p_j^{(t)} = d_{j, i_j, i_{j+1}} = \frac{v_{i_j} - c_j}{v_{i_{j+1}} - c_j}\), \[\begin{align} \sum_{j' \in [j: j^{(t)}]} p_{j'}^{(t)} \cdot \frac{v_{i_{j'+1}^{(t)}} - v_{i_{j'}^{(t)}}}{v_{i_{j'+1}^{(t)}} - c_{j'}} = p_j^{(t)} \cdot \frac{v_{i_{j+1}^{(t)}} - v_{i_{j}^{(t)}}}{v_{i_{j+1}^{(t)}} - c_{j}} + p_{j+1}^{(t)} = p_j^{(t)}~. \end{align}\]

Therefore, \(F_{d}^{(t)}(v_{i_j^{(t)}}) = \frac{p_j^{(t)}}{p_1^{(t)}}\), \(j \in [j^{(t)}]\).

In 5, there are two places to initiate and update \(p_{j+1}^{(t)}\), we initiate \(p_{j+1}^{(t)} := p_{j}^{(t)} \cdot d_{j, i_j^{(t)}, i_{j+1}^{(t)}}\) in Line [alg-line:32market32segmentation32-32p95j431], and we (might) update \(p_{j+1}^{(t)}\) and \(p_{j}^{(t)}\) with the same coefficient in line [alg-line:32maket32segmentation32-32update32p95j]. Thus, it keeps the relationship \[p_{j+1}^{(t)} = p_{j}^{(t)} \cdot d_{j, i_j^{(t)}, i_{j+1}^{(t)}}~.\] We complete the proof. ◻

Proof of 15. We denote the remaining fragment decomposition variables at the beginning of iteration \(t\) by \(\boldsymbol{x}^{(t)} = \left(x_{j, \ell, r}^{(t)}\right)\), \(\boldsymbol{y}^{(t)} = \left(y_{j, \ell, k, r}^{(t)}\right)\) and \(\boldsymbol{z}^{(t)} = \left(z_{j, \ell, r, i}^{(t)}\right)\). According to 5, in Line [alg-line:32market32segmentation32-32x], \[x_{j, \ell, r}^{(t+1)} = \begin{cases} x_{j, \ell, r}^{(t)} - p_j^{(t)}, & \quad \ell = i_{j}^{(t)}, r = i_{j+1}^{(t)}~;\\ x_{j, \ell, r}^{(t)}, & \quad \text{otherwise}~, \end{cases}\] in Line [alg-line:32market32segmentation32-32y], \[y_{j, \ell, k, r}^{(t+1)} = \begin{cases} y_{j, \ell, k, r}^{(t)} - p_j^{(t)}, & \quad \ell = i_{j}^{(t)}, k = i_{j+1}^{(t)}, r = i_{j+2}^{(t)}~;\\ y_{j, \ell, k, r}^{(t)}, & \quad \text{otherwise}~, \end{cases}\] and in Line [alg-line:32market32segmentation32-32z], \[z_{j, \ell, r, i}^{(t+1)} = \begin{cases} z_{j, \ell, r, i}^{(t)} - \alpha^{(t)} \cdot f_{d}^{(t)}(v_i), & \quad \ell = i^{(t)}_{j}, r=i^{(t)}_{j+1}~ i \in [i^{(t)}_{j}: i^{(t)}_{j+1})~;\\ z_{j, \ell, r, i}^{(t)}, & \quad \text{otherwise}~, \end{cases}\] where \(i_j^{(t)}\) refers to the value index \(i_j\) for the cost \(j\) in iteration \(t\).

Outgoing flow conservation. Assume that \((\boldsymbol{x}^{(t)}, \boldsymbol{y}^{(t)}, \boldsymbol{z}^{(t)})\) satisfies the outgoing flow conservation. Given the index \(j, \ell, k\), then \(x_{j, \ell, k}^{(t)} = \sum_r y_{j, \ell, k, r}^{(t)}\). We discuss the value of \(x_{j, \ell, k}^{(t+1)}\) in different cases:

• when \(\ell = i_{j}^{(t)}\) and \(k = i_{j+1}^{(t)}\), \[\begin{align} x_{j, \ell, k}^{(t+1)} & = x_{j, \ell, k}^{(t)} - p_j^{(t)} \\ & = \sum_r y_{j, \ell, k, r}^{(t)} - p_j^{(t)} \\ & = \sum_{r \ne i_{j+2}^{(t)}}y_{j, \ell, k, r}^{(t)} + y_{j, \ell, k, i_{j+2}^{(t)}}^{(t)} - p_j^{(t)} \\ & = \sum_{r \ne i_{j+2}^{(t)}}y_{j, \ell, k, r}^{(t+1)} + y_{j, \ell, k, i_{j+2}^{(t)}}^{(t+1)} \\ & = \sum_{r}y_{j, \ell, k, r}^{(t+1)} ~; \end{align}\]

• when \(\ell \ne i_{j}^{(t)}\) or \(k \ne i_{j+1}^{(t)}\), for all \(r \in [n]\), it satisfies \(y_{j, \ell, k, r}^{(t+1)} = y_{j, \ell, k, r}^{(t)}\). Thus, \[x_{j, \ell, k}^{(t+1)} = x_{j, \ell, k}^{(t)} = \sum_{r}y_{j, \ell, k, r}^{(t)} = \sum_{r}y_{j, \ell, k, r}^{(t+1)}~.\]

Therefore, \((\boldsymbol{x}^{(t+1)}, \boldsymbol{y}^{(t+1)}, \boldsymbol{z}^{(t+1)})\) satisfies the outgoing flow conservation if \((\boldsymbol{x}^{(t)}, \boldsymbol{y}^{(t)}, \boldsymbol{z}^{(t)})\) satisfies it.

Incoming flow conservation. Similarly, assume that \((\boldsymbol{x}^{(t)}, \boldsymbol{y}^{(t)}, \boldsymbol{z}^{(t)})\) satisfies the incoming flow conservation. Given the index \(j, k , r\), then \(x_{j+1, k, r}^{(t)} = \sum_\ell y_{j, \ell, k, r}^{(t)} \cdot d_{j, \ell, k}\). We consider \(x_{j+1, k, r}^{(t+1)}\) in different cases:

• when \(k = i_{j+1}^{(t)}\) and \(r = i_{j+2}^{(t)}\), \[\begin{align} x_{j+1, k, r}^{(t+1)} & = x_{j+1, \ell, k}^{(t)} - p_{j+1}^{(t)} \\ & = \sum_\ell y_{j, \ell, k, r}^{(t)} \cdot d_{j, \ell, k} - p_j^{(t)} \cdot d_{j, i_j^{(t)}, i_{j+1}^{(t)}} \\ & = \sum_{\ell \ne i_{j}^{(t)}}y_{j, \ell, k, r}^{(t)} \cdot d_{j, \ell, k} + y_{j, i_{j}^{(t)}, k, r}^{(t)} \cdot d_{j, i_j^{(t)}, k} - p_j^{(t)} \cdot d_{j, i_j^{(t)}, k}\\ & = \sum_{\ell \ne i_{j}^{(t)}}y_{j, \ell, k, r}^{(t+1)} \cdot d_{j, \ell, k} + y_{j, i_{j}^{(t)}, k, r}^{(t+1)} \cdot d_{j, i_j^{(t)}, k} \\ & = \sum_{r}y_{j, \ell, k, r}^{(t+1)} \cdot d_{j, \ell, k}~; \end{align}\]

• when \(k \ne i_{j+1}^{(t)}\) or \(r \ne i_{j+2}^{(t)}\), for all \(\ell \in [n]\), it satisfies \(y_{j, \ell, k, r}^{(t+1)} = y_{j, \ell, k, r}^{(t)}\). Thus, \[x_{j+1, k, r}^{(t+1)} = x_{j+1, k, r}^{(t)} = \sum_{\ell}y_{j, \ell, k, r}^{(t)} \cdot d_{j, \ell, k} = \sum_{\ell}y_{j, \ell, k, r}^{(t+1)} \cdot d_{j, \ell, k}~.\]

Therefore, \((\boldsymbol{x}^{(t+1)}, \boldsymbol{y}^{(t+1)}, \boldsymbol{z}^{(t+1)})\) satisfies the incoming flow conservation if \((\boldsymbol{x}^{(t)}, \boldsymbol{y}^{(t)}, \boldsymbol{z}^{(t)})\) satisfies it.

Proper domination. Assume for \(t\), it has \(\sum_{i\in [n]} z_{j, \ell, r, i}^{(t)} = (v_r - v_\ell)/(v_r - c_j) \cdot x_{j, \ell, r}^{(t)}\). Given \(j \in [j^{(t)}]\),

• when \(\ell \ne i^{(t)}_{j}\) or \(r \ne i^{(t)}_{j+1}\), both \(z_{j, \ell, r, i}^{(t+1)} = z_{j, \ell, r, i}^{(t)}\) and \(x_{j, \ell, r}^{(t+1)} = x_{j, \ell, r}^{(t)}\), thus \(\sum_{i\in [n]} z_{j, \ell, r, i}^{(t+1)} = (v_r - v_\ell)/(v_r - c_j) \cdot x_{j, \ell, r}^{(t+1)}\);

• when \(\ell = i^{(t)}_{j}\) and \(r = i^{(t)}_{j+1}\), \[\begin{align} \sum_{i\in [n]} z_{j, \ell, r, i}^{(t+1)} & = \sum_{i\in [\ell, r)} z_{j, \ell, r, i}^{(t+1)} \\ & = \sum_{i\in [\ell, r)} \left(z_{j, \ell, r, i}^{(t)} - \alpha^{(t)} \cdot f_{d}^{(t)}(v_i)\right)\\ & = \sum_{i\in [\ell, r)} z_{j, \ell, r, i}^{(t)} - \alpha^{(t)} \sum_{i\in [\ell, r)}f_{d}^{(t)}(v_i)~. \end{align}\] In 17, it is proved that \(F_{d}^{(t)}(v_{\ell}) = F_{d}^{(t)} \bigl(v_{i_j^{(t)}}\bigr)=p_j^{(t)} / p_1^{(t)}\) and \(p_{j+1}^{(t)}=p_{j}^{(t)}\cdot d_{j, \ell, r}\). Thus, the sum of probability mass \(\sum_{i\in [\ell, r)}f_{d}^{(t)}(v_i) = (p_j^{(t)} - p_{j+1}^{(t)})/p_1^{(t)} = p_j^{(t)} \cdot ( 1 - d_{j, \ell, r}) / p_1^{(t)}\). Since \(1-d_{j, \ell, r} = (v_r - v_\ell)/(v_r - c_j)\), then \[\begin{align} \sum_{i\in [n]} z_{j, \ell, r, i}^{(t+1)} & = \sum_{i\in [\ell, r)} z_{j, \ell, r, i}^{(t)} - p_j^{(t)} \cdot \frac{v_r - v_\ell}{v_r - c_j}\\ & =\frac{v_r - v_\ell}{v_r - c_j} \cdot ( x_{j, \ell, r}^{(t)} - p_j^{(t)}) \\ & =\frac{v_r - v_\ell}{v_r - c_j} \cdot x_{j, \ell, r}^{(t+1)}~. \end{align}\]

Therefore, when it holds for \(t\), it also holds for \(t+1\).

Assume that given \(t\), for any \(i \in [n]\), \(z^{(t)}_{j, \ell, r, i} \le {\bar F}_{j, \ell, r}(v_i) \cdot x^{(t)}_{j, \ell, r}\). For \(t+1\), given \(j \in [j^{(t)}]\),

• when \(\ell \ne i^{(t)}_{j}\) or \(r \ne i^{(t)}_{j+1}\), both \(z_{j, \ell, r, i}^{(t+1)} = z_{j, \ell, r, i}^{(t)}\) and \(x_{j, \ell, r}^{(t+1)} = x_{j, \ell, r}^{(t)}\), thus \(z_{j, \ell, r, i}^{(t+1)} \le {\bar F}_{j, \ell, r}(v_i) \cdot x_{j, \ell, r}^{(t+1)}\);

• when \(\ell = i^{(t)}_{j}\) and \(r = i^{(t)}_{j+1}\), according to Line [alg-line:32f40v95i41] and Line [alg-line:32alpha94t32and32market32segment32F], \(f_{d}^{(t)}(v_i) = \frac{1}{p_1^{(t)}} \sum_{j \in [j^{(t)}]} z_{j, i_{j}^{(t)}, i_{j + 1}^{(t)}, i}^{(t)} \cdot p_{j}^{(t)} / x_{j, i_{j}^{(t)}, i_{j + 1}^{(t)}}^{(t)}\). When \(i \notin [i_{j}^{(t)}, i_{j + 1}^{(t)})\), \[z_{j, i_{j}^{(t)}, i_{j + 1}^{(t)}, i}^{(t+1)} = z_{j, i_{j}^{(t)}, i_{j + 1}^{(t)}, i}^{(t)}= 0 \le {\bar F}_{j, \ell, r}(v_i) \cdot x_{j, \ell, r}^{(t+1)}~.\] When \(i \in [i_{j}^{(t)}, i_{j + 1}^{(t)})\), \[f_{d}^{(t)}(v_i) = \frac{z_{j, \ell, r, i}^{(t)} \cdot p_{j}^{(t)}}{p_1^{(t)} \cdot x_{j, \ell, r}^{(t)}}~.\] Thus, \(z_{j, \ell, r, i}^{(t+1)} = z_{j, \ell, r, i}^{(t)} - z_{j, \ell, r, i}^{(t)} \cdot p_{j}^{(t)}/ x_{j, \ell, r}^{(t)} = (1 - p_{j}^{(t)}/ x_{j, \ell, r}^{(t)}) \cdot z_{j, \ell, r, i}^{(t)}\) and \(x_{j, \ell, r}^{(t+1)} = x_{j, \ell, r}^{(t)} - p_j^{(t)} = (1 - \frac{p_{j}^{(t)}}{ x_{j, \ell, r}^{(t)}}) \cdot x_{j, \ell, r}^{(t)}\). Both are scaled by the same coefficient. Then \[z^{(t+1)}_{j, \ell, r, i} = \left(1 - \frac{p_{j}^{(t)}}{x_{j, \ell, r}^{(t)}}\right) \cdot z_{j, \ell, r, i}^{(t)} \le \left(1 - \frac{p_{j}^{(t)}}{x_{j, \ell, r}^{(t)}}\right) \cdot {\bar F}_{j, \ell, r}(v_i) \cdot x^{(t)}_{j, \ell, r} = {\bar F}_{j, \ell, r}(v_i) \cdot x^{(t+1)}_{j, \ell, r}~.\] Thus, when the domination relationship holds for \(t\), it also holds for \(t+1\).

Therefore, if \(\left(\boldsymbol{x}^{(t)}, \boldsymbol{y}^{(t)}, \boldsymbol{z}^{(t)}\right)\) satisfies the constraints: outgoing/incoming flow conservation, fragment composition, and proper domination, \(\left(\boldsymbol{x}^{(t+1)}, \boldsymbol{y}^{(t+1)}, \boldsymbol{z}^{(t+1)}\right)\) also satisfies all. ◻

Proof of 3. It is clear that when \(\boldsymbol{x}= \boldsymbol{0}\), 5 stops. What we need to prove is when 5 stops, \(\boldsymbol{x}= \boldsymbol{0}\).

We prove it by contradiction, which means we stop the procedure either we can not find \(x_{1, i_1, i_2} >0\) but for some \(j>1\), it has \(x_{j, i_{j}, i_{j+1}} >0\); or we can not find \(y_{j, i_j, i_{j+1}, i_{j+2}} > 0\) for a specific \(j\) when \(\boldsymbol{x}\ne 0\). However, we proved that the incoming and outgoing flow conservation are always satisfied in each iteration in 15, which indicates that if \(x_{1, \ell, r} >0\), we can always find outgoing flow and also the corresponding \(y_{j, i_j, i_{j+1}, i_{j+2}} > 0\) for all \(j\); if \(y_{j, i_j, i_{j+1}, i_{j+2}} > 0\), we can always find its incoming flow and also has \(y_{j', i_j', i_{j'+1}, i_{j'+2}} > 0\) for all \(j' \in [j]\), thus \(x_{1, i_1, i_2} >0\). These contradicts our assumption. Therefore, when 5 stops, \(\boldsymbol{x}= \boldsymbol{0}\). ◻

Proof of 16. We denote the remaining fragment decomposition variables at the beginning of iteration \(t\) by \(\boldsymbol{x}^{(t)} = (x_{j, \ell, r}^{(t)})\) and \(\boldsymbol{z}^{(t)} = (z_{j, \ell, r, i}^{(t)})\). According to Line [alg-line:32market32segmentation32-32x] of 5, \[x_{j, \ell, k}^{(t+1)} = \begin{cases} x_{j, \ell, k}^{(t)} - p_j^{(t)}, & \ell = i_{j}^{(t)}, k = i_{j+1}^{(t)}~;\\ x_{j, \ell, k}^{(t)}, & \text{otherwise}~, \end{cases}\] where \(i_{j}^{(t)}\) refers to the corresponding or \(i_{j}\) calculated in iteration \(t\) of 5. According to Line [alg-line:32market32segmentation32-32z] of 5, \[z_{j, \ell, k, i}^{(t+1)} = \begin{cases} z_{j, \ell, k, i}^{(t)} - \alpha^{(t)} \cdot f_{d}^{(t)}(v_i), & \ell = i_{j}^{(t)}, k = i_{j+1}^{(t)}~;\\ z_{j, i_j, i_{j + 1}, i}^{(t)}, & \text{otherwise}~. \end{cases}\] We first prove in each iteration \(t\), the seller surplus (\(\textsf{SS}(F_{d}^{(t)})\)) and maximum/minimum buyer surplus (\(\textsf{BS}_{\text{max}}(F_{d}^{(t)})\) / \(\textsf{BS}_{\text{min}}(F_{d}^{(t)})\)) of \(F_{d}^{(t)}\) weighted by \(\alpha^{(t)}\) is equivalent to the change in seller surplus and maximum / minimum buyer surplus induced by \((\boldsymbol{x}, \boldsymbol{z})\).

The change in seller surplus and maximum / minimum buyer surplus induced by \((\boldsymbol{x}, \boldsymbol{z})\). The seller surplus induced by \((\boldsymbol{x}^{(t)}, \boldsymbol{z}^{(t)})\) is \(\textsf{SS}\left((\boldsymbol{x}^{(t)}, \boldsymbol{z}^{(t)})\right) = \sum_{j, \ell, r} g(c_j) \cdot (v_\ell - c_j) \cdot x_{j, \ell, r}^{(t)}\) according to 6. Therefore, the change in seller surplus of iteration \(t\) equals to \[\begin{align} \textsf{SS}\left((\boldsymbol{x}, \boldsymbol{z})^{(t)}\right) - \textsf{SS}\left((\boldsymbol{x}, \boldsymbol{z})^{(t+1)}\right) & = \sum_{j, \ell, r} g(c_j) \cdot (v_\ell - c_j) \cdot x_{j, \ell, r}^{(t)} - \sum_{j, \ell, r} g(c_j) \cdot (v_\ell - c_j) \cdot x_{j, \ell, r}^{(t+1)} \\ & = \sum_{j \in [j^{(t)}]} g(c_j) \cdot (v_{i_j^{(t)}} - c_j) \cdot p_j^{(t)}~, \end{align}\] where \(j^{(t)}\) refers to the corresponding \(j\) when the while loop (Line [alg-line:32market32segmentation32-32iteration32t32while32starts] to Line [alg-line:32market32segmentation32-32iteration32t32while32ends]) ends in iteration \(t\).

The maximum social welfare charged by \((\boldsymbol{x}^{(t)}, \boldsymbol{z}^{(t)})\) is \(\textsf{SW}_{\text{max}}\left((\boldsymbol{x}^{(t)}, \boldsymbol{z}^{(t)})\right) = \sum_{j, \ell,r} \sum_{j' \in [j]}\sum_{i \in [\ell: r)} (v_i - c_{j'}) \cdot z_{j, \ell, r, i}^{(t)}\) according to 10 . Therefore, the change of maximum social welfare of iteration \(t\) equals to \[\begin{align} &\quad \textsf{SW}_{\text{max}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t)}\right) - \textsf{SW}_{\text{max}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t+1)}\right) \\ = &\quad \sum_{j, \ell,r} \sum_{j' \in [j]}\sum_{i \in [\ell: r)} g(c_{j'}) \cdot (v_i - c_{j'}) \cdot z_{j, \ell, r, i}^{(t)} - \sum_{j, \ell,r} \sum_{j' \in [j]}\sum_{i \in [\ell: r)} g(c_{j'}) \cdot (v_i - c_{j'}) \cdot z_{j, \ell, r, i}^{(t+1)} \\ = &\quad \sum_{j \in [j^{(t)}]} \sum_{j' \in [j]} \sum_{i \in [i_j^{(t)}: i_{j+1}^{(t)})} g(c_{j'}) \cdot (v_{i} - c_{j'}) \cdot \alpha^{(t)} \cdot f_{d}^{(t)}(v_i)~, \end{align}\] When we consider the social welfare for the cost \(c_j'\), for all \(j \in [j', j^{(t)}]\) and \(i \in [i_j^{(t)}: i_{j+1}^{(t)})\) it has the corresponding social welfare \(g(c_{j'}) \cdot (v_{i} - c_{j'}) \cdot \alpha^{(t)} \cdot f_{d}^{(t)}(v_i)\) contributed. Therefore, \[\begin{align} \textsf{SW}_{\text{max}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t)}\right) - \textsf{SW}_{\text{max}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t+1)}\right) = \alpha^{(t)}\sum_{j' \in [j^{(t)}]} g(c_{j'}) \sum_{i \ge i_{j'}^{(t)}} (v_{i} - c_{j'}) \cdot f_{d}^{(t)}(v_i)~. \end{align}\] Similarly, the minimum social welfare charged by \((\boldsymbol{x}^{(t)}, \boldsymbol{z}^{(t)})\) is \(\textsf{SW}_{\text{min}}\left((\boldsymbol{x}^{(t)}, \boldsymbol{z}^{(t)})\right) = \sum_{j, \ell,r} \sum_{j' \in [j-1]}\sum_{i \in [\ell: r)} (v_i - c_{j'}) \cdot z_{j, \ell, r, i}^{(t)}\) according to 11 . Therefore, the change in minimum social welfare of iteration \(t\) equals to \[\begin{align} &\quad \textsf{SW}_{\text{min}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t)}\right) - \textsf{SW}_{\text{min}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t+1)}\right) \\ = &\quad \sum_{j, \ell,r} \sum_{j' \in [j-1]}\sum_{i \in [\ell: r)} g(c_{j'}) \cdot (v_i - c_{j'}) \cdot z_{j, \ell, r, i}^{(t)} - \sum_{j, \ell,r} \sum_{j' \in [j-1]}\sum_{i \in [\ell: r)} g(c_{j'}) \cdot (v_i - c_{j'}) \cdot z_{j, \ell, r, i}^{(t+1)} \\ = &\quad \sum_{j \in [j^{(t)}]} \sum_{j' \in [j-1]} \sum_{i \in [i_j^{(t)}: i_{j+1}^{(t)})} g(c_{j'}) \cdot (v_{i} - c_{j'}) \cdot \alpha^{(t)} \cdot f_{d}^{(t)}(v_i)~, \end{align}\] When we consider the social welfare for the cost \(c_j'\), for all \(j \in [j'+1, j^{(t)}]\) and \(i \in [i_j^{(t)}: i_{j+1}^{(t)})\) it has the corresponding social welfare \(g(c_{j'}) \cdot (v_{i} - c_{j'}) \cdot \alpha^{(t)} \cdot f_{d}^{(t)}(v_i)\) contributed. Therefore, \[\begin{align} \textsf{SW}_{\text{min}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t)}\right) - \textsf{SW}_{\text{min}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t+1)}\right) = \alpha^{(t)}\sum_{j' \in [j^{(t)}]} g(c_{j'}) \sum_{i \ge i_{j'+1}^{(t)}} (v_{i} - c_{j'}) \cdot f_{d}^{(t)}(v_i)~. \end{align}\] Seller surplus and maximum/minimum buyer surplus of each constructed market \(F_{d}^{(t)}\). Since we have already proved \(F_{d}^{(t)} \bigl(v_{i_j^{(t)}}\bigr)=p_j^{(t)}/p_1^{(t)}\), we discuss the CDF of \(v_i\) for \(i \in [i_j^{(t)}: i_{j+1}^{(t)})\), \[\begin{align} F_{d}^{(t)}(v_{i}) &= \frac{p_{j+1}^{(t)}}{p_1^{(t)}} + \sum_{i' \in [i, i_{j+1}^{(t)})} f_{d}^{(t)}(v_{i'})\\ &= \frac{p_{j+1}^{(t)}}{p_1^{(t)}} + \sum_{i' \in [i, i_{j+1}^{(t)})} \frac{1}{p_1^{(t)}}\sum_{j'\in [j^{(t)}]} \frac{z_{j', i_{j'}^{(t)}, i_{j' + 1}^{(t)}, i'} \cdot p_{j'}^{(t)}}{x_{j', i_{j'}^{(t)}, i_{j' + 1}^{(t)}}}\\ &= \frac{p_{j+1}^{(t)}}{p_1^{(t)}} + \sum_{i' \in [i, i_{j+1}^{(t)})} \frac{1}{p_1^{(t)}}\frac{z_{j, i_{j}^{(t)}, i_{j + 1}^{(t)}, i'} \cdot p_{j}^{(t)}}{x_{j, i_{j}^{(t)}, i_{j + 1}^{(t)}}} \\ &= \frac{p_{j}^{(t)}}{p_1^{(t)}} \cdot \left( \frac{v_{i_j^{(t)}} - c_j}{v_{i_{j+1}^{(t)}} - c_j} + \frac{1}{x^{(t)}_{j, i_{j}^{(t)}, i_{j + 1}^{(t)}}} \sum_{i' \in [i: i_{j+1}^{(t)})} z^{(t)}_{j, i_{j}^{(t)}, i_{j + 1}^{(t)}, i'} \right)~. \end{align}\] In 15, we have proved that the fragment domination preserves, then \(\sum_{i' \in [i: i_{j+1}^{(t)})} z^{(t)}_{j, i_{j}^{(t)}, i_{j + 1}^{(t)}, i'} \le {\bar F}_{j, i_{j}^{(t)}, i_{j + 1}^{(t)}}(v_i) \cdot x^{(t)}_{j, i_{j}^{(t)}, i_{j + 1}^{(t)}}\) for all \(i \in [i_j^{(t)}: i_{j+1}^{(t)})\). Moreover, combining 8 and the definition of undominated fragment \({\bar F}_{j, i_{j}^{(t)}, i_{j + 1}^{(t)}}\), we have \[{\bar F}_{j, \ell, r}(v_i) = \frac{v_{i_{j}^{(t)}} - c_j}{v_i - c_j} - \frac{v_{i_{j}^{(t)}} - c_j}{v_{i_{j+1}^{(t)}} - c_j},~\quad i \in [i_{j}^{(t)}, i_{j+1}^{(t)})~.\] Then \[\begin{align} F_{d}^{(t)}(v_{i}) &\le \frac{p_{j}^{(t)}}{p_1^{(t)}} \cdot \left( \frac{v_{i_j^{(t)}} - c_j}{v_{i} - c_j} \right),~\quad i \in [i_{j}^{(t)}, i_{j+1}^{(t)})~. \end{align}\] Since \(F_{d}^{(t)}(v_{i_j^{(t)}}) = \frac{p_{j}^{(t)}}{p_1^{(t)}}\), and \(F_{d}^{(t)}(v_{i_{j+1}^{(t)}}) = \frac{p_{j+1}^{(t)}}{p_1^{(t)}} = \frac{p_{j}^{(t)}}{p_1^{(t)}} \cdot \frac{v_{i_j^{(t)}} - c_j}{v_{i_{j+1}^{(t)}} - c_j}\), for all \(j \in [j^{(t)}]\), \[F_{d}^{(t)}(v_{i}) \cdot (v_{i} - c_j) \le F_{d}^{(t)}(v_{i_j^{(t)}}) \cdot ( v_{i_j^{(t)}} - c_j),~\quad i \in [i_{j}^{(t)}, i_{j+1}^{(t)}]~,\] and the equality holds when \(i = i_{j}^{(t)}\) or \(i = i_{j+1}^{(t)}\). Thus, \(F_{d}^{(t)}\) is (weakly) dominated by \(F_{q, S}\), where \(q= (v_{i_j^{(t)}})_{j\in [j^{(t)}]}\) and \(S= (v_i)_{i \in [n]}\). Indicates that \(\{v_{i_j^{(t)}}, v_{i_{j+1}^{(t)}}\} \subseteq Q_j(F_{d}^{(t)})\). When we use \(v_{i_j^{(t)}}\) as the price for cost \(c_j\), the seller surplus of the constructed \(F_{d}\) equals \[\begin{align} \textsf{SS}(F_{d}^{(t)}) & = \sum_jg(c_j) \cdot (v_{i_j^{(t)}} - c_j) \cdot F_{d}^{(t)}(v_{i_j^{(t)}}) = \sum_jg(c_j) \cdot (v_{i_j^{(t)}} - c_j) \cdot \frac{p_j^{(t)}}{p_1^{(t)}}~. \end{align}\] Therefore, the weighted seller surplus \(\alpha^{(t)} \cdot \textsf{SS}(F_{d}^{(t)}) = \sum_jg(c_j) \cdot (v_{i_j^{(t)}} - c_j) \cdot p_j^{(t)}\) equals the change of the seller surplus \(\textsf{SS}\left((\boldsymbol{x}, \boldsymbol{z})^{(t)}\right) - \textsf{SS}\left((\boldsymbol{x}, \boldsymbol{z})^{(t+1)}\right)\) induced by \((\boldsymbol{x}, \boldsymbol{z})\).

Due to the monotonicity of the optimal price set \(Q_j(F_{d}^{(t)})\) (3), we infer that \(v_{i_j^{(t)}}\) is the minimum optimal price and \(v_{i_{j+1}^{(t)}}\) is the maximum optimal price for cost \(c_j\) in the constructed market \(F_{d}^{(t)}\). Thus, the maximum(or minimum) social welfare is attained when we apply \(v_{i_{j}^{(t)}}\) (or \(v_{i_{j+1}^{(t)}}\)) as the price for cost \(c_j\), \[\begin{align} \textsf{SW}_{\text{max}}(F_{d}^{(t)}) & = \sum_{j\in j^{(t)}}g(c_j) \sum_{i \ge i_{j}^{(t)}} (v_{i} - c_j) \cdot f_{d}^{(t)}(v_{i}) ~; \\ \textsf{SW}_{\text{min}}(F_{d}^{(t)}) & = \sum_{j\in j^{(t)}}g(c_j) \sum_{i \ge i_{j+1}^{(t)}} (v_{i} - c_j) \cdot f_{d}^{(t)}(v_{i})~. \end{align}\] Therefore, the weighted maximum social welfare \(\alpha^{(t)} \cdot \textsf{SW}_{\text{max}}(F_{d}^{(t)})\) equals the change of maximum social welfare \(\textsf{SW}_{\text{max}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t)}\right) - \textsf{SW}_{\text{max}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t+1)}\right)\) induced by \((\boldsymbol{x}, \boldsymbol{z})\), and the weighted minimum social welfare \(\alpha^{(t)} \cdot \textsf{SW}_{\text{min}}(F_{d}^{(t)})\) equals the change of the minimum social welfare \(\textsf{SW}_{\text{min}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t)}\right) - \textsf{SW}_{\text{min}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t+1)}\right)\) induced by \((\boldsymbol{x}, \boldsymbol{z})\). Then, the weighted maximum buyer surplus \(\alpha^{(t)} \cdot \textsf{BS}_{\text{max}}(F_{d}^{(t)}) = \alpha^{(t)} \cdot (\textsf{SW}_{\text{max}}(F_{d}^{(t)}) - \textsf{SS}(F_{d}^{(t)}))\) equals the change of the maximum buyer surplus \(\textsf{BS}_{\text{max}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t)}\right) - \textsf{BS}_{\text{max}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t+1)}\right)\) induced by \((\boldsymbol{x}, \boldsymbol{z})\), and the weighted minimum buyer surplus \(\alpha^{(t)} \cdot \textsf{BS}_{\text{min}}(F_{d}^{(t)}) =\alpha^{(t)} \cdot (\textsf{SW}_{\text{min}}(F_{d}^{(t)}) - \textsf{SS}(F_{d}^{(t)}))\) equals the change of the minimum buyer surplus \(\textsf{BS}_{\text{min}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t)}\right) - \textsf{BS}_{\text{min}}\left((\boldsymbol{x}, \boldsymbol{z})^{(t+1)}\right)\) induced by \((\boldsymbol{x}, \boldsymbol{z})\).

Since 5 stops iff \(\boldsymbol{x}=0\) (as in 3), we can finally conclude that if we segment the aggregate market \(F^*\) with 5, the seller surplus and The maximum / minimum buyer surplus of the segmentation (\(\alpha^{(t)}, F_{d}^{(t)})\) are equivalent to the seller surplus and maximum / minimum buyer surplus induced by \((\boldsymbol{x}, \boldsymbol{z})\). ◻