\section{Introduction}

In general, the electricity market is organized by a sequence of processes: unit commitment, day-ahead market, real time market, balancing market, \emph{etc}. Since the focuses of different processes are diverse, the incentives they provide do not necessarily align with each other. To relieve the tension between these processes, convex hull pricing (CHP) is one promising solution: it provides the minimal uplift payment to the generators for incentive alignment \cite{o2005efficient,hogan2003minimum,Schiro}.

However, although remarkable in improving the system efficiency by reallocating the market surplus between supply and demand \cite{Thompson}, we find that the incentive issues in the CHP scheme have not been fully solved due to the non-convex cost structures. To the best of our knowledge, we are the first to identify market power in the CHP schemes.

In this letter, we first revisit the CHP scheme in Section \ref{sec:2}. And then we seek to understand each individual firm's possible strategic behaviors in Section \ref{sec:3}. Based on the identified behaviors, we propose the market power index and highlight the existence of market power via numerical studies in Section \ref{sec:4}. Finally, concluding remarks are given in Section \ref{sec:5}. We provide all the necessary proofs in the Appendix.


\section{Convex Hull Pricing: A Brief Revisit}
\label{sec:2}
We consider the CHP scheme in the electricity pool model with $n$ generators in the system. To highlight the existence of strategic behaviors, we assume all the generators have the same capacity $G$. In such a model, the system operator seeks to minimize the total generation costs at each time slot:
\begin{equation}
    \begin{aligned}
    c(y)\coloneqq \min_\textbf{g} &\sum\nolimits_{i=1}^n f_i(g_i)\\
    s.t. & \sum\nolimits_{i=1}^n g_i=y,\\
    &0\le g_i\le G,
\end{aligned}
\end{equation}
where $g_i$ denotes the output of generator $i$, $f_i(g_i)$ denotes the generation cost for generator $i$, vector $\textbf{g}$ is $[g_1,...,g_n]$, and $y$ is the total load in the system. The optimal solution $\textbf{g}^*(y)$ and the optimal objective value $c(y)$ are both functions of $y$.

If $f_i(g_i)$ is linear, then the operator could conduct the economic dispatch according to the merit order of marginal generation cost and set the price as the marginal cost.

However, in practice, there are start up costs associated with generation. Hence, for generator $i$, $f_i(g_i)$ is often of the following form:
\begin{equation}
    f_i(g_i)=s_i\cdot I(g_i>0)+v_i\cdot g_i,
    \label{eq:cost structure}
\end{equation}
where $s_i$ is the sum of fixed cost and start up cost, and $v_i$ is the variable cost. To highlight the non-convexity in $f_i(g_i)$, we employ the indicator function $I(\cdot)$. Such a cost structure challenges the conventional scheme in terms of dispatch profile, price design, and incentive analysis.

The solution proposed by CHP is to use the uplift payment to incentivize the generators to follow the system operator's dispatch profile.

For each generator $i$, given price $p$, its desired generation level $g_i^d(p)$ is associated with its maximal profits, and can be different from the dispatch profile $g_i^*$:
\begin{equation}
    g_i^d(p)=\sup \left\{\arg \max_{z\in [0,G]}\{p\cdot z-f_i(z)\}\right\}.
\end{equation}
And this generation level leads to the maximal profits given $p$, denoted by $\pi_i^*(p)$, i.e.,
 \begin{equation}
     \pi_i^*(p)=p\cdot g_i^d(p)-f_i(g_i^d(p)).
 \end{equation}
 The difference in the profits between generating $g_i^d(p)$ and $g_i^*$ needs to be compensated by uplift payment:
\begin{equation}
    \text{Uplift}_i(p,y)=\pi_i^*(p)-[p\cdot g_i^*-f_i(g_i^*)].
    \label{def:uplift}
\end{equation}
And the CHP scheme is proved to guarantee that it leads to the optimal price $p^*$ in terms of minimizing the total uplift payment \cite{Gribik}. In this letter, we adopt an equivalent form to characterize $p^*$:

\vspace{0.1cm}
\noindent \textbf{Lemma 1}: The optimal price $p^*$ in CHP can be expressed as follows:
\begin{equation}
    p^*=\inf\left\{p\big |\sum\nolimits_{i=1}^n g_i^d(p)\ge y\right\}.
\end{equation}
Given the structure of $f_i(g_i)$, we claim for demand of $y$, there exists an optimal dispatch profile $\textbf{g}^*$, which is composed of the following dispatch profiles:

1) $m-1$ elements are $G$, and $n-m$ elements are 0.

2) one generator is dispatched at $x$ units. 

Here, $m=\lceil \frac{y}{G}\rceil$, and $x=y-(m-1)\cdot G$. This allows the system operator to dispatch the generators roughly in the order of their average generation costs\footnote{This order plays the most important role in the optimal dispatch. There is minor issue in dispatching the generator which is scheduled to generate $x$ units. We omit the detailed discussion due to the page limits.}. In our case, since all the generators share the same capacity, the system operator can directly sort them with respect to $f_i(G)$. For notational simplicity, we assume the subscript $i$ for generator $i$ also denotes its ascending order in the average generation costs. Hence, we can make the following observations.

\vspace{0.1cm}
\noindent \textbf{Fact 1}: We can establish the mapping between generator's order in average generation cost and its dispatch profile.

1) If $i<m$, then $g_i^*\in\{x,G\}$; if $i>m$, then $g_i^*\in\{0,x\}$.

2) If $g_i^*=0$, then $i\ge m$; if $g_i^*=G$, then $i\le m$.
\vspace{0.1cm}

However, the CHP scheme only guarantees the minimal total uplift payment, it does not fully mitigate generators' opportunities in obtaining more profits by strategic bidding.

\section{Strategic Behavior Analysis}
\label{sec:3}
 We seek to understand generator's strategic behavior via analyzing its profits. For each generator, its total profits are gained from the uplift payment as well as selling electricity according to the dispatch profile from the system operator. We want to emphasize that the second component is not necessarily positive, which further implies the importance of uplift payment. 
 
 In practice, the generators are allowed to bid their cost functions as well as their available capacities to the operator. In this letter, we assume the generator is not allowed to withhold its capacity. Hence, it can only strategically bid its cost function. Since the fixed cost and start up cost are rather stable, the only remaining opportunity for manipulation is the variable cost $v_i$, for each generator $i$.
 
 Mathematically, if generator $i$ truthfully bids its $v_i$, given a demand of $y$, we denote its profits $P_i$ as benchmark:
 \begin{equation}
     P_i = \pi_i(p^*(v_i)) = \{f_m(G)-f_i(G)\}^+.
     \label{eq:truthful profit}
 \end{equation}

 Recall $m=\lceil \frac{y}{G}\rceil$, and $f_m(\cdot)$ denotes the cost function for generator $m$, which ranks the $m^{th}$ in terms of the average generation cost. It is crucial in determining the optimal price $p^*$ in CHP. We provide the detailed analysis in the Appendix.
 
 On the other hand, if the generator strategically reports its generation cost as $\Tilde{f}_i(\cdot)$ (more precisely, a different variable cost $\tilde{v}_i$), which may lead to a potentially different $\Tilde{p}^*$ given by CHP, and a potentially different dispatch profile $\Tilde{\textbf{g}}^*$. This strategic bidding will also reshuffle the order of generators in terms of average \emph{bid} generation cost. We denote the reshuffled bid generation cost by $\tilde{f}^{(1)},\cdots,\tilde{f}^{(n)}$. Hence, generator $i$'s total profits $\Tilde{P}_i(\tilde{v}_i)$ via strategic bidding by can be straightforwardly characterized as follows:

\begin{equation}
    \Tilde{P}_i(\tilde{v}_i)=\underbrace{\left\{\tilde{f}^{(m)}(G)-\tilde{f}_i(G)\right\}^+}_{\text{Profits by Strategic Bidding}} +\underbrace{\left(\Tilde{f}_i(\Tilde{g}_i^*)-f_i(\Tilde{g}^*_i)\right)}_{\text{Profits in Generation Cost}}.
    \label{eq:gain decomposition}
\end{equation}

Since for every generator $i$, $\Tilde{g}_i^*\in\{0,x,G\}$, we can define its maximal profits via strategic bidding as follows:
\begin{equation}
    \sup\{\Tilde{P}_i\}=\sup_{u\in\{0,x,G\}}\{\Tilde{P}_i|\Tilde{g}_i^*=u\}.
\end{equation}
This allows us to quantify each generation's maximal \emph{additional} profits through strategic manipulation:
\begin{equation}
    M(i)\coloneqq\ \sup\{\Tilde{P}_i\}-P_i.
    \label{def:market power}
