\section{Introduction}
Cournot Competition in single-market setting has been vastly studied in the literature \cite{kreps1983quantity,fang2015managing,tramontana2015local,constantatos2019accommodation}. In this oligopolistic model, each firm decides the quantity of the homogenous good it is willing to supply to the market. Then, according to the inverse demand function, the market-clearing price is determined based on the aggregate supply in the market. However, with the emergence of diverse and complicated economic scenarios, single-market models are inadequate for studying reality. In many settings, firms can compete in different markets, whether or not the good is identical in those markets. Typically, this situation is modeled using a bipartite graph in which one side of nodes represents firms and the other side depicts various markets. Each market is characterized by an inverse demand function. Multi-market competition is found abundantly in industries such as natural gas, water, electricity, airlines, cement, healthcare, etc \cite{skantze2000stochastic,heggestad1978multi,gilbert2017multi,villena2017dynamics}.

One question that arises naturally in the presence of strategic agents is the means by which it is possible to raise welfare measures \cite{just1979welfare,bateman2006aggregation}. One such measure is social welfare, which aims to capture the aggregate well-being in the economic environment \cite{sen2018collective,clarke1997managerial}. In this case, it is typically the government that seeks and has the responsibility of higher social welfare. While there have been many studies on interactions between firms and equilibria in networked markets (See e.g. \cite{bertrand,shayan,mamtagh}), to the best of our knowledge, there is little work on how to govern and control social welfare in networked markets. The prevalence of networked markets in real-life experiences motivates us to study social welfare in this model. Our paper takes one step forward towards this objective.

We consider a limited intervention budget for the government in the pursuit of higher social welfares. Therefore, we assume that the government is able to have a small amount of supply into every market. This small intervention setting enables us to use some techniques for the estimation of social welfare in terms of government's supplies. The simple structure of the approximation leads to a strategy for the government. However, it is good to note that the actions taken by the government, are specified by the structure of the network. After all, this structure, along with the consumers' behaviors, are sufficient statistics to specify the market.

\subsection{Related Works}
Our work is in essence related to several groups of papers. First, there have been many attempts in studying the strategic behavior of firms and equilibria in the competition \cite{nava2009quantity,shayan,anshelevich2015price,pang2017efficiency}. One such study, which has been our first step-stone, is done by Bimpikis el al. \cite{shayan}, where they present a "characterization of the production quantities at the unique equilibrium of the resulting game for any given network", in terms of supply paths in the network. Furthermore, they introduce the \textit{price-impact} matrix which enables them to explore the effect of changes in network structure on firms' profits and consumer welfare. These changes include entering of a firm in a new market and also merging of two firms. Their results challenge the standard beliefs in Cournot oligopoly that more competition necessarily leads to higher welfare. Relatedly, Abolhassani et al. \cite{mamtagh} turn their focus on finding algorithms that compute pure Nash equilibria in Cournot competitions in networks. In \cite{bertrand}, the impact of monopolies on social welfare in a certain model of Bertrand network competition is studied.

Another thread of studies relevant to ours is the ones analyzing interactions in the networks and their impact on aggregate measures \cite{jackson2010social,aliz, sajadi2018affective,zhang2008clustering}. Most relatedly, Acemoglu et al. \cite{aliz} have proposed a framework that paves the way to examine equilibria in such inter-dependent agents setting and discover the effect of small microeconomic shocks on the economy's aggregate performance. Acting as our main inspiring study, they use Taylor expansion to acquire insights on the impact of shocks. Their examinations yield different results about the economy's \textit{ex ante} aggregate performance in the case of linear and non-linear worlds. To understand how the structure of the network shapes the economy's performance, they demonstrate that the \textit{Bonacich centrality} measure can capture this effect when the nature of the interactions is linear. Such analysis is prevalent in economics. For example, the general notion of production networks demands consideration of dependencies and network effects \cite{primer}.

Lastly, following the connections found between \textit{Bonacich centrality} and network effects in network Cournot competition \cite{shayan,ilkilic2009cournot}, studies about controlling centrality measures in networks can be considered related to ours. Generally, with an established relationship between centrality measures and social welfare in our setting, one might use these methods to change the structure of the competition such that social welfare increases. As such articles, \cite{nicosia2012controlling,liu2012control,bonacich1998controlling} model the centrality control problem as an optimization problem and presents an algorithm to solve it.

\section{Problem Formulation}
Consider a netwok game $\mathcal{G}$ which consists of $n$ firms $F = \{f_1, \cdots, f_n\}$ and $m$ markets $M = \{m_1, \cdots, m_m\}$ in which the firms compete. Each firm has access to a set of markets, meaning that it can supply the goods only in those specific markets. For firm $f_i$, let $M_i$ be the set of those markets.

Similarly, let $F_j$ denote the set of firms that have access to market $m_j$. The amount of good that firm $f_i$ supplies in $m_j$ is shown by $q_{ij}$. Moreover, firm $f_i$ would incur the production cost $C_i(q)$ ($q$ is the vector of all $q_{ij}$s). We consider the inverse demand functions of the markets as linear. More specifically, market $m_j$ is governed by the relation
\begin{equation}
P_j(q) = \alpha_j - \beta_j \sum_{f_i \in F_j} q_{ij}.
\end{equation}
 Additionally,
 \begin{equation}
 C_i(q) = c_i\cdot(\sum_{m_j \in M_i} q_{ij})^2.
 \end{equation}
  For the sake of our analysis, we at first, suppose that for all $m_i \in M$, $\alpha_i = \alpha$ and $\beta_i = \beta$ and for all $f_j \in F$, $c_j = c$. We model this economy with a bipartite graph $G =(V,E)$. An example of this graph can be seen in Figure \ref{f:samplegraph}.

\begin{figure}[h]
\centering
\includegraphics[width=0.3\textwidth]{graph.png}
\caption{A Graph for a Networked Market}
\label{f:samplegraph}
\end{figure}

Briefly speaking, we can consider each $f_i$'s profit as a combination of the afformentioned components:
\begin{equation}
\pi_i(q) = \sum_{m_k \in M_i}{q_{ik}\cdot P_k(q)}-C_i(q)
\end{equation}
 So given a network market graph $G$, each $f_i$ in competition with other firms solves the following optimization problems for computing its best response.
\begin{equation}
\begin{array}{lll}{\underset{q_{i}}{\operatorname{maximize}}} & {\pi_{i}\left(\boldsymbol{q}_{i}, \boldsymbol{q}_{-\boldsymbol{i}}\right)} & {} \\ {\text { subject to }} & {q_{i k} \geq 0} & {\text { for } m_k \in M_{i}} \\ {} & {q_{i k}=0} & {\text { for } m_k \notin M_{i}}\end{array}
\end{equation}
where $q_i$ and $q_{-i}$ denotes the vector of production quantities of $f_i$ and its competitors, respectively.

Bimpikis et al. \cite{shayan}, have focused on the equilibrium analysis of this model and their main result about the unique Nash equilibrium of this game is adopted as the foundation of this research.