\end{equation}
Surprisingly, $M(i)$ has a uniform and rather neat expression.

\vspace{0.1cm}
\noindent \textbf{Theorem 1}: $M(i)=c^{\{i\}}(y)-c(y)-P_i \ $.
\vspace{0.1cm}

Note that $c^{\{i\}}(y)$ denotes the minimal system cost without generator $i$'s participation. Generally, for each set $A$, we can define $c^A(y)$ as follows:
\begin{equation}
\begin{aligned}
c^{A}(y)&\coloneqq\min_{\textbf{g}} f
_k(g_k)\\
s.t. \quad &\sum\nolimits_{k=1}^n g_k=y, \\
& g_k=0, \ \ k\in A,\\
& 0\le g_k\le G, \ \ k\not\in A. 
\end{aligned}
\end{equation}
This highlights $c^{\{i\}}(y)-c(y)$ in Theorem 1 just seems like the information rent in the VCG mechanism \cite{bushnell1999international}!

\vspace{0.1cm}
\noindent \textbf{Remark:} Throughout the analysis, we assume that only one generator adopts the strategic behavior, and it knows all the information in the system. This is the standard assumption for worst case analysis and it is best suitable to understand the \emph{potential} of strategic behavior. 

\begin{figure}
    \centering
    \includegraphics[scale=0.23]{markedpercentage.pdf}\vspace{-0.2cm}
    \caption{Percentage of coalitions with market power.\vspace{-0.5cm}}
    \label{fig:percentage}
\end{figure}

\begin{figure}
    \centering
        \includegraphics[scale=0.23]{barpower.pdf}\vspace{-0.2cm}
    \caption{Market power quantification versus coalition size. \vspace{-0.5cm}}
    \label{fig:powers}
\end{figure}

\section{Market Power Index}
\label{sec:4}
The additional profits brought by strategic bidding can actually measure market power. More precisely, suppose two generators ($i$ and $j$) collude together, and all other generators are truthful, we can similarly characterize $M(i\cup j)$ as follows:
\begin{equation}
\label{M_cup_def}
   M(i\cup j)\coloneqq \sup \{\tilde{P}_{i\cup j}\}\!-\!P_{i\cup j}\!=\!c^{\{i,j\}}(y)\!-\!c(y)\!-\!P_i\!-\!P_j.
\end{equation}

Due to space limit, we omit the details in deriving Eq. (\ref{M_cup_def}). Instead, we prove the following theorem to highlight that index $M(\cdot)$ is suitable to characterize market power.

\vspace{0.1cm}
\noindent \textbf{Theorem 2}: Index $M$ is supermodular, i.e.,
\begin{equation}
    M(i\cup j)\ge M(i)+M(j), \forall i\neq j.
\end{equation}

We further examine the existence of market power in the IEEE RTS 96 node system \cite{TP-toolbox-web}. This model consists of 24 generators (which can be categorized into 7 types). We modify the system parameters such that all the generators share the same capacity of 100MW. We quantify market power with total load ranging from 510MW to 1734MW, and we consider at most 6 generators can collude together. This is because without any 6 generators, the rest can still meet the total demand. From Figs. \ref{fig:percentage} and \ref{fig:powers}, it is evident that when more generators collude together, they are more likely to have market power (Fig. \ref{fig:percentage}) and surprisingly, their average ability in manipulating the market increases almost linearly in the coalition size (Fig. \ref{fig:powers}).

\section{Concluding Remarks}
\label{sec:5}
In this letter, we identify the existence of strategic behaviors in a restricted setting for CHP scheme. This highlights the existence of market power in the general CHP schemes. We intend to examine the impacts of heterogeneous generation capacities as well as the network constraints on market power quantification in our future work.

\begin{small}
\bibliographystyle{ieeetr}

\section{Introduction}

In general, the electricity market is organized by a sequence of processes: unit commitment, day-ahead market, real time market, balancing market, \emph{etc}. Since the focused of different processes are diverse often, the incentives they provide do not necessarily align with each other. For example, convex hull pricing (also know as extended locational marginal price (elmp)) is proposed to relieve the tension from unit commitment to real time market, by providing the minimal uplift payment to the generators \cite{o2005efficient,hogan2003minimum,Gribik,Schiro}.

However, although remarkable in improving the system efficiency by reallocating the market surplus between supply and demand \cite{Thompson}, in this letter, we find that the incentive issues in the convex hull pricing scheme has not been fully solved due to the non-convex cost structure.

In this letter, we first revisit the convex hull pricing scheme in Section \ref{sec:2}. And then we seek to understand each individual firm's possible strategic behaviors in Section \ref{sec:3}. Based on the identified behaviors as well as the associated profit gains, we propose the market power index for convex hull pricing scheme in Section \ref{sec:4}. We highlight the existence of the market power in real systems via numerical studies in Section \ref{sec:5}. Finally, concluding remarks and future directions are given in Section \ref{sec:6}.





\section{Convex Hull Pricing: A Brief Revisit}
\label{sec:2}
In this letter, we revisit the convex hull pricing in the electricity pool model with $n$ generators in the system. To highlight the existence of strategic behaviors, we assume all the generators have the same capacity $G$. In such a model, the system operator seeks to minimize the total generation costs in a particular time slot:
\begin{equation}
    \begin{aligned}
    c(y)\coloneqq \min_\textbf{g} &\sum_{i=1}^n f_i(g_i)\\
    s.t. &\quad \sum_{i=1}^n g_i=y,\\
    &0\le g_i\le G,
\end{aligned}
\end{equation}
where $g_i$ denote the output of generator $i$, $f_i(g_i)$ denotes the generation cost for generator $i$, vector $\textbf{g}$ is $[g_1,...,g_n]$, and $y$ is the total load in the system. Note that, the optimal solution $\textbf{g}^*(y)$ and the optimal objective value $c(y)$ are both functions of $y$.

If the generation costs $f_i(\cdot)$s are linear functions in $g_i$s, then the system operator could simply conduct the economic dispatch according to the merit order and set the price as the marginal cost.

However, in the practice, there are start up costs associated with generation, hence, for generator $i$, $f_i(g_i)$ is often of the following form:
\begin{equation}
    f_i(g_i)=s_i\cdot I_{(g_i>0)}+v_i\cdot g_i
\end{equation}
where $s_i$ is the sum of fixed cost and the start up cost, and $v_i$ is the variable cost. To highlight the non-convexity in the cost structure, we employ the indicator function $I(\cdot)$. Such a cost structure challenges the conventional scheme in terms of dispatch order, price setting, and incentive issues.

The solution proposed by convex hull pricing is to design the uplift payment such that the generators will follow the system operator's dispatch profile.

{\color{blue}We first focus on the allocation of the total uplift $Uplift(p,y)$. For generator $i$, when it faces the price $p$, the maximal profit $\pi^*_i(p)$:
\begin{equation}
    \pi_i^*(p)=\max_{z\in [0,G]}\{p\cdot z-f_i(z)\}
\end{equation}
Then $\pi^*(p)$ can be rewritten as
\begin{equation}
    \pi^*(p)=\sum_{i=1}^n\pi_i^*(p)
    \label{allocation}
\end{equation} 
Since $\pi(p,y)=p\cdot y-c(y)=\sum_{i=1}^n\{p\cdot g_i^*-f_i(g_i^*)\}$, for generator $i$, when the demand is $y$ and the price is $p$, the uplift is:
\begin{equation}
    Uplift_i(p,y)=\pi_i^*(p)-[p\cdot g_i^*-f_i(g_i^*)]
    \label{def:uplift}
\end{equation}

Then $Uplift(p,y)=\Sigma_{i=1}^n Uplift_i(p,y)$. Convex Hull Pricing guarantees the price $p^*$ can minimize the total uplift,
\begin{equation}
    Uplift(p^*,y)=\min_p Uplift(p,y)=\min_p \sum_{i=1}^n Uplift_i(p,y)
\end{equation}
The output set $g_i^d(p)$ is the maximal of all desired output which can reach the maximal profit:
\begin{equation}
    g_i^d(p)\coloneqq \max \{arg\max_{z\in [0,G]}\{p\cdot z-f_i(z)\}\}
    \label{def:g_i^d}
\end{equation}
 Suppose the system demand is $y$, we have the following fact:
\begin{lemma}
\begin{equation}
    p^*=inf\{p|\sum_{i=1}^ng_i^d(p)\ge y\}
\end{equation}
\label{lemma:price}
\end{lemma}
Proof is in Appendix.
This is convex hull pricing}