\begin{theorem} \label{t:equil} [Adopted from Bimpikis et al. \cite{shayan}] The unique Nash equilibrium of the game is given by
$$q^* = [I+\gamma W]^{-1}\gamma \bar{\alpha},$$
where $\gamma = \frac{1}{2(c+\beta)}$, $\bar{\alpha}$ is a $|E| \times 1$ vector such that for every edge $(i,k)\in E$ we have $\bar{\alpha}_{ik}=\alpha_k$ and $W$ is an $|E|\times |E|$ matrix whose entries are
$$w_{i_{1} k_{1}, i_{2} k_{2}}=\left\{\begin{array}{l}{2 c \text { if } i_{1}=i_{2}, k_{1} \neq k_{2}} \\ {\beta \text { if } i_{1} \neq i_{2}, k_{1}=k_{2}} \\ {0 \text { otherwise }}\end{array}\right.$$

\end{theorem}

The matrix $[I+\gamma W]^{-1}$ is called the \textit{Leontief inverse}. We assume that the matrix $[I+\gamma W]$ is inversible. For a given realistic economy, this assumption is shown to be true \cite{sonis2000new,waugh1950inversion}. In this paper, we propose and formalize the problem of optimized governance of the afformentioned network market (networked cournot competition) with the objective of maximizing the social welfare. Social welfare ($SW$) in cournot competitions is defined as the sum of consumer surplus ($CS$) and firms' total profit. The consumer surplus in the Nash equilibrium is computed by the following formula (see \cite{hammond2002essential,shayan}):
\begin{equation}
CS =  \sum_{m_k \in M} \frac{\left(\alpha_{k}-P_{k}(q^*)\right)^{2}}{2 \beta}.
\end{equation}
Therefore the social welfare's formula is:
\begin{equation}
\begin{array}{ll}
SW  & =\sum_{f_i \in F}{\pi_i(q^*)} + CS \\
{ }  & = \sum_{f_i \in F}{[\sum_{m_k \in M_i}{q^*_{ik}\cdot P_k(q^*)}-C_i(q^*)]}\\
{ } & \hspace{0.5cm}+ \sum_{m_k \in M} 2/\beta \cdot \left(\alpha_{k}-P_{k}(q^*)\right)^{2}
\end{array}
\end{equation}

Now, assume that an additional node which is called the government and has access to all markets is added to the network. This node's target is to maximize the social welfare without concerning its own utility. It has been provided with a budget of $B$ and can use this budget to provide some shocks to each market. In this paper, each shock to market $m_k$ is defined as provisioning some goods ($\epsilon_k \leq q^t$) to this market alongside the competing firms. $q^t$ is a threshold that is forced by external entities such as law or social pressure. Firms compete until they reach an equilibrium. The equilibrium can be computed by the following theorem.

\begin{theorem} \label{equil2}
The unique Nash equilibrium of the game $\mathcal{G}$ in the presence of shocks $\{\epsilon_i\}_{i=1}^{m}$ is given by
$$q^{*}=[I+\gamma W]^{-1} \gamma(\bar{\alpha}-\overline{\beta \epsilon}),$$
where $W$ and $\overline{\alpha}$ are defined as in Theorem \ref{t:equil} and $\overline{\beta \epsilon}$ is a $|E| \times 1$ vector such that for every edge $(i,k)\in E$ we have $\bar{\beta \epsilon}_{ik}=\beta_k \cdot \epsilon_k$
\end{theorem}
\begin{proof}
In the presence of shocks we can rewrite the firms' utility functions:
$$
\begin{array}{ll}
\pi_i(q, \epsilon) & = \sum_{m_{k} \in M_{i}} q_{i k} \cdot P_{k}(q)-C_{i}(q) \\
{ } & = \sum_{m_k \in M_i}{q_{ik}[\alpha_k-\beta_k(\sum_{f_j\in F_k}{q_{jk}} + \epsilon_k)]} \\
{ } & \hspace{0.5cm} - c_i\cdot(\sum_{m_k\in M_i}{q_{ik}})^2 \\
{ } & = \sum_{m_k \in M_i}{q_{ik}[(\alpha_k-\beta_k\epsilon_k)+\beta_k\sum_{f_j\in F_k}{q_{jk}}]} \\
{ } & \hspace{0.5cm} - c_i\cdot(\sum_{m_k\in M_i}{q_{ik}})^2 \\
\end{array}.
$$

Assume that we have a new game $\mathcal{G'}$ where everything is the same as the previous setting ($\mathcal{G})$ except that the values of $\alpha_k$s have changed to $\alpha_k - \beta_k\epsilon_k$. By Theorem \ref{t:equil} , we will have the following formula for the Nash equilibrium point:
$$q^{*}=[I+\gamma W]^{-1} \gamma(\bar{\alpha}- \overline{\beta \epsilon})$$

Equilibria in $\mathcal{G}$ in the presence of shocks are equal to equilibria of $\mathcal{G'}$ because $\pi_i$s computed by the above formula is exactly what must be for $\mathcal{G'}$. So by following the method used in \cite{shayan} for proving Theorem \ref{t:equil}, our desired target will be achieved.

\end{proof}
Note that for each $m_k \in M$, we must have $\epsilon_k < \alpha / \beta$, because if not, the price function $P_k$ will be negative and it is not acceptable. Now we can write the formulation of social welfare. The $SW$ function in the presence of shocks can be recalculated as follows:

$$
\begin{array}{ll}
SW  & =\sum_{f_i \in F}{\pi_i(q^*,\epsilon)} + CS \\
{ }  & = \sum_{f_i \in F}{\big[\sum_{m_k \in M_i}{q^*_{ik}\cdot P_k(q^*, \epsilon)}-C_i(q^*)\big]}\\
{ } & \hspace{0.5cm}+ \sum_{m_k \in M} 2/\beta_k \cdot \big(\alpha_{k}-P_{k}(q^*,\epsilon)\big)^{2} \\
{ } & = \sum_{f_i \in F}\Big[\sum_{m_k \in M_{i}} q^*_{i k}\big(\alpha_{k}-\beta \sum_{f_j \in F_{k}} q^*_{j k}-\beta\epsilon\big) \\
{ } & \hspace{1.5cm} -c\big(\sum_{m_k \in M_{i}} q^*_{i k}\big)^{2}\Big]\\
{ } & \hspace{0.5cm} + \sum_{m_k \in M} 2/\beta \cdot \Big[\big(\beta\sum_{f_j \in F_k}{q^*_{jk}+\beta\epsilon}\big)^2\Big] \\
{ } & = \sum_{m_k \in M} \Big(\sum_{f_i \in F_{k}} q^*_{i k} \alpha_{k}\Big) \\
{ } & \hspace{0.5cm}-(\beta/2)\cdot \sum_{m_k\in M}\Big(\sum_{f_i \in F_{k}} q^*_{i k}\Big)^{2}\\
{ } & \hspace{0.5cm}-c \sum_{f_i\in F}\Big(\sum_{m_k \in M_{i}} q^*_{i k}\Big)^{2} \\
{ } & \hspace{0.5cm}-\sum_{m_k \in M}\Big((\beta/2)\cdot \epsilon_k^2+\sum_{f_i \in F_k}q^*_{ik}\epsilon_k \Big)
\end{array}
$$
Therefore, we have the following vectorized formula,
\begin{equation}\label{sw}
\begin{aligned}
SW  = {q^*}^T\overline{\alpha}-(\beta/2+c){q^*}^T q^*- (1/2){q^*}^TW q^*\\
-\overline{\beta \epsilon}^Tq^* - (\beta/2)\overline{\epsilon}^T\overline{\epsilon}, \hspace{3cm}
\end{aligned}
\end{equation}

where $\overline{\epsilon}$ is a $m\times 1$ vector whose $k$th component is equal to $\epsilon_k$ and other things are defined as before (see Theorem \ref{t:equil} and Theorem \ref{equil2}).
By the above formulation the problem of governing social welfare with market shocks can be modeled by the optimization problem described in Definition \ref{finalOPT}.

\begin{definition}  \label{finalOPT}
The problem of governing (maximizing) social welfare with shocks in a networked market $\mathcal{G}$ ($MaxSW(\mathcal{G})$) is defined as the following optimization problem:
\begin{equation*}
\begin{array}{ll@{}ll}
\text{Maximize}  & {q^*}^T\overline{\alpha}-(\beta/2+c){q^*}^T q^*- (1/2){q^*}^TW q^*&\\
{ }   &\hspace{0.5cm}-\overline{\beta \epsilon}^Tq^* - (\beta/2)\overline{\epsilon}^T\overline{\epsilon}& \\
\text{subject to}& \displaystyle  q^{*}=[I+\gamma W]^{-1} \gamma(\bar{\alpha}-\overline{\beta \epsilon})  & \\
                 &  \displaystyle  c\cdot(\sum_{m_k \in M} \epsilon_k)^2 \leq B  & { } \\
                 &  \displaystyle  0 \leq \epsilon_k \leq q^t  \hspace{2.5cm} \forall m_k \in M &\\
\end{array}
\end{equation*}
\end{definition}

All the elements of the sum depicted in the $SW$ formula are concave except $-\overline{\beta \epsilon}^Tq^* $ which makes the convex optimization frameworks unusable. In the next section, we devise a heuristic algorithm for this optimization problem. This is done by proposing a linear estimation for the social welfare and an optimization algorithm for maximizing it. Then in Section \ref{experiments}, by experimentation on real and synthetic data, the good performance of this heuristic algorithm is shown.

\section{Solution Estimation}
In this section, we provide some insights about the social welfare function and by linearizing it with Taylor expansion, we propose an algorithm called the \textit{Linear} heuristic for the $MaxSW(\mathcal{G})$ problem. More precisely in this section, we propose a metric that can be computed by the network structure and we analytically show that picking the markets with larger amounts of it can (approximately) maximize the social welfare. In the next section by running experiments on real and synthetic datasets, we will demonstrate the superiority of this metric over other metrics.

The main idea for this aim is to use the first order multivariate Taylor expansion \cite{konigsberger2013analysis} to create a linear approximation for the social welfare function. This approximation leads to a linear combination of $\epsilon_i$s:
$$SW(\epsilon) = SW(0) + \zeta_1 \epsilon_1+\zeta_2\epsilon_2+...+\zeta_m \epsilon_m.$$
Keeping in mind that the government has a limited budget for its interventions, we can consider the shocks small ($\forall_{m_k \in M}\epsilon_k \leq q^t$), so this approximation may be valid. The coefficient of each $\epsilon_i$ ($\zeta_i$) can be considered as the afformentioned metric. Since $SW$ is a differentiable function, we can write $SW$ as follows:
\begin{equation}
\begin{aligned}
SW(\epsilon) \approx SW(0)+\epsilon \cdot \nabla SW(0) \hspace{0.45cm}\\
= SW(0) + \sum_{r = 1}^m{\epsilon_r \frac{\partial SW}{\partial \epsilon_r}|_{\epsilon=0}}
\end{aligned}
\end{equation}
So, the amount of social welfare added by shocks is a linear combination of $\epsilon_r$s whose coefficients are $\zeta_r = \frac{\partial SW}{\partial \epsilon_r}|_{\epsilon=0}$. So to maximize the amount of social welfare, markets should be supplied in order of their $\zeta_r$s. The structure of this algorithm can be seen in Algorithm \ref{algo}. Here's how to calculate the coefficients.

Using Theorem \ref{equil2} and expanding the formula derived for $q^*$, we have:
\begin{equation}
\begin{aligned}
q_{i k}^{*}=\frac{\alpha_{k}-2 c \sum_{m_\ell \in M_{i}, m_\ell \neq m_k} q_{i \ell}^{*}-\beta \sum_{f_j \in F_{k}} q_{j k}^{*}}{2(\beta+c)}\\
\hspace{-0.6cm}=\frac{\alpha_{k}}{2(\beta+c)}-\sum_{(j,\ell) \in E\left(\mathcal{G}\right)}(\gamma W)_{i k, j \ell} q_{j \ell}^{*} \hspace{1.5cm}
\end{aligned}
\end{equation}

If we define function $f(z) = \gamma \alpha - \gamma z$,
\begin{equation}
q^*_{ij} = f(\sum_{k, \, l} w_{ij, k\ell} q^*_{k\ell} + \gamma \beta \epsilon_j)
\end{equation}
 denotes the amount firm $f_i$ supplies in market $m_j$ in equilibrium under the presence of shock $\epsilon_j$. Moreover, from Equation \ref{sw} with $h(x) = \alpha x - (\frac{\beta}{2} + c) x^2$ and $u(q_{ij}, q_{k\ell}) = w_{ij, k\ell} q_{ij} q_{k\ell}$,
 \begin{equation}
\begin{aligned}
SW = \sum_{i, \, j} h(q^*_{ij}) + \sum_{m_k \in M} h(\epsilon_k)\hspace{2cm}\\
 - \frac{1}{2} \sum_{i, \, j, \, k \, , \ell} u(q^*_{ij}, q^*_{k\ell}) - \beta \sum_{k=1}^{m} \epsilon_k \sum_j q^*_{jk}
\end{aligned}
\end{equation}
is the social welfare under the circumstances discussed so far.

We start our analysis by calculating $\frac{\partial q^*_{ij}}{\partial \epsilon_r}$. By the idea used in \cite{aliz},
\begin{equation}
\begin{aligned}
\frac{\partial q^*_{ij}}{\partial \epsilon_{r}}=f^{\prime}\left(\sum_{i, \, j, \, k \, , \ell} w_{ij, k\ell} q^*_{k\ell} + \gamma \beta \epsilon_{j}\right)\cdot \hspace{2cm}\\
\hspace{2cm} \left(\sum_{i, \, j, \, k \, , \ell} w_{ij, k\ell} \frac{\partial q^*_{k\ell}}{\partial \epsilon_{r}}+\gamma \beta \mathbf{1}\{r=j\}\right)
\end{aligned}
\end{equation}
Evaluating this equation using the matrix form at the point
 $\epsilon = (\epsilon_1,\cdots, \epsilon_{|E|}) = 0$, which is the absence of the government,
yields
\begin{equation}
\begin{aligned}
\frac{\partial q^*}{\partial \epsilon_r}|_{\epsilon=0} = -\gamma \beta (I + \gamma W)^{-1} e_r\text{,}
\end{aligned}
\end{equation}
where $e_r$ is a $|E| \times 1$ vector, with ones for edges connecting to market $m_r$ and zeros elsewhere. Thus, we have:

\begin{equation}
\begin{aligned}
\frac{\partial q^*_{ij}}{\partial \epsilon_r}|_{\epsilon=0} = - \gamma \beta \sum_{k} \lambda_{ij, kr}\text{ ,} \label{eq:1}
\end{aligned}
\end{equation}
where $\lambda_{ij, kr}$ is the corresponding element to edges $ij$ and $kr$ of matrix $(I + \gamma W)^{-1}$.

Setting our sights on social welfare, we have:

\begin{equation}
\begin{aligned}
\frac{\partial \text{ SW}}{\partial \epsilon_{r}}= \sum_{i, j} h^{\prime}\left(q^*_{ij}\right) \frac{\partial q^*_{ij}}{\partial \epsilon_{r}}  + \alpha - (\beta + 2c) \epsilon_r \hspace{1.6cm} \\
- \frac{1}{2}\sum_{i, j, k, \ell} \left[\frac{\partial u}{\partial q^*_{ij}} \frac{\partial q^*_{ij}}{\partial \epsilon_r} + \frac{\partial u}{\partial q_{k\ell}} \frac{\partial q^*_{k\ell}}{\partial \epsilon_r}\right] - \beta \sum_k \epsilon_k \sum_j \frac{\partial q^*_{jk}}{\partial \epsilon_r}.
\end{aligned}
\end{equation}

Considering $h^\prime(x) = \alpha - (\beta + 2c)x$ and $\frac{\partial u(q_{ij}, q_{k\ell})}{\partial q_{ij}} = w_{ij, k\ell} q_{k\ell}$, we get:

\begin{equation} \label{eq:2}
\begin{aligned}
\frac{\partial \text{ SW}}{\partial \epsilon_{r}}= \sum_{i,j} (\alpha - (\beta + 2c) q^*_{ij}) \frac{\partial q^*_{ij}}{\partial \epsilon_{r}} +\hspace{2cm}  \\
 - \frac{1}{2}\sum_{i, j, k, \ell} \left[w_{ij, k\ell} q^*_{k\ell} \frac{\partial q^*_{ij}}{\partial \epsilon_r} + w_{ij, k\ell} q^*_{ij} \frac{\partial q^*_{k\ell}}{\partial \epsilon_r}\right] \\
 - \beta \sum_k \epsilon_k \sum_j \frac{\partial q^*_{jk}}{\partial \epsilon_r}+ \alpha - (\beta + 2c) \epsilon_r) \hspace{0.6cm}
\end{aligned}
\end{equation}
Thus, we evaluate equation \eqref{eq:2} at $\epsilon = 0$:

\begin{equation}\label{eq:3}
\begin{aligned}
\frac{\partial \text{ SW}}{\partial \epsilon_{r}}|_{\epsilon=0} = \sum_{i,j} (\alpha - (\beta + 2c) q^*_{ij}|_{\epsilon=0}) \frac{\partial q^*_{ij}}{\partial \epsilon_{r}}|_{\epsilon=0} \\
 - \frac{1}{2}\sum_{i, j, k, \ell} \Big[w_{ij, k\ell} q^*_{k\ell}|_{\epsilon=0} \frac{\partial q^*_{ij}}{\partial \epsilon_r}|_{\epsilon=0} \hspace{0.5cm}\\+ w_{ij, k\ell} q^*_{ij}|_{\epsilon=0} \frac{\partial q^*_{k\ell}}{\partial \epsilon_r}|_{\epsilon=0}\Big] + \alpha ) \hspace{0.8cm}