However, the convex hull pricing only guarantee the minimal total uplift payment, it does not fully mitigate generators opportunities in obtaining more profits by strategic bidding.





\section{Strategic Behavior Analysis}
\label{sec:3}
 We seek to understand generator's strategic behaviors via analyzing their profit. For each generator, its total profit are gained from the uplift payment as well as selling electricity according to the dispatch profile from the system operator. We want to emphasize that the second component is not necessarily positive, which further implies the importance of uplift payment. {\color{blue}And we assume the generator cannot withhold its capacity.} Hence, it can only strategically bid its cost function. Since the fixed cost and the start up cost are rather stable, the only remaining opportunity is to manipulate the variable cost $v_i$ , for each generator.
 
 Mathematically, if the generator truthfully bids its $v_i$, we denote its profit as benchmark:
 \begin{equation}
     P(p^*) = \pi_i(p^*) = p^*\cdot g_i^d(p^*)-f_i(g_i^d(p^*))
 \end{equation}
 Note that $P(p^*)$ is non-decreasing in $p^*$.
 
 On the other hand, if the generator strategically reports its generation cost as $\Tilde{f}_i(\cdot)$, which may lead to a potentially different CHP $\Tilde{p}^*$, and a potentially different dispatch dispatch profile $\Tilde{\textbf{g}}^*$.







\section{Strategically Bidding(Personal)}
\label{sec:strategically}
\subsection{Gain Decomposition}
If the generator strategically reports its generation cost as $\Tilde{f}_i(\cdot)$, when demand is $y$, the price obtained from Convex Hull Pricing is $\Tilde{p}^*$, and the system dispatch is $\Tilde{\textbf{g}}^*$. The profit of generating as dispatch $\Tilde{g}_i^*$ is $\Tilde{p}^*\cdot \Tilde{g}_i^*-f_i(\Tilde{g}_i^*)$. According to equality (\ref{def:uplift}),
\begin{equation}
    \Tilde{Uplift}_i(\Tilde{p}^*)=\pi_i^*(\Tilde{p}^*)-[\Tilde{p}^*\cdot \Tilde{g}^*_i-\Tilde{f}_i(\Tilde{g}^*_i)]
\end{equation}
So, the gain of pretending as $\Tilde{f}_i(\cdot)$ is:
\begin{equation}
    \Tilde{gain}_i=gain_{\Tilde{i}}(\Tilde{p}^*)+guise_{\Tilde{i}}(\Tilde{g}^*)
    \label{eq:gain decomposition}
\end{equation}
where $gain_{\Tilde{1}}=\Tilde{p}^*\cdot \Tilde{g}_i^d(\Tilde{p}^*)-\Tilde{f}_i(\Tilde{g}_i^d(\Tilde{p}^*))$ is the gain of a virtual generator $\Tilde{i}$ whose cost function is $\Tilde{f}_i(\cdot)$. And $guise_{\Tilde{i}}=\Tilde{f}_i(\Tilde{g}_i^*)-f_i(\Tilde{g}^*_i)$ is the ``cost'' to pretend as the generator $\Tilde{i}$.

\subsection{ISO dispatch}
\label{subsection:Setting}
We further assume $f_i(g_i)=c_i\cdot I_{g_i>0}+v_i\cdot g_i$ where $c_i$ is the combination of fixed cost and start-up cost, $v_i$ denotes the variable cost and $I(\cdot)$ is the indicator function. We order generators in this way: $f_1(G)\le ...\le f_n(G)$. 

We claim the following fact:

\begin{lemma}
When $y=(m-1)\cdot G+x$ where $x\in (0,G]$, there is an optimal dispatch $\textbf{g}^*$ satisfies:

(a) there are $m-1$ elements of $\textbf{g}^*$ is $G$,

(b) one generator is dispatched at $x$ units,

(c) and $n-m$ elements of $\textbf{g}^*$ is 0.
\label{lemma:dispatch}
\end{lemma}

Proof can be see in Appendix. To further explore the structure of dispatch, we have the following observation which hold for any bidding profile: Denote $[m]$ as the set $\{1,...,m\}$. Define $P_{m-1}^i\coloneqq arg\max\{v_k|k\in [m-1]\verb|\|\{i\}\}$ and we omit superscript when $\{i\}=\varnothing$. Similarly $Q_{m-1}^i\coloneqq arg\min\{f_k(x)|k\in[n]\verb|\|([m-1]\cup\{i\})\}$. 

\begin{lemma}

Dispatch:

If $f_m(G)-G\cdot v_{P_{m-1}}\le f_{Q_{m-1}}(x)-x\cdot v_{P_{m-1}}$, the optimal dispatch $\textbf{g}^*$ is: $g^*_{P_{m-1}}=x$, $g^*_{k}=G,k\in[m]\verb|\|\{P_{m-1}\}$. Otherwise, $g^*_{Q_{m-1}}=x$, $g^*_k=G, k\in [m-1]$.


Gain:

$gain_k=(f_m(G)-f_k(G))^+$.
\label{lemma:dispatch structure}
\end{lemma}

One corollary which will always be used in following part is:

a) If $i<m$, then $g_i^*\in\{x,G\}$; If $i>m$, then $g_i^*\in\{0,x\}$

b) If $g_i^*=0$, then $i\le m$; If $g_i^*=G$, then $i\ge m$


\subsection{Gain analysis}
Frequent changes on the fixed cost and start-up cost $c_i$ may be not convincing. We assume only $v_i$ can be reported strategically as $v_{\Tilde{i}}$. We consider there is only one generator $i$ can report cost strategically. Now we analyse the gain of different biddings. Based on Lemma \ref{lemma:dispatch}, we know $\Tilde{g}^*_i\in\{0,G,x\}$. 

\begin{itemize}
    \item If $\Tilde{g}^*_i=0$:
\end{itemize}

From Lemma \ref{lemma:dispatch structure}, it must be $\Tilde{f}_i(G)\ge \Tilde{f}_m(G)$ where $\Tilde{f}_m(G)\coloneqq\{\Tilde{f}_k(G)\}_{m}$ and $\{\}_m$ means the $m_{th}$ order statistics. In others words, generator $m$ is the generator who can decide the price in the world where generator $i$ reported strategically. Then we have $\Tilde{gain}_i=0$. There is no incentive to lie to make $\Tilde{g}^*_i=0$ for any generator.
\begin{itemize}
    \item If $\Tilde{g}^*_i=x$:
\end{itemize}

 When $\Tilde{f}_i(G)> \Tilde{f}_m(G)$, it means $i$ pretends to be ``$Q_{m-1}$'' in the ISO's view. So, $\Tilde{gain}_i=\Tilde{f}_i(x)-f_i(x)$ which increases with $\Tilde{v}_i$ increasing. In ISO's view, $\Tilde{f}_i(x)+\sum_{k=1}^{m-1}\Tilde{f}_k(G)$ is the total social cost to meet the demand $y$. $A$ is a set consist generators, define $c^{A}(y)$ as follows:
\begin{equation}
    \begin{aligned}
        c^{A}(y)&\coloneqq\min_{\textbf{g}} f
_k(g_k)\\
s.t. \quad &\sum_{k=1}^n g_k=y &\\
& g_k=0  &k\in A\\
& 0\le g_k\le G  &k\in [n]
\end{aligned}
\end{equation}
Noting that in optimization problem $c^i(y)$, the parameter is $f_k$ rather than $\Tilde{f}_k$ since $i$ is the only generator who can lie. 

Since $\Tilde{f}_i(G)> \Tilde{f}_m(G)$, the system will dispatched generator $i$ at unit $x$ either 0. To guarantee $\Tilde{g}^*_i=x$ rather than 0, in ISO's view, the total social cost is less than $c^{\{i\}}(y)$, i.e. $\Tilde{f}_i(x)+\sum_{k=1}^{m-1}\Tilde{f}_k(G)\le c^{\{i\}}(y)$. And $\sum_{k=1}^{m-1}\Tilde{f}_k(G)=c^{\{i\}}((m-1)\cdot G)$. So $sup\{\Tilde{gain}_i|\Tilde{g}^*_i=x, \Tilde{f}_i(G)>\Tilde{f}_m(G)\}=c^{\{i\}}(y)-c^{\{i\}}((m-1)\cdot G)-f_i(x)$.