\end{aligned}
\end{equation}

$q^*_{ij} |_{\epsilon=0}$ has been studied in \cite{shayan}. Based on their results, we can deduce the following in our setting:

\begin{equation}
\begin{aligned}
q^*_{ij} |_{\epsilon=0} = \gamma \alpha \sum_{k\ell} \lambda_{ij, k\ell}\text{ .}\label{eq:5}
\end{aligned}
\end{equation}

Using equation \eqref{eq:1} and \eqref{eq:5}, we get:

\begin{equation}
\begin{aligned}
\frac{\partial \text{ SW}}{\partial \epsilon_{r}}|_{\epsilon=0}= -\gamma \beta\sum_{ij} (\alpha - \gamma \alpha(\beta + 2c) \sum_{k\ell} \lambda_{ij, k\ell}) \sum_{k} \lambda_{ij, kr} - \\ \sum_{i,j} (\gamma \alpha \sum_{k\ell} \lambda_{ij, k\ell} (\sum_{k\ell} w_{ij, k\ell} \sum_{t} \gamma \beta \lambda_{k\ell, tr})) + \alpha \label{eq:6}
\end{aligned}
\end{equation}

Since we have derived a formula for computing $\zeta_r = \frac{\partial SW}{\partial \epsilon_r}|_{\epsilon=0}$s, we can state the final algorithm. This algorithm is shown in Algorithm \ref{algo}. In the first four lines of this algorithm $\zeta_r$s are computed from the network structure and Leontief matrix. After that a set $T$ is initialized to the set of all markets and a variable $S$ is initialized to 0. In the next while loop, $T$ is to be the set of markets that have not been supplied with shocks so far and $S$ is defined as the total goods supplied by the government. So the loop execution will continue until either all markets are supplied with shocks or the cost of shock supplies exceeds the budget intended for this purpose ($B$).

In each iteration of the while loop, the market with maximum $\zeta_r$ is chosen from $T$ and extracted from this set. Then the maximum possible shock is computed as $\epsilon_r$ and is added to $S$. Note that for computing $\epsilon_r$, three upper bounds must be considered:
\begin{enumerate}
\item $q^t$ is the upper bound defined in Definition \ref{finalOPT}.
\item $\frac{\beta}{\alpha}$ is the upper bound defined by the price function. If $\epsilon_r > \frac{\beta}{\alpha}$, the price will be negative at that market and it is acceptable.
\item $\sqrt{\frac{B}{c_r}}-S$ is the amount of goods that can be provided by the remaining budget.
\end{enumerate}

\begin{algorithm*}
\DontPrintSemicolon
\KwIn{A network market $\mathcal{G}$ alongside with parameters $\alpha$, $\beta$ and $\gamma$}
\KwOut{The amount of shocks $\epsilon_1$, $\epsilon_2$, ..., $\epsilon_m$ which makes the maximum social welfare}
\;

Set $\lambda_{ij,kr}$ equal to the corresponding elements to edges $ij$ and $kr$ of matrix $(I+\gamma W)^{-1}$\;
\For{$r \gets 1$ \textbf{to} $m$} {
   $\zeta_r \gets -\gamma \beta\sum_{ij} (\alpha - \gamma \alpha(\beta + 2c) \sum_{k\ell} \lambda_{ij, k\ell}) \sum_{k} \lambda_{ij, kr} -  \sum_{i,j} (\gamma \alpha \sum_{k\ell} \lambda_{ij, k\ell} (\sum_{k\ell} w_{ij, k\ell} \sum_{t} \gamma \beta \lambda_{k\ell, tr})) + \alpha$
}
$T \gets M$
$S \gets 0$\;
\While{$T \neq \emptyset$ and $c\cdot S^2 < B$}{
Set $r$ to the index of the market $m_r \in T$ with maximum $\zeta_r$ \;
$T \gets T \setminus m_r$ \;
$\epsilon_r \gets \min\{q^t, \frac{\beta_r}{\alpha_r}, \sqrt{\frac{B}{c_r}}-S \}$\;
$S \gets S + \epsilon_r$
}
\Return{$\epsilon_r$s} \;
\caption{The Linear Heuristic for solving $MaxSW(\mathcal{G})$ }
\label{algo}
\end{algorithm*}

\section{Empirical Study} \label{experiments}

We evaluate the performance of our proposed measure and method on the synthetic data and a real-world dataset of different pharmaceutical companies as our firms and different markets for drugs. For example, Aspirin and its users define a market in which players are companies that produce this drug. We collect this dataset from different 135 drug companies that produce 603 drugs altogether. Additionally, we use identical parameters $\alpha, \beta, c$ for all the firms and markets, as we are considering the symmetric case. These parameters are set in a way to be close to real-life values. The synthetic data also has 603 markets and 135 firms, which has been chosen randomly. The characteristics of this dataset are shown in Table \ref{dataset}. A subgraph of this network is shown in Figure \ref{subgraph}.
\begin{figure}[h]
\centering
\includegraphics[width=0.3\textwidth]{graph2.png}
\caption{A Subgraph of the Drug Company Dataset}
\label{subgraph}
\end{figure}