When $\Tilde{f}_i(G)\le\Tilde{f}_m(G)$, it means $i$ pretends to be ``$P_{m-1}$'' in the ISO's view. $\Tilde{gain}_i=\Tilde{f}_m(G)-\Tilde{f}_i(G)+\Tilde{f}_i(G)-f_i(x)$. We have $\Tilde{f}_i(G)+c^{\{i\}}(y-G)\ge \Tilde{f}_m(G)+\Tilde{f}_i(x)+c^{\{i\}}((m-2)\cdot G)$ which guarantee $\Tilde{g}^*_i=x$ rather than $G$. So the maximal gain is $sup\{\Tilde{gain}_i|\Tilde{g}^*_i=x, \Tilde{f}_i(G)\le\Tilde{f}_m(G)\}= c^{\{i\}}(y-G)-c^{\{i\}}((m-2)\cdot G)-f_i(x)$.

Since the following lemma:

\begin{lemma}
$f_{m-1}(G)\le c(y)-c(y-G)\le f_m(G)$
\label{lemma:social cost}
\end{lemma}
we can sum up, if generator $i$ want to lie to make $\Tilde{g}_i^*=x$, $sup\{\Tilde{gain}_i|\Tilde{g}^*_i=x\}=c^{\{i\}}(y)-c^{\{i\}}((m-1)\cdot G)-f_i(x)$.

\begin{itemize}
    \item If $\Tilde{g}^*_i=G$:
\end{itemize}

$\Tilde{f}_i(G)\le \Tilde{f}_m(G)$, $\Tilde{gain}_i=\Tilde{f}_m(G)-f_i(G)$. Obviously, for generator $i>m$, they have no incentive to lie in this way. If any generator $i\le m$ lie to make $\Tilde{g}^*_i=G$ and keep $\Tilde{f}_m(G)=f_m(G)$, their gain does not changed. So to gain more benefit, generator $i(i\le m)$ have to make $\Tilde{f}_m(G)>f_m(G)$. Since $i$ is the only generator who can lie, so, $\Tilde{f}_i(G)=\Tilde{f}_m(G)$. Then to make $\Tilde{g}_i^*=G$, we have to guarantee: $\Tilde{f}_m(G)+c^{\{i\}}(y-G)\le c^{\{i\}}(y)$. So $sup\{\Tilde{gain}_i|\Tilde{g}^*_i=G\}=c^{\{i\}}(y)-c^{\{i\}}(y-G)-f_i(G)$.

\subsection{Market Power}

We define market power of generators $i$ is $M(i)$:
\begin{equation}
    M(i)\coloneqq\ sup\{\Tilde{gain}_i\}-gain_i
\end{equation}
Now we sort the generators into 3 groups according to original optimal dispatch: $g_i^*=0$, $g_i^*=x$, $g_i^*=G$ and analyse their market power.

For generators satisfies $g^*_i=0$, $M(i)=0$. Detail can be seen in appendix. For generators satisfies $g^*_i=x$, $c^{\{i\}}((m-1)\cdot G)+f_i(x)=c(y)\le c^{\{i\}}(y-G)+f_i(G)$ (otherwise $g^*_i=x$ would not hold), so $M(i)=\{c^{\{i\}}(y)-c(y)-gain_i\}^+$. For generators satisfies $g^*_i=G$, similarly we can get $M(i)=\{c^{\{i\}}(y)-c(y)-gain_i\}^+$.


\begin{lemma}

(a) For any generator, to purchase the maximal profit,$\Tilde{g}^*_i=g^*_i$, i.e. the optimal dispatch does not changed.

(b) For any generator $i$, $M(i)=\{c^{\{i\}}(y)-c(y)-gain_i\}^+$.
\end{lemma}

We use a figure to summarize:



\section{Strategically Bidding (Coalition of Two)}
\label{sec:coalition}
Consider generator $i$ and $j$ make an alliance and purchase the maximal gain of the alliance. We assume other generators report truthfully. 

Similarly, $M(i\cup j)=c^{\{i,j\}}(y)-c(y)-gain_i-gain_j$.
\begin{theorem}
$M(i\cup j)\ge M(i)+M(j)$
\label{supermodularity}
\end{theorem}
The Theorem \ref{supermodularity} can easily proved by the following Lemma \ref{lemma:less generators more power}. 

\begin{lemma}
For any system demand $y$ and generator $i$ and $j$, $c^{\{i,j\}}(y)-c^{\{j\}}(y)\ge c^{\{i\}}(y)-c(y)$
\label{lemma:less generators more power}
\end{lemma}

\bibliographystyle{ieeetr}

\section{Introduction}
\subsection{non-convexity}
\subsection{convex hull pricing}
\subsection{vulnerability}
\subsection{Price Analysis}
The output set $g_i^d(p)$ consist of all desired output which can reach the maximal profit:
\begin{equation}
    g_i^d(p)\coloneqq arg\max_{z\in [0,G]}\{p\cdot z-f_i(z)\}
    \label{def:g_i^d}
\end{equation}

\emph{Definition (summation of sets):} 
For set $A\in \mathbb{R}$,$B\in \mathbb{R}$, $A+B=\{m+n|m\in A, n\in B\}$ 

\emph{Definition (support-convex-hull price):} 
$price(y)=\{p|y\in \sum_{i=1}^n g^d_i(p)\}$

We have the following fact:

\textbf{Fact 1:}
\begin{equation}
    price(y)\neq \varnothing,\quad \forall y
    \label{not empty}
\end{equation}
Proof can be see in Appendix.

\textbf{Fact 2:}
\begin{equation}
    p^*\in price(y)
    \label{def:p^*}
\end{equation}
Proof can be see in Appendix.
\subsection{}
First we prove $g_i^d(p)$ is non-decreasing, i.e. $\forall p_1<p_2$, $g_i^d(p_1)\le g_i^d(p_2)$:

Suppose $g_i^d(p_1)> g_i^d(p_2)$, since the definition of $g_i^d(p)$ (\ref{def:g_i^d}) which can maximize $h(z)=p\cdot z-f_i(z)$, $z\in [0,G]$:
\begin{align*}
    &p_1\cdot g_i^d(p_1)-f_i(g_i^d(p_1))\ge p_1\cdot g_i^d(p_2)-f_i(g_i^d(p_2))\\
    \Rightarrow &f_i(g_i^d(p_1))-f_i(g_i^d(p_2))\le p_1\cdot(g_i^d(p_1)-g_i^d(p_2))\\
    &p_2\cdot g_i^d(p_2)-f_i(g_i^d(p_2))\ge p_2\cdot g_i^d(p_1)-f_i(g_i^d(p_1))\\
    \Rightarrow & p_2\cdot(g_i^d(p_1)-g_i^d(p_2)) \le f_i(g_i^d(p_1))-f_i(g_i^d(p_2))\\
    \Rightarrow & p_2\cdot(g_i^d(p_1)-g_i^d(p_2)) \le p_1\cdot(g_i^d(p_1)-g_i^d(p_2))
\end{align*}
$\Rightarrow \Leftarrow !$

Intuitively, the higher the price is, the more the generator wants to generate. 


\subsection{}
Define the function $v^{-k}(x)$ where $x\in[0,G]$ and related optimal solution $\textbf{g}^{*-k}(x)$:
\begin{equation}
    \begin{aligned}
    v^{-k}(x)\coloneqq \min_\textbf{g} &\sum_{i>k}^n f_i(g_i)\\
    s.t. &\sum_{i>k}^n g_i=x\\
    &0\le g_i\le G
\end{aligned}
\end{equation}
$m_i\coloneqq\min\{k|\exists x, g^{*-k}_i(x)\neq 0\}$. It is obvious $m_i\le i$. 

\subsection{}
\begin{itemize}
    \item[-] $\frac{c_i}{G}+\Tilde{v}_i< (\frac{c_k}{G}+\Tilde{v}_k)_{m}=\Tilde{p}^*(y)$
\end{itemize}

As for generator $i$ itself, proof of \textbf{Fact 4} shows bidding strategically cannot make any difference. As for other generators, bidding strategically cannot make any difference. 

\begin{itemize}
    \item[-] $(\frac{c_k}{G}+\Tilde{v}_k)_{m}\le \frac{c_i}{G}+\Tilde{v}_i=\Tilde{p}^*(y)\le (\frac{c_k}{G}+\Tilde{v}_k)_{m+1}$
\end{itemize}

The impact is the same as when $i=m-1$.

\begin{itemize}
    \item[-] $(\frac{c_k}{G}+\Tilde{v}_k)_{m+1}=\Tilde{p}^*(y)\le \frac{c_i}{G}+\Tilde{v}_i$
\end{itemize}

The impact is the same as when $i>m-1$.
{\color{blue}Finished, like $G_1$ in [G, 2G]}

\begin{itemize}
    \item $\Tilde{p}^*(y)> \frac{c_i}{G}+\Tilde{v}_i$:
    
    As showed in proof of \textbf{Fact 4}, $\Tilde{gain}_i=gain_i$. Bidding strategically cannot make any difference. 
    
    Since the price is not decided by generator $i$, bidding strategically cannot influence the gain of other generators since $gain_{\Tilde{i}}=\pi^*_{\Tilde{i}}(\Tilde{p}^*)$. {\color{blue}Finished, like $G_1$ in [G, 2G]}
    
    \item $\Tilde{p}^*(y)\le \frac{c_i}{G}+\Tilde{v}_i$:
    
    $gain_{\Tilde{i}}=\pi_{\Tilde{i}}=0$, we have $\Tilde{gain}_i=\Tilde{f}(\Tilde{g}^{*})-f(\Tilde{g}^{*})$
    
    \begin{itemize}
        \item $\Tilde{p}^*(y)< \frac{c_i}{G}+v_i$:
        
        As for generator $i$ itself, denote $v_{-i}(y)$ as the minimal system cost to meet demand $y$ if there is no generator $i$. The maximal gain the generator $i$ can get is $v_{-i}(y)-v(y)$ by biding strategically $\Tilde{v}_i=v_{i}+\frac{v_{-i}(y)-v(y)}{y}$.
        
        Also bidding strategically cannot influence the gain of other generators. {\color{blue}Finished, like $G_4$ in [0, G]}
        
        \item $\Tilde{p}^*(y)\ge \frac{c_i}{G}+v_i$:
        
        
        
    \end{itemize}
\end{itemize}



\begin{itemize}
    \item $\Tilde{p}^*(y)< \frac{c_i}{G}+v_i$ and $g_i^{*-(m-1)}=0$:
    
    Due to \textbf{Fact 4}, $f(\cdot)\le \Tilde{f}(\cdot)$, so $\Tilde{g}^{*-(m-1)}_i\le g_i^{*-(m-1)}=0$. The system will not dispatch generator $i$. $gain_{\Tilde{i}}=guise=0$. Bidding strategically cannot make any difference. {\color{blue}Finished, like $G_4$ in [0,G]}
    
    \item $\Tilde{p}^*(y)< \frac{c_i}{G}+v_i$ and $g_i^{*-(m-1)}\neq 0$:
    
    since $\frac{c_i}{G}+v_i\le \frac{c_i}{G}+\Tilde{v}_i$, $\Tilde{p}^*(y)< \frac{c_i}{G}+\Tilde{v}_i$, as the proof of \textbf{Fact 4} shows, $gain_{\Tilde{i}}=0$. {\color{blue}not finished, like $G_4$ in [G,2G]}
    
    \item $\frac{c_i}{G}+v_i\le \Tilde{p}^*(y)\le \frac{c_i}{G}+\Tilde{v}_i$:
    
    $gain_{\Tilde{i}}=0\Rightarrow \Tilde{gain}_i=\Tilde{f}(\Tilde{g}^*(x))-f(\Tilde{g}^*(x))$. 
    {\color{blue}not finished, like $G_1$ in [0,G]}
    
    \item $\Tilde{p}^*(y)> \frac{c_i}{G}+\Tilde{v}_i$:
    
    As showed in proof of \textbf{Fact 4}, $\Tilde{gain}_i=gain_i$. Bidding strategically cannot make any difference. {\color{blue}Finished, like $G_1$ in [G,2G]}
\end{itemize}

Here we only consider generator $1$ can report strategically to pretend as generator $\Tilde{1}$. There are two situations:
\begin{enumerate}
    \item $c_1+\Tilde{v}_1\cdot G\le c_2+v_2\cdot G$
    \item $c_1+\Tilde{v}_1\cdot G> c_2+v_2\cdot G$
\end{enumerate}

\emph{situation 1):}