\begin{table} \centering
\caption{Summary of Dataset's Characteristics}
\begin{tabular}{ |p{4cm}|p{2cm}|  }
\hline
 \multicolumn{2}{|c|}{Drug Companies Dataset} \\
 \hline
Characteristic& Value \\
 \hline
 \#Markets   & 603    \\
 \#Firms&   135  \\
 \#Firm-Market pairs (edges) & 2049 \\
 \hline
\end{tabular}
\label{dataset}
\end{table}

\subsection{Competitor Benchmark}

The essence of competitors we consider is that the government takes on a measure to rank the markets. Next, it supplies goods to markets in that order, as much as possible and as long as permissible. Naively, it is possible to choose the markets at random. No measure, to the best of our knowledge, has been presented for picking the markets yet. Nevertheless, centrality measures are natural candidates for us to use as benchmarks. As for the centrality measures we consider, we use the followings:

\begin{itemize}

\item \textbf{Degree.}
The simplest centrality measure is the degree of a node, which in our model, is the number of firms competing in a market:
$$
d(m_i) = |F_i|.
$$

\item \textbf{Betweenness.}
Generally speaking, betweenness centrality is a quantity for determining the impact of a node over the flow of information in a graph \cite{brandes2001faster}. The betweenness of a node is an indicator for the fraction of shortest paths in a graph that pass through this vertex. In our setting:

$$
b(m_i)=\sum_{f_j, f_k \in F} \frac{\sigma_{j k}(m_i)}{\sigma_{j k}} ,
$$
where $\sigma_{j k}$ is the total number of shortest paths from firm $f_j$ to firm $f_k$ and $\sigma_{j k}(m_i)$ is the total number of those paths that include market $m_i$.

\item \textbf{Closeness.}
Closeness centrality is an aggregate measure of a node's proximity to other nodes. More precisely, closeness of node $v$ is defined as the inverse of sum of distances of node $v$ from other nodes. Considering our model:

$$
cl(m_i) = \sum_{f_j\in F} \frac{1}{dist(m_i, f_j)} ,
$$
where $dist(m_i, f_j)$ is the distance between market $m_i$ and firm $f_j$ in the graph.

\end{itemize}

Regardless of the measure one picks, it is possible to adopt the ascending or the descending order. Thus, we consider both choices, however, the ascending order empirically shows better performance with these benchmark centrality measures. In conclusion, we present our studied strategies in Table \ref{heuristics}.

\begin{table}\centering
\caption{Summary of proposed algorithms in the competitor benchmark}
\begin{tabular}{@{}cccl@{}}\toprule
& \multicolumn{1}{c}{Heuristic} & \phantom{abc} & \multicolumn{1}{c}{Description}\\ \midrule
& $Linear$ && Descending order of $\zeta_i$\\
& $AscDeg$ && Ascending order of $d(m_i)$\\
& $DescDeg$ && Descending order of $d(m_i)$\\
& $AscBet$ && Ascending order of $b(m_i)$\\
& $DescBet$ && Descending order of $b(m_i)$\\
& $AscCL$ && Ascending order of $cl(m_i)$\\
& $DescCL$ && Descending order of $cl(m_i)$\\
& $Random$ && Random order of $m_i$\\
 \bottomrule
\end{tabular}
\label{heuristics}
\end{table}

After having our graph, we use Theorem \ref{equil2} to calculate the equilibrium of the game with our parameters $\alpha$, $\beta$, and $c$. Subsequently, we pick a policy $A$ for governance of social welfare from Table \ref{heuristics}. Then, the government begins supplying the amount $q^t$ of the commodity into the markets in the corresponding order, until the supplies violate the constraints in Definition \ref{finalOPT}. Thus, the government would supply up to $\left\lfloor \sqrt{\frac{B}{C}} \right\rfloor$, where $B$ is the budget that innates to the $MaxSW(\mathcal{G})$ problem. Altering $B$ gives us a trajectory for social welfare. Let $SW_{A}(B)$ be the social welfare obtained by applying strategy $A$ on $MaxSW(\mathcal{G})$ with parameter $B$. In the next subsection, we compare trajectories $SW_{A}(B)$ for policies in Table \ref{heuristics}.

\subsection{General performance}

Our empirical results are indicated in Figures \ref{f1}, \ref{f2}, \ref{f3}, \ref{f4}, \ref{f5} and \ref{f6}. For each policy $A$ of Table \ref{heuristics}, we plot the difference between the amount of social welfare which can be obtained by our Linear algorithm and the social welfare which can be obtained by the heuristic $A$, i.e. $SW_{Linear}(B) - SW_{A}(B)$.

We observe that our proposed measure is strictly better than other mentioned quantities. For the random case, we use the average results over 50 different realizations to extract the expected performance. It is good to note that picking the markets according to ascending order of a centrality measure seems to be better than the reverse order. This is intuitive, since markets with lower centralities are generally more monopolized and government's interventions have more impact on them. This observation is in accordance with the general belief in economics that higher competition leads to higher social welfare \cite{}. In addition, the difference in social welfare obtained by the Linear heuristics and other methods tend to rise, until a certain point at which drops. Since the end point of the plots suggests the government to supply in almost all markets by each method, the last points have $y$ coordinates close to zero. All the plots are strictly above the horizontal line $y = 0$, except beginning points which indicates the superiority of our proposed approach over other mentioned strategies.

\begin{figure} \centering
   \includegraphics[scale=0.13]{asc.png}
   \caption{The difference between the social welfare obtained by the Linear heuristic and competitor structural heuristics with ascending order in the dataset of drug companies}
   \label{f1}
\end{figure}
\begin{figure} \centering
   \includegraphics[scale=0.13]{dsc.png}
   \caption{The difference between the social welfare obtained by the Linear heuristic and  competitor structural heuristics with descending order in the dataset of drug companies}
   \label{f2}
\end{figure}
\begin{figure} \centering
   \includegraphics[scale=0.13]{rand.png}
   \caption{The difference between the social welfare obtained by the Linear heuristic and the random heuristic in the dataset of drug companies}
   \label{f3}
\end{figure}
\begin{figure} \centering
   \includegraphics[scale=0.13]{asc2.png}
   \caption{The difference between the social welfare obtained by the Linear heuristic and competitor structural heuristics with ascending order in the synthetic dataset}
   \label{f4}
\end{figure}
\begin{figure} \centering
   \includegraphics[scale=0.13]{dsc2.png}
   \caption{The difference between the social welfare obtained by the Linear heuristic and  competitor structural heuristics with descending order in the synthetic dataset}
   \label{f5}
\end{figure}
\begin{figure} \centering
   \includegraphics[scale=0.13]{rand2.png}
   \caption{The difference between the social welfare obtained by the Linear heuristic and the random heuristic in the synthetic dataset}
   \label{f6}
\end{figure}

\clearpage

\bibliographystyle{unsrt}


\section{Introduction}

Space-time trade-offs are a widely observed phenomenon in data structure complexity.
In this work, we are interested in trade-offs between offline preprocessing advice length and online running time in inverting random functions, namely, the trade-off between the size $S$  (in the number of bits) of pre-computed data structure (or advice) on the function (but not the image that we wish to invert) and the algorithm's running time $T$ for computing the inverse of a certain image.
Such trade-offs give lower bound for algorithms that inverts cryptographic functions without taking the specific structure of that family of functions.

Without pre-computed advice ($S = 0$), classical computers require $T = \Omega(\eps N)$ for inverting a random image for a random function $f: [N] \mapsto [N]$ with probability $\eps$, and quantum computers require $T = \Omega(\sqrt{\eps N})$ \cite{ambainis2002quantum} to do so.
Both bounds are asymptotically tight, since we observe that exhaustive search and Grover's algorithm~\cite{grover1996fast} on input range $[\eps N]$ inverts an $\eps$ fraction of inputs, respectively.
However, if we allow some pre-computed advice, classical computers can do much better.
Hellman \cite{hellman1980cryptanalytic} showed that every function can be inverted with $S = T = \tilde O(N^{2/3})$ and every permutation can be inverted using only $S = T = \tilde O(N^{1/2})$.
However, it is not known whether we can do better than Grover's algorithm or Hellman's algorithm, even if we allow quantum computers to come into play.
Therefore motivated by post-quantum cryptanalysis, it is natural to ask whether these two algorithms are indeed the best that we can do.

\subsection{The reduction}

Now we proceed to construct an encoding scheme given an inverter.
Given a permutation inverter $(\alpha, \mathcal A)$ that inverts an $\eps$ fraction of the input.
Let $\eps' = \eps / 2$.
By how we defined success probability, we can show that there exists a large subset $X$ of all the permutations $S_N$ with size at least $\eps' N!$, such that for any permutation $\pi \in X$, we have that
\begin{equation*}
    \Prob{y}[(\alpha, \mathcal A) \textnormal{ inverts $y$ for $\pi$}] \ge \eps'.
\end{equation*}

Consider a permutation $\pi \in X$, and let $I$ be the set of indices $x \in [N]$ such that $\mathcal A$ inverts $f(x)$. Recall that by the definition of $X$, we have $|I| \ge \eps' N$.
We use the shared randomness in the way such that we sample a subset $R \subseteq [N]$ with each element of $[N]$ independently chosen to be in $R$ with probability $\gamma/T^2$, where $\gamma \in (0, 1)$ is some constant that we will decide later.

Let $G$ be a subset of $I$, where an element $x \in G$ if it satisfies the following two conditions,
\begin{enumerate}
    \Item \begin{equation}
        \label{inverter-condition-1}
        x \in R;
    \end{equation}
    \item The total query magnitude on $R \setminus \{x\}$ while running $\mathcal A^{\pi}(\alpha, \pi(x))$ is bounded by $c/T$ for some constant $c$, that is,
    \begin{equation}
        \label{inverter-condition-2}
        \sum_{z\in R\setminus\{x\}}{q_z(x)}\le \frac c T.
    \end{equation}
\end{enumerate}

\begin{claim}
    With probability at least 0.8 over the choice of $R$, $|G| = \Omega(\eps N/T^2)$.
\end{claim}
\begin{proof}
    Let $H = R \cap I$.
    Due to the definition of $R$, $|H|$ is distributed according to a binomial distribution.
    Therefore, the expected value of $|H|$ is $|I| \gamma/T^2$.
    By the multiplicative Chernoff bound and \eqref{eq-nondegenerate-T},
    \begin{equation}
        \label{eq-size-H}
        \Prob{R}\left[|H| \ge \frac{|I|\gamma}{2T^2}\right] \ge 0.9
    \end{equation}
    for all sufficiently large $N$.

    By definition, each query that $\mathcal A$ makes is of unit length.
    Since $\mathcal A$ makes at most $T$ queries, by \Cref{def-total-query-magnitude},
    \begin{equation*}
        \sum_{z \in [N]} q_z(x) \le T.
    \end{equation*}
    By linearity of expectation,
    \begin{equation*}
        \Epc{R}\left[\sum_{z \in R \setminus \{x\}}q_z(x) \right]
            = \sum_{z \in [N] \setminus \{x\}} \frac \gamma {T^2} q_z(x)
            \le \frac \gamma{T^2} T
            = \frac \gamma T.
    \end{equation*}
    Hence, by Markov's inequality,
    \begin{equation}
        \label{eq-prob-J}
        \Prob{R}\left[\sum_{z \in R \setminus \{x\}}q_z(x) \ge \frac c T \right] \le \frac T c \cdot \frac \gamma T = \frac \gamma c.
    \end{equation}
    Let $J$ denote the subset of $x \in I$ that satisfy \eqref{inverter-condition-1} but not \eqref{inverter-condition-2}.
    Note that \eqref{inverter-condition-1} and \eqref{inverter-condition-2} are independent for each $x \in I$, since \eqref{inverter-condition-1} is whether $x \in R$ and \eqref{inverter-condition-2} only concerns the intersection of $R$ and $[N] \setminus \{x\}$.
    Therefore by \eqref{eq-prob-J}, the probability that $x \in I$ satisfies $x \in J$ is at most $\gamma^2/(cT^2)$.
    Hence, by Markov's inequality,
    \begin{equation}
        \label{eq-size-J}
        \Prob{R}\left[|J| \le \frac{10|I|\gamma^2}{cT^2}\right] \ge 0.9.
    \end{equation}
    From \eqref{eq-size-H} and \eqref{eq-size-J}, we get that with probability at least 0.8 over the choice of $R$,
    \begin{equation*}
        |G| = |H| - |J|
            \ge \frac{|I|\gamma}{2T^2} - \frac{10|I|\gamma^2}{cT^2}
            \ge \frac{\eps'\gamma N}{2T^2} \left(1 - \frac{5 \gamma^2} c \right)
            = \Omega\left(\frac{\eps N}{T^2}\right),
    \end{equation*}
    given that $\gamma$ is a small enough positive constant.
\end{proof}

We now proceed to describe the QRAC-VL scheme for encoding $\pi^{-1}$.
If $\pi \not\in X$ or $|G|$ is smaller than $O(\eps N/T^2)$, the encoding simply sets a (classical) flag (which takes one bit) and stores the entire permutation table of $\pi^{-1}$ (we will denote this as case A).
In this case, it is straightforward to construct a decoder that succeeds with probability 1.

Otherwise assuming $G$ is large enough, we clear the first flag, and proceed with our QRAC-VL that computes (if necessary) and outputs the following information $\beta$ as our encoding: (which we will denote as case B)
\begin{itemize}
    \item The size of $G$, encoded using $\log N$ bits;
    \item The set $G \subseteq R$, encoded using $\log \binom{|R|}{|G|}$ bits;
    \item The permutation $\pi$ restricted to input outside of $G$, encoded using $\log (N!/|G|!)$ bits;
    \item Quantum advice used by the algorithm repeated $\rho$ times $\alpha^{\bigotimes \rho}$, for some $\rho$ that we will decide later.
        (We can compute this as the encoder can preprocess multiple copies of the same advice. Note that this is the only part of our encoding that is not classical.)
\end{itemize}

Upon given the encoding $\beta$, some image $y \in [N]$, and the algorithm's randomness $R$, the decoder first proceeds to recover set $G$ and $\pi(x)$ for every $x \not\in G$.
If the given $y = \pi(x)$ for some $x \not\in G$, the decoder outputs $x = \pi^{-1}(y)$.
Otherwise, the decoder constructs $\pi'$ to be
\begin{equation*}
    \pi'(x) = \begin{cases}
        y, & x \in G; \\
        \pi(x), & x \not\in G.
    \end{cases}
\end{equation*}
Then the decoder extracts $\alpha_1, \alpha_2, ..., \alpha_\rho$, and invokes $\mathcal A^{\pi'}(\alpha_i, y)$ for each $i \in [\rho]$ and outputs their majority vote.
Let $\ket{\phi_\pi}$ and $\ket{\phi_{\pi'}}$ denote the final states of $\mathcal A$ when it is given the oracle $\pi$ and $\pi'$ respectively.
Then by \Cref{swapping-lemma} and the definition of $G$,
\begin{equation*}
    \| \ket{\phi_\pi} - \ket{\phi_{\pi'}} \|
        \le \sqrt{T\sum_{z \in R \setminus \{x\}}{q_z(x)}}
        \le \sqrt{T \cdot \frac c T}
        = \sqrt c.
\end{equation*}
As $x \in I$, by the definition of $I$, measuring $\ket{\phi_\pi}$ gives $x$ with probability at least $2/3$.
Given $c$ is a small enough positive constant, measuring $\ket{\phi_{\pi'}}$ will also give $x$ with probability at least $0.6$.

We now examine the length of our encoding.
With probability $1 - \eps'$, we have $\pi \not\in X$;
    with probability $\eps' \cdot (1 - 0.8)$, we have $\pi \in X$ but $G$ is small.
Therefore, over all, with probability $1 - 0.6 \eps$, our encoding will take case A, where the encoding consists of $1 + \log N!$ classical bits and decoder succeeds with probability 1.

With probability $0.4 \eps$, our encoding takes case B, and the size of the encoding will be
\begin{align*}
    1 + \log N + \log \binom{|R|}{|G|} + \log (N!/|G|!) + \rho S.
\end{align*}
By \eqref{eq-nondegenerate-T}, $\log \binom{|R|}{|G|} = O(|G| \log(|R|/|G|)) = O(|G| \log 1/\eps) = o(|G| \log |G|)$, and we can rewrite the size of the encoding as
\begin{align*}
    \rho S - \log |G|! + \log N! + o(\log |G|!).
\end{align*}
In this case, when the decoder is queried a point inside what she has remembered, that is $y \not\in \pi(G)$ (which occurs with probability $1 - |G|/N$), she recovers the correct pre-image with probability 1;
    otherwise, with one copy of the advice, she recovers the correct pre-image with probability 0.6, therefore with $\rho$ copies, by Chernoff's bound, she recovers the correct pre-image using majority vote, with probability $1 - \exp(-\Omega(\rho))$.

Overall, the average encoding length is at most $1/2 \cdot (\eps \rho S + |G| H(\eps) - \eps \log |G|! + \eps \log N) + \log N!$, and the average success probability is $1 - |G|/N \cdot \exp(-\Omega(\rho))$.
By setting $\rho = \Omega(\log(N/\eps)) = \Omega(\log N)$, the average success probability\footnote{Technically, we proved that the average success probability will be at least this much. However, as the success probability is monotone in encoding length, it is not hard to see that we can still use \Cref{theorem-qrac-vl-permutation}.} will be $1 - O(\eps/N)$
By \eqref{eq-nondegenerate-eps} and \Cref{theorem-qrac-vl-permutation}, we have
\begin{equation*}
    \log N! + 1/2 \cdot (\eps \log |G|! - \eps \rho S - o(\eps \log |G|!) - \eps \log N) \ge \log N! - O(\log N).
\end{equation*}
Given \eqref{eq-nondegenerate-T}, \eqref{eq-nondegenerate-S}, i.e. $S, T$ satisfy some non-trivial conditions, we can simplify the expression above and obtain
\begin{equation*}
    \log |G|! + o(\log |G|!) \ge \Omega(S \log N).
\end{equation*}
As we are conditioning on the event that $G$ is large, plugging in the lower bound on $|G|$, we obtain that $ST^2 \ge \tilde\Omega(\eps N)$.

\section{Preliminaries}

\input{pre}

\input{qrac}

\section{Proof of \texorpdfstring{\Cref{permutations}}{Theorem for Permutations}}
\input{main_result}

\section{Proof of \texorpdfstring{\Cref{functions}}{Theorem for Functions}}
\input{functions}

\section{Open Questions}

Our work still does not answer whether there exists a tighter asymptotic lower bound like $ST + T^2 \ge \eps N$, nor whether there exists an attack using quantum advice that achieves $ST^2 = \eps N$.

On the other hand, it seems hard to generalize our techniques to handle random functions where $M \gg N$.
Say $M = N^2$.
It turns out that for whatever choice of $G \subseteq R$, remembering where $G$ is, and $f$ for points outside of $G$ is already too much (requires number of bits greater than $M \log N$).
Recall that $|R| \propto M/T^2$, but if we only remember one pre-image per image, $|G| \le N$.
Therefore under these parameters, $\log \binom{|R|}{|G|} \ge |G| \log N > |G| \log |G|$ and we will lose the non-trivial savings we get from the reduction.
Therefore, a natural direction would be to prove any meaningful lower bound for random function inversion under the regime where $M \gg N$.

\iflipics\else
\section*{Acknowledgements}

The authors would like to thank Nai-Hui Chia, Luca Trevisan, Xiaodi Wu, and Penghui Yao for their helpful insights during the discussions. We also thank the anonymous reviewers at QIP and ITC for pointing out various issues in the paper.
\fi

\section{Quantum Random Access Codes with Variable Length}
\label{sec:qrac-vl}

Intuitively, quantum random access code looks at the following problem:
\begin{itemize}
    \item A random function $f: [N] \mapsto X_N$ is sampled from an \textit{arbitrary} distribution.
    \item At the offline phase, an unbounded algorithm gets access to the entire function and produces a quantum state $\ket\alpha$ of bounded size $\ell$ (therefore dimension at most $2^\ell$).
    \item At the online phase, a uniformly random challenge $x \in [N]$ is generated, and the algorithm given $\ket\alpha$ and $x$ is asked to recover $f(x)$ with probability $\delta$.
\end{itemize}

In this section, we want to prove that there is a trade-off between the expected encoding size $L := \Epc{f}[\ell]$ and the success probability $\delta$.
This is a generalization of QRAC considered in previous works like~\cite{ambainis1999dense} since we can view their QRAC equivalent to ours by making the following restrictions:
\begin{enumerate}
    \item $X_N = \{0, 1\}$.
    \item The function distribution is always the uniform distribution.
    \item The quantum state length $\ell$ is fixed parameter that does not depend on the specific function $f$.
\end{enumerate}

We formalize the problem above as quantum random access code with variable length, as given by the definition below.

\begin{definition}
Let $F_N$ be a set of functions $f: [N] \to X_N$ for some finite set $X_N$.
A quantum random access code with variable length (QRAC-VL) for $F_N$ consists of two algorithms $(\textnormal{Enc}, \textnormal{Dec})$.
\begin{enumerate}
    \item $\textnormal{Enc}: F_N \times \mathcal{R} \to \mathbb{C}^*$. The encoding algorithm encodes a function $f \in F_N$ with some fresh independent randomness in $\mathcal{R}$ to some qubits. The number of qubits denoted by $\ell = \ell(f)$ can depend on the function $f$.
    \item $\textnormal{Dec}: \mathbb{C}^* \times [N] \times \mathcal{R} \to X_N$. The decoding algorithm compute $f(x)$ on some specific element $x \in [N]$ with the encoded message in $\mathbb{C}^{2^\ell}$, and it uses the same shared randomness for the encoding algorithm.
\end{enumerate}

The performance of the code is measured by two parameters $L$ and $\delta$.
We define
\begin{equation*}
    L := \Epc{f}[\ell(f)]
\end{equation*}
to be the average length of the coding scheme over uniform distribution on $f \in F_N$, and
\begin{equation*}
    \delta := \Prob{f, x, R}[\textnormal{Dec}(\textnormal{Enc}(f; R), x; R) = f(x)]
\end{equation*}
to be the probability that our scheme correctly reconstructs the image of the function, where the probability is taken over uniform distribution on $f \in F_N$, $x \in [N]$, and the scheme's internal randomness.
\end{definition}

First, we prove a helpful lemma that says conditional quantum entropy satisfies subadditivity.

\begin{lemma}
    \label{conditional-entropy-subadditivity-lemma}
	Let $X = (X_1, ..., X_N), Q$ be some quantum states, then
    \begin{equation*}
        \sum_{i = 1}^N S(X_i | Q) \ge S(X | Q).
    \end{equation*}
\end{lemma}
\begin{proof}
We will prove this for $N = 2$ and it is easy to extend this proof to any $N$ using an inductive argument by showing that
$$\sum_{i = 1}^{N - 1} S(X_i | Q) + S(X_N | Q) \ge S(X_1 ... X_{N - 1} | Q) + S(X_N | Q) \ge S(X | Q).$$

For $N = 2$, by the definition of conditional entropy, it is equivalent to prove $S(X_1 Q) + S(X_2 Q) \ge S(X_1 X_2 Q) + S(Q)$, which holds due to strong subadditivity of von Neumann entropy.
\end{proof}

\begin{theorem}(Lower bound for QRAC-VL)
\label{theorem-qrac-vl}
For any QRAC-VL, let $X = (X_1, \dots, X_N)$ be a random variable sampled uniformly random from the distribution (of truth tables) of functions $F_N$.
Therefore, $S(X)$ is the (von Neumann) entropy of a uniformly random distribution of $F_N$ and $S(X_J)$ is the average (or expected) entropy of a single element.
We have that for all sufficiently large $N$,
\begin{equation*}
L \ge S(X) - N \cdot (H(\delta) + (1 - \delta) \cdot S(X_J)),
\end{equation*}
where $H(x) := -x \log_2 x - (1 - x) \log_2 (1 - x)$ is the binary entropy function.
\end{theorem}
\begin{proof}
    Sample $R$ independently.
    Let $Q = \textnormal{Enc}(X; R)$ be the encoding.
    Using the fact in conditional mutual information that $I(Q, R; X) = I(Q; X | R) + I(X; R)$ and the fact that $X$ and $R$ are independent classical random variables,
    \begin{equation}
        \label{eq-qrac-vc-1}
        I(Q, R; X) = I(Q; X | R) \le S(Q | R).
    \end{equation}
    Since $R$ is classical, by \Cref{quantum-source-coding-theorem},
    \begin{equation}
        \label{eq-qrac-vc-2}
        S(Q | R) \le S(Q) \le L.
    \end{equation}

    On the other hand, using \Cref{conditional-entropy-subadditivity-lemma},
    \begin{align}
        \label{eq-qrac-vc-3}
        \begin{split}
		    I(Q, R; X)
    		    &= S(X) - S(X | Q, R) \\
    			&\ge S(X) - \sum_{i=1}^N S(X_i | Q, R) \\
                &= S(X) - N \cdot S(X_J | Q, R, J),
        \end{split}
    \end{align}
    By data processing inequality, we know that
    \begin{align}
    \begin{split}
        \label{eq-qrac-vc-4}
        S(X_J | Q, R, J) \le S(X_J | \textnormal{Dec}(Q, J; R)).
    \end{split}
    \end{align}
    Note that $X_J, \textnormal{Dec}(Q, J; R)$ are both classical random variables.
    Let $I$ be the indicator variable that indicates whether $X_J = \textnormal{Dec}(Q, J; R)$.
    By definition of success probability in quantum random access code, we can show that
    \begin{align}
        \label{eq-qrac-vc-5}
        \begin{split}
            S(X_J | \textnormal{Dec}(Q, J; R))
                &= S(X_J, I | \textnormal{Dec}(Q, J; R)) - S(I | X_J, \textnormal{Dec}(Q, J; R)) \\
                &= S(I | \textnormal{Dec}(Q, J; R)) + S(X_J | I, \textnormal{Dec}(Q, J; R)) - 0 \\
                &\le S(I) + \delta \cdot 0 + (1 - \delta) \cdot S(X_J) \\
                &= H(\delta) + (1 - \delta) S(X_J).
        \end{split}
    \end{align}

    Combining \eqref{eq-qrac-vc-1}, \eqref{eq-qrac-vc-2}, \eqref{eq-qrac-vc-3}, \eqref{eq-qrac-vc-4}, and \eqref{eq-qrac-vc-5}, we get the expected equation in the theorem.
\end{proof}

To see an immediate application of this theorem, we will demonstrate proving a bound for QRAC-VL for permutations.
For permutations, $S(X) = \log N!$ and $S(X_J) = \log N$.
Combining the theorem above with the following algebraic fact, we can prove a lower bound for QRAC-VL for permutations.

\begin{fact}
    $H(1 - \delta) = H(\delta) \le \delta \cdot \log(e/\delta).$
\end{fact}

\begin{corollary}
\label{theorem-qrac-vl-permutation}
For any QRAC-VL for permutations $S_N$ with $\delta = 1 - k/N$ for any $k = \Omega(1/N)$, we have
\begin{equation*}
L \ge \log N! - O(k \log N).
\end{equation*}
\end{corollary}

\subsection{Our Contributions}

In this work, we resolve this discrepancy by showing that $ST^2 = \tilde\Omega(\eps N)$ is still required even if the inverter is allowed to use quantum advice.
Formally,
\begin{definition}
A function (or permutation) inverter is a pair $(\alpha, \mathcal A)$, where:
\begin{enumerate}
    \item $\alpha = \alpha(f)$ is a pre-computed quantum advice of $S$ qubits, which can depend on the function $f: [M] \mapsto [N]$; (for permutations, $M = N$)
    \item $\mathcal A$ is a quantum oracle algorithm that takes advice $\alpha$ and an image $y \in [N]$, makes at most $T$ quantum queries to the function as an oracle $O_f$, and outputs a supposed pre-image $x \in [M]$.
\end{enumerate}
\end{definition}

\begin{definition}
Fix a function inverter $(\alpha, \mathcal A)$.
\begin{itemize}
    \item We say that ``$(\alpha, \mathcal A)$ inverts $y$ for $f$" if
    \begin{equation*}
        \Prob{}[f(\mathcal A^{f}(\alpha, y)) = y] \ge 2/3,
    \end{equation*}
    where the probability is taken over the measurement results (internal randomness) of $\mathcal A$.
    \item For any real $\eps$, we say that ``$(\alpha, \mathcal A)$ inverts $\eps$ fractions of inputs" if
    \begin{equation*}
        \Prob{y, f}[(\alpha, \mathcal A) \textnormal{ inverts $y$ for $f$}] \ge \eps,
    \end{equation*}
    where $y$ and $f$ is sampled uniformly from $[N]$ and $S_N$, respectively.
\end{itemize}

\end{definition}

\begin{theorem}(Lower bound for permutations)
\label{permutations}
For any permutation inverter that invert $\eps$ fractions of inputs, assuming:
\begin{enumerate}
    \Item \begin{equation}
        \label{eq-nondegenerate-eps}
        \eps = \omega(1/N),
    \end{equation}
    that is, the inverter can succeed on more than a constant number of points;
    \Item \begin{equation}
        \label{eq-nondegenerate-T}
        T = o(\eps \sqrt{N}),
    \end{equation}
    noting that $T = O(\sqrt{\eps N})$ is the complexity of Grover's search algorithm;
    \Item \begin{equation}
        \label{eq-nondegenerate-S}
        S \ge 1.
    \end{equation}
\end{enumerate}
We have
\begin{equation*}
    ST^2 \ge \tilde\Omega(\eps N)
\end{equation*}
for all sufficiently large $N$.
\end{theorem}

\begin{theorem}(Lower bound for functions)
\label{functions}
For any function inverter that invert $\eps$ fractions of inputs, assuming:
\begin{enumerate}
    \Item \begin{equation}
        \label{eq-not-too-many-preimages}
        M = O(N),
    \end{equation}
    \Item \begin{equation}
        \label{eq-function-nondegenerate-T}
        T = o(\eps \sqrt{M}/\log^{10} N),
    \end{equation}
    noting that $T = O(\sqrt{\eps M})$ is the complexity of Grover's search algorithm;
    \Item \begin{equation}
        \label{eq-function-nondegenerate-eps}
        \eps \ge 1/N,
    \end{equation}
    that is, the inverter performs no worse than a fixed point output inverter;
    \Item \begin{equation}
        \label{eq-function-nondegenerate-S}
        S \ge 1.
    \end{equation}
\end{enumerate}
We have
\begin{equation*}
    ST^2 \ge \tilde\Omega(\eps M)
\end{equation*}
for all sufficiently large $M$.
\end{theorem}

Towards proving these two theorems, we also develop a lower bound for a natural generalization of quantum random access code (QRAC).
We believe the notion of quantum random access code is a natural object to study in quantum information theory, and that our generalization has potential to find other applications in quantum information.
In \Cref{sec:qrac-vl}, we will explain the concept more thoroughly and prove the lower bound.

\subsection{Related Work}
\label{sec:concurrent-work}

Independently in \cite{cryptoeprint:2019:1093}, they considered a number of cryptographic applications of random functions under both classical advice (quantum query) model and quantum advice model, which they denote as AI-QROM and QAI-QROM respectively.
Under quantum advice model, their Theorem 6 showed bounds for inverting random permutations using different techniques, namely, gentle measurements and semi-classical oracle.

However, in their work, they left the problem of proving bounds for random functions open and we partially give some answers to that open problem in this work.
They noted that generalizing this to function inversion seems problematic -- to use gentle measurement lemma, we need to boost the per-element success probability to $1 - O(1/N^4)$; however, in the function case, even with our idea of using 2-universal hash functions (which we outline in the technical overview section), we cannot hope to boost the per-element success probability beyond $1 - o(1/N)$ as it would already make storing all the hash tags too expensive for an efficient encoding.
In conclusion, it seems hopeless to combine gentle measurement technique with our 2-universal hash for adversaries with constant success probability on $\eps$ fractions of input.
Our QRAC technique, on the other hand, works and gives non-trivial bound even if the per-element success probability is as low as $1 - O(1/\log N)$ under the exact same setting.
This shows that our QRAC technique seems to be able to achieve some improvements compared to their approach.
We also note that our proof technique does not involve internal measurements in the compress/decompress algorithm and is conceptually simpler.

\section{Technical Overview}
\label{sec:tech}

\subsection{Permutations}

We first show how to solve the permutation inversion problem, which is an easier argument.

\paragraph*{Compression argument.}
In De et al. \cite{de2009non}, the main idea in proving the lower bound is to leverage the inverter to produce an algorithm that compresses the permutation into a short string, and the information theoretic lower bound on the size of the string translates to our desired lower bound.
However, as the inverter needs to make $T$ adaptive queries, we need to produce the correct answer for the inverter so that she can successfully invert the image and we can extract the information from the inverter.
The way to do this is to randomly remove a small enough subset of the image from the permutation.
As we are picking a small independently random subset, the probability that the inverter hits this subset will be small.
Therefore, we can use the advice and the permutation without the removed fraction as the encoding for the permutation, and since the length of the encoding is lower bounded by the entropy of all the permutations the encoding scheme is able to compress, this translates to a lower bound in the space-time trade-off for the permutation inversion problem.
In the process, we ``cheated'' by using some shared randomness, but it turns out we can fix this since having shared randomness does not affect the information theoretic lower bound that we need in the end.

As shown by Nayebi et al. \cite{nayebi2015quantum}, this idea also holds similarly for algorithms that can make quantum queries to the permutation.
Namely, if we change $\delta$ fraction of the input, by a similar argument to proving the optimality of Grover's algorithm \cite{ambainis2002quantum}, a quantum query algorithm is required to take $\Omega(\sqrt{1/\delta})$ queries to distinguish the change with constant probability.
However, they also have shown that this approach has a fundamental limitation when one tries to adapt it to the case where the pre-processed information can be quantum.
Recall that in order to invoke the inverter to recover a deleted entry, we need to invoke it with the pre-computed advice.
If the advice is classical, we can simply repeat this process for every entry to recover the entire permutation table; but if the advice is quantum, we cannot hope to do this repeatedly as the previous copy would be destroyed by measurement, and we cannot hope to clone multiple copies of the advice for free due to no cloning theorem \cite{wootters1982single}.
The only thing we can do is to produce multiple copies of the same advice in the encoding phase, however, if we work out the calculation, we can see that this encoding scheme is too inefficient for proving a meaningful lower bound for inverting permutations.

\paragraph*{Avoiding repeated measurements.}
Approaching this challenge, our idea is to reduce the problem to a similar problem that does not require recovering the entire permutation table.
Ambainis et al. \cite{ambainis1999dense} introduced the notion of Quantum Random Access Code with Shared Randomness, which is a two-player game where two players share some randomness $R$; the first player $\mathcal A$ gets a bit string $X$ chosen uniformly at random and is asked to encode it into an encoding $Y \gets \mathcal A(X, R)$; and the second player is asked to recover $X_i$ given $Y, R$ and some index $i \in [|X|]$ chosen uniformly at random.
Assuming the two player succeeds with probability $\delta$, the number of bits in $Y$ is lower bounded by (with some very rough approximations when $\delta \rightarrow 1$) $|Y| \ge \delta |X|$.
It can be shown that this lower bound is tight even when everything is classical, simply by observing that an algorithm that simply remembers a $\delta$ fraction of the input wins the game with probability $\delta$.
This game has found several applications in quantum information theory and quantum cryptography, for example~\cite{alagic2018non}.

Thus, a natural idea is to come up with a similar lower bound for quantum random access code with shared randomness for permutations and do the reduction.
However, unlike in the case of bit strings, as there is correlations between each element of the permutation, our lower bound argument would need to proceed very carefully.
Indeed, in this work we proved a lower bound on the expected number of qubits which is only related to the overall entropy, the average element entropy, and the recovery success probability.
Furthermore, this holds even if there exists correlations between the elements.
In general, this lower bound is weaker than the compression argument where the entire permutation is recovered.
However, we note that if the success probability is high, say $\delta \ge 1 - O(1/N)$ for permutations, then the expected number of qubits needs to be at least $\log N! - O(\log N)$, which asymptotically matches the lower bound for compression argument in the classical case.

A direct encoding scheme would be using the encoding scheme of Nayebi et al. \cite{nayebi2015quantum} and decode only the element in question.
However, this direct idea does not work, since we are randomly removing entries from the permutation, the scheme only succeeds when the removed entries (determined by shared randomness $R$) does not affect the output of the inverter, which only happens with a small probability.
This means that $\delta$ will be bounded away from 1.
Recall that our encoding will need to remember $1 - o(1)$ fraction of the permutation, this gives us no meaningful bound.
In fact, in order for this idea to succeed, we need to boost the success probability to also $1 - o(1)$.

We observe that in our proof for quantum random access code, the length of our encoding is ultimately bounded by the von Neumann entropy of the encoding.
By using the variable length version of quantum source coding theorem, we can also use a variable length encoding that is still bounded by the von Neumann entropy of the encoding.
Specifically, if the randomness will cause the encoding to err, we will simply use the entire permutation table as our encoding, which the decoder can decode any element directly.
By repeating the advice poly-logarithmically many times, we can make the success probability sufficiently close to 1 for proving a meaningful bound.

\subsection{Functions}

To bootstrap the previous argument into an argument for function inverters, we can view the inverse function $f^{-1}$ as a partition of $[M]$, and our goal is to design a random access code for querying this partition.
In order to accommodate all possible adversaries, we only pick the pre-images that have high probability to be returned by the adversary.
However, consider the following bad case, $f^{-1}(y) = \{x_1, x_2\}$, and the adversary uniformly returns $x_1, x_2$ or a third bad output $x'$.
In this case, majority vote will not work since (without loss of generality) assuming we removed $x_1$ from the encoding, the decoder cannot distinguish adversary returns $x_1$ or $x'$ (assuming the adversary gets lucky so that $x'$ is also removed from the encoding).
To fix this, we use a 2-universal hash function (sampled from shared randomness) and use the hash tag to distinguish the correct output.

However, we need to choose the hash length very carefully, as choosing a length too short results in high error probability, and length too long results in inefficient coding (our goal is to achieve nontrivial savings for the random function).
In particular, due to our QRAC bound, we must choose our length tag to be much shorter than $\log N$ to get a nontrivial bound for function inversion.
It turns out that using a length of $\log \log N$ works in our case.