According to the bids, the price of demand should be:
\begin{equation}
    p^*(y)=\left\{
\begin{aligned}
&\frac{c_1}{G}+\Tilde{v}_1 & y\in[0,G]&\\
    &\frac{c_i}{G}+v_i & y\in[(i-1)\cdot G,i\cdot G]&\quad i>1
    \end{aligned}
\right.
\end{equation}

In this situation, when demand $y\ge G$, $\Tilde{g}_1^*(y)=G$. Then:
\begin{equation}
    \Tilde{gain}_1= (c_i-c_1)+(v_i-v_1)\cdot G \quad y\in [(i-1)\cdot G,i\cdot G]
\end{equation}
which is equal to the gain of truthfully bidding.

However, when demand $y\in [0,G]$, the gain of truthfully bidding is 0. The uplift of generator $\Tilde{1}$ is 0. But the cost of pretending as $\Tilde{1}$ is $(v_1-\Tilde{v}_1)\cdot \Tilde{g}_1^*$ where $\Tilde{g}_1^*=y\cdot I(y)$. $I$ is the indicator function:
\begin{equation}
    I(y)=\left\{
\begin{aligned}
1 \quad &  y\in [\max_i\{\frac{c_1-c_i}{v_i-\Tilde{v}_1}\},G]\\
0 \quad & y\in[0,\max_i\{\frac{c_1-c_i}{v_i-\Tilde{v}_1}\})
\end{aligned}
\right.
\end{equation}

If the demand is believed to be an uniform distribution in $[d,d+l]\subset [\max_i\{\frac{c_1-c_i}{v_i-v_1}\},G]$, the expected gain of pretending as generator $\Tilde{1}$ is:
\begin{align}
    \mathbb{E}\Tilde{gain}_1=&\mathbb{E}((v_1-\Tilde{v}_1)\cdot \Tilde{g}_1^*)\\
    =&\frac{1}{2}(\Tilde{v}_1-v_1)[(d+l)^2-(\max_i\{\frac{c_1-c_i}{v_i-\Tilde{v}_1}\})^2]
\end{align}

\textbf{To sum up}, according to the believed demand interval $[d,d+l]$, the best strategy for generator 1 $\Tilde{v}^*_1$ is :
\begin{enumerate}
\item[*] If $d+l\le\max_i\{\frac{c_1-c_i}{v_i-v_1}\}$ or $d\ge G$: $\Tilde{v}^*_1=v_1$
\end{enumerate}
\section{APPENDIX}
Proof of \textbf{Fact 2}:

To prove the \textbf{Fact 2}, it is sufficient to show for any system demand $y$, $\sum_{i=1}^n Uplift_i(p)\ge \sum_{i=1}^n Uplift_i(p^*(y))$ for any $p$. Choose $\{z_i|z_i\in g_i^d(p)\}_{i=1}^n$ and $\{z^*_i|z^*_i\in g_i^d(p^*)\}_{i=1}^n$:

\begin{align*}
    &\sum_{i=1}^n Uplift_i(p)-\sum_{i=1}^n Uplift_i(p^{*})\\
    =&p\cdot (\sum_{i=1}^n z_i\!-\!y)\!-\!\sum_{i=1}^n f_i(z_i)+\!\sum_{i=1}^n f_i(z_i^*)\\
    =&p\cdot (\sum_{i=1}^n z_i-\sum_{i=1}^n z_i^*)-\sum_{i=1}^n f_i(z_i)+\sum_{i=1}^n f_i(z_i^*)\\
    =&\sum_{i=1}^n \{p\cdot z_i-f_i(z_i)-[p\cdot z_i^*-f_i(z_i^*)]\}\\
    \ge &0
\end{align*}
The last inequality holds due to equality (\ref{def:g_i^d}).
$\hfill\blacksquare$

Proof of \textbf{Fact 1}:
Suppose $\exists y$, $price(y)=\varnothing$, then $\exists p'$, satisfies
\begin{align*}
    &\forall \epsilon>0, \min \sum_{i=1}^n g^d_i(p'+\epsilon)>y\\
    &\forall \epsilon>0, \max \sum_{i=1}^n g^d_i(p'-\epsilon)<y
\end{align*}
By the following \textbf{Fact 3}, 
\begin{align*}
    &\lim_{\epsilon\rightarrow 0^+}\max \sum_{i=1}^n g^d_i(p'-\epsilon)=\min\sum_{i=1}^n g_i^d(p')\\
    &\lim_{\epsilon\rightarrow 0^+}\min \sum_{i=1}^n g^d_i(p'+\epsilon)=\max\sum_{i=1}^n g_i^d(p')
\end{align*} 
Since $\sum_{i=1}^n g^d_i(p')$ is an interval, we have $y\in \sum_{i=1}^n g_i^d(p')$, $\Rightarrow \Leftarrow !$.
$\hfill\blacksquare$

\textbf{Fact X:}

$\max g_i^d(p)=\lim_{\epsilon\rightarrow 0^+}\min g_i^d(p+\epsilon)$

Proof of \textbf{Fact X}:

(a) $g^d_i(p)$ is interval:

Since $f'(\cdot)$ is non-decreasing, $p-f'(\cdot)$ is non-increasing, which result in $g^d_i(p)$ is interval (a point is a special interval).

(b)$\forall p_1<p_2$, $\forall z_1\in g_i^d(p_1)$, $z_2\in g_i^d(p_2)\Rightarrow z_1\le z_2$:

Suppose $z_2<z_1$, we have $f_i(z_1)\ge f_i(z_2)$. Since $z_1\in g_i^d(p_1)$, 
\begin{align*}
    &p_1\cdot z_1-f_i(z_1)\ge p_1\cdot z_2-f_i(z_2)\\
    \Rightarrow & f_i(z_1)-f_i(z_2)\le p_1\cdot(z_1-z_2)<0
\end{align*}
$\Rightarrow \Leftarrow !$.

We can drive $\max g_i^d(p)\le \lim_{\epsilon\rightarrow 0^+}\min g_i^d(p+\epsilon)$ from (b). $\forall p,\Bar{z}\coloneqq \max g_i^d(p)$,
\begin{align*}
    &\forall z>\Bar{z},\Delta\coloneqq p\cdot \Bar{z}-f_i(\Bar{z})-[p\cdot z-f_i(z)]>0\\
    &\forall 0<\epsilon<\frac{\Delta}{z}, p\cdot \Bar{z}-f_i(\Bar{z})> (p+\epsilon)\cdot z-f_i(z)
\end{align*}
since  $f'(\cdot)$ is non-decreasing, if $\min g_i^d(p+\epsilon)\ge z$, then
$$(p+\epsilon)\cdot\Bar{z}-f_i(\Bar{z})\le (p+\epsilon)\cdot z-f_i(z)<p\cdot \Bar{z}-f_i(\Bar{z})$$
$\Rightarrow \Leftarrow !$. So, 
\begin{align*}
    &\forall z>\Bar{z}, \lim_{\epsilon\rightarrow 0^+}\min g_i^d(p+\epsilon)<z\\
    \Rightarrow & \lim_{\epsilon\rightarrow 0^+}\min g_i^d(p+\epsilon)=\Bar{z}=\max g_i^d(p)
\end{align*} 
$\hfill\blacksquare$

\subsection{}
\begin{itemize}
    \item $i>m-1$:
\end{itemize}    

This means $\Tilde{p}^*(y)< \frac{c_i}{G}+v_i\le \frac{c_i}{G}+\Tilde{v}_i$. In other word, $\Tilde{p}^*(y)$ is not decided by generator $i$.
    
As for generator $i$ itself,  $gain_{\Tilde{i}}=\pi^*_{\Tilde{i}}(\Tilde{p}^*(y))=0\Rightarrow \Tilde{gain}_i=\Tilde{f}_i(\Tilde{g}^{*})-f_i(\Tilde{g}^{*})=(\Tilde{v}_i-v_i)\cdot g_i^*$. Denote $\Tilde{v}(y)$ as the minimal system cost (according to bid) to meet demand $y$ and $v_{-i}(y)$ as the minimal system cost (whether according to bid does not matter since $i$ is the only one who can bid strategically) to meet demand $y$ if there is no generator $i$.

\begin{equation}
    \begin{aligned}
    \Tilde{v}(y)\coloneqq \min_\textbf{g} &\sum_{i=1}^n \Tilde{f}_i(g_i)\\
    s.t. &\sum_{i>k}^n g_i=y\\
    &0\le g_i\le G
\end{aligned}
\end{equation}

Due to \textbf{Fact 3}, as long as $v_{-i}(y)-\Tilde{v}(y)> 0$, $\Tilde{g}^*_i=x$. Otherwise $\Tilde{g}^*_i=0$.
    \begin{equation}
        \frac{\Delta \Tilde{gain}_i}{\Delta \Tilde{v}_i}=\left\{
        \begin{aligned}
        x & \quad v_{-i}(y)-\Tilde{v}(y)> 0\\
        0 & \quad v_{-i}(y)-\Tilde{v}(y)= 0
        \end{aligned}
        \right.
    \end{equation}
When $\Tilde{v}(y) \le v_{-i}(y)$, $\Tilde{v}(y)=\Tilde{v}((m-1)\cdot G)+\Tilde{f}_i(x)$, $v(y)=v((m-1)\cdot G)+f_i(x)$. So the maximal gain for the generator $i$, $\Tilde{f}_i(x)-f_i(x)=v_{-i}(y)-v(y)$ by biding strategically $\Tilde{v}^*_i=v_{i}+\frac{v_{-i}(y)-v(y)}{x}$.
        
As for other generators, since $\Tilde{p}^*(y)$ is not decided by generator $i$, so generator $i$'s bidding strategically cannot influence the gain of other generators. {\color{blue}Finished, like $G_4$ in [0, G]}
 \begin{itemize}   
    \item $i=m-1$:
\end{itemize}

As for generator $i$ itself, since $\Tilde{p}^*(y)\le \frac{c_i}{G}+\Tilde{v}_i$ still hold, so the analyse is the same as when $i>m-1$. The best strategy is $\Tilde{v}^*_i=v_{i}+\frac{v_{-i}(y)-v(y)}{x}$.

As for other generators, $\Tilde{p}^*(y)$ can be raised until $(\frac{c_k}{G}+\Tilde{v}_k)_{m+1}$, which can result additional $[(\frac{c_k}{G}+\Tilde{v}_k)_{m+1}-(\frac{c_k}{G}+\Tilde{v}_k)_{m}]\cdot G$ gain for the lower $m-1$ bidders. {\color{blue}Finished, like $G_2$ in [G, 2G]}

 \begin{itemize}   
    \item $i<m-1$:
\end{itemize}

As for generator $i$ itself, if reports truthfully, the gain is $f_m(G)-f_i(G)$. If $(\frac{c_k}{G}+v_k)_{m}\ge \frac{c_i}{G}+\Tilde{v}_i$, bid strategically cannot make any difference. Otherwise, the impact is the same as that when $i>m-1$. Only when $ v^{-1}(y)> v^{-1}((m-1)\cdot G)+c_i+\frac{f_m(G)-c_i}{G}$, $v^{-1}(y)>\Tilde{v}(y)$ can be possible and $\Tilde{g}^*_i=x$. The maximal gain is $\Tilde{gain}^*_i=v_{-i}(y)-v_{-i}((m-1)\cdot G)-f_i(x)$. Otherwise $\Tilde{gain}^*_i=0$. 

As for other generators,the impact is the same as that when $i=m-1$.



\section{WOW}
\textbf{WOW}
We consider there is only one generator $i$ can report cost strategically, i.e. $\Tilde{v}_j=v_j$ when $j\neq i$. Next we will analysis how $i$ affects the gain of itself and other generators when $i$ belong to different types. 

First, we reveal the influence on other generators. By the following two facts:

(a)\begin{lemma}
For any generator $i$, $\Tilde{v}_i\le v_i$ cannot gain more than $\Tilde{v}_i=v_i$ (Proof can be see in Appendix).
\label{lemma:lie variable cost}
\end{lemma}


(b)Based on Lemma \ref{lemma:price},
\begin{equation}
    \Tilde{p}^*(y)=\{\frac{\Tilde{f}_k(G)}{G}\}_{m}
    \label{eq:one stage p^*}
\end{equation}


Combine Lemma \ref{lemma:lie variable cost} and (\ref{eq:one stage p^*}), we have $\Tilde{p}^*\ge p^*$. So gain of other truthful generators will not get decreasing since $gain_i(\cdot)$ is non-decreasing.

Next, we analysis the influence on $i$'s gain. We define market power of generators $i$ is $M(i)$:
$$M(i)\coloneqq\ sup_{\Tilde{v}_i}\{\Tilde{gain}_i\}-gain_i$$

\subsection{Market Power}
\begin{itemize}
    \item $i\in $(i):
\end{itemize}  

$i\in $(i) means $p^*\le \frac{f_i(G)}{G}$, so $gain_i=0$. Then for any $\Tilde{v}_i$, $\Tilde{p}^*\le \frac{\Tilde{f}_i(G)}{G}$. So $gain_{\Tilde{i}}=\pi^*_{\Tilde{i}}=0$. Since $\Tilde{f}_i(\cdot)\le f_i(\cdot)$, $\Tilde{g}^*\le g^*=0$ which means $guise_{\Tilde{i}}=0$. We have $M(i)=0$.

\begin{itemize}
    \item $i\in $(ii):
\end{itemize} 

$i\in $(ii) means $p^*\le \frac{f_i(G)}{G}$, so $gain_i=0$. Then for any $\Tilde{v}_i$, $\Tilde{p}^*\le \frac{\Tilde{f}_i(G)}{G}$. So $gain_{\Tilde{i}}=\pi^*_{\Tilde{i}}=0$. 

Denote$v_{m-1}^{i}\coloneqq\min\{f_m(x),...f_{i-1}(x),f_{i+1}(x),...,f_n(x)\}$ and $v_{m-1}\coloneqq\min\{f_m(x),...,f_n(x)\}$. Based on Lemma \ref{lemma:dispatch}, $f_i(x)=v_{m-1}$. If $\Tilde{f}_i(x)>v_{m-1}^{i}$, $\Tilde{g}^*=0$ which result $guise_{\Tilde{i}}=0$ and $\Tilde{gain}_i=0$. If $\Tilde{f}_i(x)\le v_{m-1}^{i}$, $\Tilde{g}^*=x$ which result in $\Tilde{gain}_i=\Tilde{f}_i(x)-f_i(x)$. We can drive $M(i)=v_{m-1}^{i}-f_i(x)$.

\begin{itemize}
    \item $i\in $(iii):
    \label{M(i)}
\end{itemize} 
If $i$ bid truthfully, the gain is $gain_i=f_m(G)-f_i(G)$. If $\frac{\Tilde{f}_i(G)}{G}< p^*$, the price and the dispatch will have no changes. If $\frac{\Tilde{f}_i(G)}{G}\ge p^*$, $i$ generator can make change: Generator $m$ will be dispatched at its full capacity to take place the $i$'s capacity and one generator will be dispatched to generate $x$ units. Further more, if $\Tilde{f}_i(x)\ge v_{m}$, $\Tilde{g}^*=0$ which result $\Tilde{gain}_i=0$. If $\Tilde{f}_i(x)< v_{m}$, $\Tilde{g}^*=x$ which result in $\Tilde{gain}_i=\Tilde{f}_i(x)-f_i(x)<v_{m}-f_i(x)$. 
We can drive $sup \Tilde{gain}_i=\max\{v_{m}-f_i(x), gain_i\}$

To sum up, only when $\{\Tilde{v}_i|\frac{\Tilde{f}_i(G)}{G}\ge p^*\}\cap \{\Tilde{v}_i|\Tilde{f}_i(x)< v_{m}\}\neq \varnothing$ and $v_{m}-f_i(x)>gain_i$, $i$ generator has incentive to bid strategically. More detail can be seen in Appendix, when $i\in $(iii), $M(i)=\{v_{m}\!-\!f_i(x)\!-\!(f_m(G)\!-\!f_i(G))\}^+$.

We use a table \ref{table: Market Power of Single Generator} to summarize the maximal gain by bidding strategically, i.e. market power:

\begin{table*}[]
\centering
\begin{tabular}{|c|c|c|c|c|c|}
\hline
                              & $gain_i$                         & $gain_{\Tilde(i)}$ & $\Tilde{g}^*$ & $guise_{\Tilde{i}}$  & $M(i)$                                                            \\ \hline
$i\in$ (i)                    & 0                                & 0                  & 0             & 0                    & 0                                                                 \\ \hline
$i\in$ (ii)                   & 0                                & 0                  & $x$             & $v_{m-1}^{i}-f_i(x)$ & $v_{m-1}^{i}-f_i(x)$                                              \\ \hline
\multirow{2}{*}{$i\in$ (iii)} & \multirow{2}{*}{$f_m(G)-f_i(G)$} & \multirow{2}{*}{0} & $x$             & $v_{m}-f_i(x)$       & \multirow{2}{*}{$\{v_{m}\!-\!f_i(x)\!-\!(f_m(G)\!-\!f_i(G))\}^+$} \\ \cline{4-5}
                              &                                  &                    & G             & 0                    &                                                                   \\ \hline
\end{tabular}
\caption{Market Power of Single Generator}
\label{table: Market Power of Single Generator}
\end{table*}

\section{Strategically Bidding (Coalition of Two)}
Consider generator $i$ and $j$ make an alliance and purchase the maximal gain of summation of the two generators. They can report their cost function as $(\Tilde{f}_i,\Tilde{f}_j)$ and we assume other generators report truthfully. 

\subsection{Property of Strategy}
\begin{lemma}
$(\Tilde{v}_i,\Tilde{v}_i)$ is the best strategy, then $\Tilde{v}_i\ge v_i$ and $\Tilde{v}_j\ge v_j$.
\label{lemma:lie strategy of two}
\end{lemma}

Proof can be seen in Appendix.

\subsection{Coalition Analysis}

In the following part, we will prove 
\begin{lemma}
The supermodularity of market power:

$\forall i, j, M(i)+M(j)\le M(i\cup j)$
\label{lemma:supermodular}
\end{lemma}

$M(i)$ and $M(j)$ are defined as (\ref{eq:gain decomposition}) where there is only one generator can report strategically to purchase its own maximal addition gain. As for $M(i\cup j)$, it is defined in the following situation: both $i$ and $j$ can report strategically whose aim is to maximal the total additional gain of the two generators. More precisely, let $\Tilde{p}^*$ denote the price when $i$ and $j$ report their variable cost as $\Tilde{v}_i$ and $\Tilde{v}_j$ and $\Tilde{\textbf{g}}^*$ as system dispatch:

$M(i\cup j)=sup_{\Tilde{v}_i,\Tilde{v}_j}\{\Tilde{gain}_i+\Tilde{gain}_j\}-(gain_i+gain_j)$
where $\Tilde{gain}_i=gain_{\Tilde{i}}(\Tilde{p}^*)+guise_i(\Tilde{g}_i^*)$. $\Tilde{gain}_i$ is similar definition. 

Since there are 3 types of generator when demand is $y$, and type (ii) has only one generator, there are five different types of alliances. Since $M(\cdot)$ is defined as the upper bound of the additional gain by bidding strategically compared with bidding truthfully, for any type of alliances, to prove the Lemma \ref{lemma:supermodular}, it is sufficient to prove that there is a strategy profile $(\Tilde{v}_i,\Tilde{v}_j)$ by which $\Tilde{gain}_i+\Tilde{gain}_j \ge M(i)+M(j)$.

In the alliance where there is one generator denote as $i$ satisfies $M(i)=0$. Denote $\Tilde{v}^*_j$ as the best strategy when only $j$ can report strategically to purchase its own maximal gain. Since we have proved in \ref{subsection:Setting}, the gain of other generators will not get decreased if $j$ lies. So, consider strategy profile $(v_i,\Tilde{v}^*_j)$, $gain_i\le \Tilde{gain}_i$, $\Tilde{gain}_i=M(j)$ which results in $\Tilde{gain}_i+\Tilde{gain}_j\ge M(j)+M(i)$. The supermodularity of market power holds when there is one generator $i$ whose $M(i)=0$. 

Now we focus on the following two coalitions:

(a). $i\in$(ii); $j\in$(iii) and
$M(i)=v_{m-1}^i-f_i(x)$, $M(j)=v_{m}\!-\!f_j(x)\!-\!(f_m(G)\!-\!f_j(G))>0$ 

(b). $i, j\in$(iii) and $M(i)=v_{m}\!-\!f_i(x)\!-\!(f_m(G)\!-\!f_(G))>0$; $M(j)=v_{m}\!-\!f_j(x)\!-\!(f_m(G)\!-\!f_j(G))>0$ 

First, consider coalition (a):

If $i\neq m$:

Recall that $v_{m}=\min\{f_{m+1}(x),...,f_n(x)\}$, and $f_i(x)=\min\{f_m(x),...,f_n(x)\}$, so we have $v_m=f_i(x)$. Then $M(i)+M(j)=v_{m-1}^i-f_j(x)-f_m(G)+f_j(G)$.

Consider $\Tilde{v}_i=\infty$, in this situation, it is obvious $\Tilde{g}^*_i=0$. $j$ can additionally gain $v_{m}^{-i}-f_j(x)-(f_m(G)-f_i(G))$ where $v_{m}^{-i}=\min\{f_{m+1}(x),...,f_{i-1}(x),f_{i+1}(x),...,f_n(x)\}$. $M(i\cup j)=v_{m}^{-i}-f_j(x)-(f_m(G)-f_i(G))$

It is obvious the supermodularity holds in this condition.

If $i=m$:

Second, consider coalition (b):


\section{Appendix}

Proof of Lemma \ref{lemma:price}:
More clearly, 
\begin{equation}
    g_i^d(p)=\left\{
    \begin{aligned}
    &0 & p<f'_i(0)\\
    &\max\{x|f'(x)\le p\} & 0\le p\le f'_i(G)\\
    &G & p>f'_i(0)\\
    \end{aligned}
    \right.
\end{equation}
When $0\le p\le f'_i(G)$, there are finite $p$s where $f'^{-1}(p)$ is an interval. This result in discontinuity points of $g_i^d(p)$. If $f'^{-1}(p)$ is empty, ${g_i^d}'(p)=0$. If $f'^{-1}(p)$ is a point, $p-f'(g_i^d(p))=0$. So expect the finite discontinuity points, we have $(p-f'(g_i^d(p)))\cdot {g_i^d}'(p)=0$. 

$\sum_{i=1}^n Uplift_i(p,y)$ is continuous in $[0,G]$ and derivable in the area where all $g_i^d(\cdot)$ are derivable.
\begin{equation}
\begin{aligned}
    &\sum_{i=1}^n Uplift'_i(p,y)\\
    =&\sum_{i=1}^ng_i^d(p)-y+\sum_{i=1}^n (p-f'(g_i^d(p)))\cdot {g_i^d}'(p)\\
    =&\sum_{i=1}^ng_i^d(p)-y
    \end{aligned}
\end{equation}

Define $A\coloneqq\{p|\sum_{i=1}^n g_i^d(p)\ge y\}$ and $ B\coloneqq\{p|\sum_{i=1}^n g_i^d(p)<y\}$, it is obvious $\forall a\in A, b\in B, a<b$, $A\cup B=\mathbb{R}^+$ and $A\cap B=\varnothing$. That means $inf A=sup B$. 
As $g_i^d(p)$ is non-decreasing, we have the result $\sum_{i=1}^n g_i^d(p^*)=inf\{p|\sum_{i=1}^n g_i^d(p^*)\ge y\}$.$\hfill\blacksquare$

Proof of Lemma \ref{lemma:dispatch}:

The system minimize system cost according to generators' bidding, suppose there are two generators $i<j$, and $\Tilde{g}^*_i\in (0,G)$, $\Tilde{g}^*_j\in (0,G)$, then we have $\Tilde{v}_i=\Tilde{v}_k$. So, $\{\Tilde{g}^*_1,...g'_i=G,...,g'_j=\Tilde{g}^*_i+\Tilde{g}^*_j-G,\Tilde{g}^*_{j+1},...,\Tilde{g}^*_n\}$ must be anther optimal dispatch. Now we have proved that there is an optimal dispatch where at most one element is between 0 and $G$. Then the Lemma \ref{lemma:dispatch} gets proved. $\hfill\blacksquare$

Proof of Lemma \ref{lemma:lie variable cost}:

When $\Tilde{p}^*(y)\le \frac{c_i}{G}+\Tilde{v}_i$, since $gain_{\Tilde{i}}=\pi^*_{\Tilde{v}_i}=0$, $\Tilde{gain}_i=guise\le 0$ due to $\Tilde{f}(\cdot)\le f(\cdot)$.

When $\Tilde{p}^*(y)>\frac{c_i}{G}+\Tilde{v}_i$, according to \textbf{Fact 3}, $g_i^*=G$, $\Tilde{gain}_i=gain_i$. $\hfill\blacksquare$

Proof of detail \ref{M(i)} ($i\in$(iii)):

``...only when $\{\Tilde{v}_i|\frac{\Tilde{f}_i(G)}{G}\ge p^*\}\cap \{\Tilde{v}_i|\Tilde{f}_i(x)< v_{m}\}\neq \varnothing$ and $v_{m}-f_i(x)>gain_i$...''
$$\frac{\Tilde{f}_i(G)}{G}\ge p^*\Rightarrow \Tilde{v}_i\ge \frac{f_m(G)-c_i}{G}$$
\begin{equation}
    \begin{aligned}
        &\{\Tilde{v}_i|\frac{\Tilde{f}_i(G)}{G}\ge p^*\}\cap \{\Tilde{v}_i|\Tilde{f}_i(x)< v_{m}\}\neq \varnothing\\
        \Rightarrow &c_i+\frac{f_m(G)-c_i}{G}\cdot x< v_{m}\\
    \end{aligned}
\end{equation}

$$v_{m}-f_i(x)>gain_i\Rightarrow f_m(G)-v_i\cdot(G-x)< v_{m}$$

Define $h(x)\coloneqq f_m(G)-v_i\cdot(G-x)$ and $k(x)\coloneqq c_i+\frac{f_m(G)-c_i}{G}\cdot x$, we have $h(G)=k(G)$ and $\frac{f_m(G)-c_i}{G}>\frac{f_i(G)-c_i}{G}=v_i$. Then $h(x)\ge k(x) \forall x\in [0,G]$. So if $v_{m}-f_i(x)>gain_i$ holds, we will have $M(i)=v_{m}-f_i(x)-gain_i$ otherwise $M(i)=0$. $\hfill\blacksquare$

Proof of Lemma \ref{lemma:lie strategy of two}:

Define $gain_{\Tilde{i},\Tilde{j}}$ as the summation of gain of $i$ and $j$ if their reports are $\Tilde{v}_i$ and $\Tilde{v}_j$. First we prove $\forall \Tilde{v}_j\ge v_j$, if $\Tilde{v}_i\le v_i$,  $gain_{\Tilde{i},\Tilde{j}}\le gain_{i,\Tilde{j}}$. Exchange $i$ and $j$, we have a symmetrical result. Second we prove if $\Tilde{v}_i\le v_i$ and $\Tilde{v}_j\le v_j$, $gain_{\Tilde{i},\Tilde{j}}<gain_{i,j}$. Then the lemma \ref{lemma:lie strategy of two} get prove.

First, for any given $\Tilde{v}_j>v_j$, as proved in Lemma \ref{lemma:lie variable cost}, $\Tilde{gain}_i<gain_i$.
Denote the price of $(v_i,\Tilde{v}_j)$ is $p^*$ and the price of $(\Tilde{v}_i,\Tilde{v}_j)$ is $\Tilde{p}^*$. Relatively, the dispatches of $j$ generator are $g_j^*$ and $\Tilde{g}_j^*$. Since $\Tilde{v}_i<v_i$, so $\Tilde{p}^*\le p^*$ and $\Tilde{g}^*_j\le g^*_j$.  For generator $j$, $\Tilde{gain}_{\Tilde{j}}(p)$ is non-decreasing, so $\Tilde{gain}_{\Tilde{j}}(\Tilde{p}^*)\le \Tilde{gain}_{\Tilde{j}}(p^*)$. Since $\Tilde{v}_j>v_j$, $guise_{\Tilde{j}}(g)$ is non-decreasing, so $guise_{\Tilde{j}}(\Tilde{g}^*_j)\le guise_{\Tilde{j}}(g^*_j)$. So, $\Tilde{gain}_j$ will get loss.

Second, we consider two ``parallel world'', one is that all generator bid truthfully, and another is $i$ and $j$ bid $\Tilde{v}_i$ and $\Tilde{v}_j$ as their variable cost relatively when other generators keep telling the truth. The prices, dispatches and gains are relatively denote as $p^*$ and $\Tilde{p}^*$, $\textbf{g}^*$ and $\Tilde{\textbf{g}}^*$ and $gain_i\verb|/| gain_j$ and $\Tilde{gain}_i \verb|/| \Tilde{gain}_j$.

We know $\Tilde{p}^*\le p^*$, take $i$ as an example, if $\frac{\Tilde{f}_i(G)}{G}<\Tilde{p}^*$, then the system will dispatch $i$ at its capacity, i.e. $\Tilde{g}^*=G$. Then we can get the $\Tilde{gain}_i$: 
$$gain_{\Tilde{i}}=\pi_{\Tilde{i}}^*\Tilde{p}^*)=\max_{z\in [0,G]}\{\Tilde{p}^*\cdot z-\Tilde{f}_i(z)\}=\Tilde{p}^*\cdot G-\Tilde{f}_i(G)$$ 
$$guise_{\Tilde{i}}=\Tilde{f}_i(G)-f_i(G)$$
\begin{equation}
\begin{aligned}
\Rightarrow \Tilde{gain}_i&=\Tilde{p}^*\cdot G-f_i(G)=p^*\cdot G-f_i(G)\\
&\le \max_{z\in [0,G]}\{p^*\cdot z-f_i(z)\}=gain_i
    \end{aligned}
\end{equation}
$\hfill\blacksquare$
\end{document}