\documentclass[10pt]{article}
\renewcommand{\baselinestretch}{1.5}
\usepackage{epsfig}
\usepackage{subfigure}
\newcommand\s{{\bf s}}
\newcommand\x{{\bf x}} 
\newcommand\y{{\bf y}} 
\newcommand\z{{\bf z}} 
\newcommand\p{{\bf p}} 
\newcommand\e{{\bf e}} 
\renewcommand\d{{\bf d}} 
\renewcommand\a{{\bf a}} 
\renewcommand\b{{\bf b}} 
\renewcommand\c{{\bf c}} 

\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}
\setlength{\textheight}{22cm} \setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0pt} \setlength{\evensidemargin}{1pt}
\setlength{\oddsidemargin}{1pt} \setlength{\headsep}{10pt}
\parskip=2mm
\parindent=8mm

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{example}[theorem]{Example}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{remark}[theorem]{Remark}

\newcommand{\xiaocheng}[1]{{[XC: {#1}]}}

\begin{document}
\title{CME307/MS\&E311 Suggested Course Project II: Online Linear Programming and Resource Allocation}
%\author{(You don't need to answer all the questions posted in the project)}
\maketitle



In resource allocation described in class, we consider a linear program of the form
\begin{equation}
\begin{array}{ll}\label{resourceallo}
\mbox{maximize}_{\x} & \sum_{j=1}^n\pi_j x_j\\
\mbox{s.t.}& \sum_{j=1}^n a_{ij}x_j\le b_i, \mbox{  }\forall\mbox{ } i=1,2,...,m\\
& 0\le x_j \le 1,\ \forall\ j=1,...,n;
\end{array}
\end{equation}
where $\pi_j$ is the gain to allocate a combination of goods/resources to bidder $j$ (we can think of this as the bid of bidder $j$), $a_{ij}$ is the requested quantity of good/resource $i$ by bidder $j$, and $b_i$ is the total available quantity of good/resource $i$; see \cite{shipra1} and references therein. For simplicity, in this project we assume that $a_{ij}$ is either $0$ or 1.

The classical offline LP algorithm would compute the full optimal solution $\x$  
in one go, while the online algorithm would compute the solution sequentially $x_1$, then $x_2$,.... Specifically, when computing
the decision variables $x_1$ to $x_k$, we don't consider information associated with $x_{k+1}$ and beyond.
In this course project, you are asked to study and explore some theories of online linear and convex programming and perform computational observations on some simulated or real data. 

The online algorithm described in \cite{shipra1} is as follows: suppose there is a reliable estimate that there will be a total of $n$ bidders in the market; then we wait for the first $k$ bidders to arrive, solve the resulting partial linear program:
\[
\begin{array}{cll}
\mbox{(SLPM):}& \mbox{maximize}_{x_1,...,x_k} & \sum_{j=1}^k\pi_j x_j\\
         &\mbox{s.t.}& \sum_{j=1}^{k} a_{ij}x_{j}\le \frac{k}{n}b_i, \mbox{  }\forall \mbox{ }i=1,2,...,m,\\
         && 0\le x_j\le 1,\ \forall\ j=1,...,k.
\end{array}
\]
and then use the {\em dual prices}, say $\bar{\y}^k$, of the (partial) LP for future online decisions:
\[x_j=1,\ \mbox{if}\ \pi_j> \a_j^T\bar{\y}^k\ \mbox{and there are remaining goods left};\quad \mbox{and}\ x_j=0,\ \mbox{otherwise}.\]
The interpretation of this is that we allow the allocation to bidder $j$ if the their bid is higher than the value, calculated after $k$ bids, of the goods they require.

You may run the online and offline auctions using simulated bidding data with $m=10$ and $b_i=1,000$ for all $i$. Fix a ground truth price vector $\bar{\p}>0$. One way to generate a sequence of random bids, $k=1,2,...$, is as follows:  generate a vector $\a_k$ whose each entry is either zero or one at random, then let $\pi_k=\bar{\p}^T\a_k+randn(0,0.2)$ where $randn(0,0.2)$ represents the Gauss random variable with zero mean and variance $0.2$ in Matlab. 

{\bf Question 1:} Let $n=10,000$. Then run the one-time online learning (SLPM) algorithm using the same simulated bidding data above based on three different sizes of $k=50,100,200$ to see how sensitive the ratio of the generated revenue over the offline revenue is to $k$. Note that we keep the estimated prices $\bar{\y}^k$ fixed in this case. What is the trade-off between choosing large and small $k$?


{\bf Question 2:} Now let us dynamically update the dual prices at time points $k=50,100,200,400,800...$ and use the prices to make decision for the immediate subsequent period. How does the dynamic learning perform on the revenue? Do the dual price vectors $\bar{\y}^k$ generated from the online LP model approach the ground truth vector $\bar{\p}>0$? Explain your observations and findings. Again, use the same data generated in Question 1. 


The online algorithm described above does not use information on how much good inventory remains for allocation in the decision process.
One approach is to consider an offiline model as
\begin{equation}
\begin{array}{ll}\label{CPCAM}
\mbox{maximize}_{\x,\s} & \sum_j\pi_j x_j +u(\s)\\
\mbox{s.t.}& \sum_j a_{ij}x_j+s_i=b_i, \mbox{  }\forall \mbox{  }i=1,2,...,m,\\
& 0\le x_j\le 1,\ \forall\ j=1,...,n,\\
& s_i\ge 0, \forall\ i=1,...,m.
\end{array}
\end{equation}
where $u(\s)=u(s_1,\ldots,s_m)$ is increasing and strictly concave and it gradient entry $\frac{\partial u(.)}{\partial s_i}_{s_i=0}$ is sufficiently large for all $i$. Typical choices of $u(\s)$ are
$$u(\s)=\frac{w}{m}\sum_i\log{s_i}$$
or
$$u(\s)=\frac{w}{m}\sum_i(1-e^{-a\cdot s_i})$$
for some parameters $w (>0)$ and $a (>0)$.

{\bf Question 3:} Write down the first-order KKT conditions for optimality. Are they sufficient? Argue why this problem will have unique optimal multipliers/prices (that is, the Lagrangian multipliers on the $m$ equality constraints of the problem).
How would you interpret $u(\s)$ and $\s$? (Hint: Read \cite{peters2}, \cite{shipra} and \cite{AD, GM, KRTV}.)
  
    
{\bf Question 4:} Now consider, after the first $k$ bidders arrived, solving the revealed partial convex program
\[
\begin{array}{cll}
\mbox{(SCPM):}& \mbox{maximize}_{x_1,...,x_k} & \sum_{j=1}^k\pi_i x_i+u(\s)\\
         &\mbox{s.t.}& \sum_{j=1}^{k} a_{ik}x_{k} +s_i\le \frac{k}{n}b_i, \mbox{  }\forall \mbox{ }i=1,2,...,m,\\
         && 0\le x_j\le 1,\ \forall\ j=1,...,k.
\end{array}
\]
and then use the {\em optimal Lagrangian multipliers/prices}, say $\bar{\y}^k$, of the partial convex program for future online decisions:
\[x_j=1,\ \mbox{if}\ \pi_j> \a_j^T\bar{\y}^k\ \mbox{and there are remaining goods left};\quad \mbox{and}\ x_j=0,\ \mbox{otherwise}.\] 
 
{\bf Question 5:} Dynamically update the {\em optimal Lagrangian multipliers/prices} at time points $k=50,100,$ $200,400,800...$ and use the them to make decision for the immediate subsequent period. How does the convex programming online learning perform on the revenue? Again, use the same data generated in Question 1, and you may tune parameters $w$ and $a$ in $u(\s)$ to improve the performance. 


Another online approach that uses the information of inventory (See \cite{li}) is the Action-history-dependent Learning Algorithm, which means this algorithm uses historic actions to update the dual price, i.e., at each time point $k\geq2$, decide the value of $x_k$:
\[x_k=1,\ \mbox{if}\ \pi_k> \a_k^T\bar{\y}^{k-1}\ \mbox{and there are remaining goods left};\quad \mbox{and}\ x_k=0,\ \mbox{otherwise},\] 
update remaining resources:
$$
  b_i^{(k)} = b_i^{(k-1)} - a_{ik}x_{k} \text{ for i = 1,2,...,m,}
$$ 
and, then update the dual price by solving the linear programming:
\begin{equation}
\begin{array}{cll}
\mbox{}& \mbox{maximize}_{x_1,...,x_k} & \sum_{j=1}^k\pi_j x_j\\
         &\mbox{s.t.}& \sum_{j=1}^{k} a_{ij}x_{j}\le \frac{k}{n-k}b_i^{(k)}, \mbox{  }\forall \mbox{ }i=1,2,...,m,\\
         && 0\le x_j\le 1,\ \forall\ j=1,...,k,
\end{array}
\label{OLP_li}
\end{equation}
and, just compute the initial dual price by (\ref{OLP_li}) when $k=1$.

{\bf Question 6:} Solve the LP by the Action-history-dependent Learning Algorithm. At each time point $k\geq2$, compute $\sum\limits_{j=1}^{k}r_jx_j-\frac{k}{n}OPT$ for the Action-history-dependent Learning Algorithm, where $OPT$ is the optimal of the offline problem (\ref{resourceallo}). Then, do the same thing for the algorithm in Question 2. Which algorithm has better performance? Provide your result and intuition. Again, use the same data generated in Question 1.



{\bf Question 7:} In \cite{li}, note that if $(\pi_j,\a_j)\sim (\pi,\a),\ j=1,2,...,n$ is a sequence of i.i.d. random vectors, the problem (\ref{resourceallo}) is closely related to 
\begin{equation}
\begin{array}{cll}
\mbox{}& \mbox{minimize}_{\bar{\y}} & \d^T\bar{\y} + \mathbb{E}\left( \pi-\a^T\bar{\y}\right)^+, \\
         &\mbox{s.t.}& \bar{\y}\geq0,
\end{array}
\label{OLP_dual_li}
\end{equation}
where $\d=\b/n$ and $(\cdot)^+ = \max\{\cdot,0\}$. Prove that (\ref{OLP_dual_li}) is a convex optimization problem and find the connection between (\ref{resourceallo})
and (\ref{OLP_dual_li}).

{\bf Question 8:}
Although both dynamic online algorithms above can provide good results, one drawback of them is that one has to solve a large scale LP to update the dual price. When $n$ is large, the computation is both time- and memory- consuming. A way to fix it is to utilize the idea of Stochastic Gradient Descent. 

Under some mild conditions, the objective in (\ref{OLP_dual_li}) is differentiable and the derivative is $$\textbf{f}(\bar{\y})=\mathbb{E}\left(\d-\a\mathbb{I}_{\{\pi>\a^T\bar{\y}\}}\right).$$ 
 Assume at each time step $k$, $\mathbb{E}(\textbf{f}(\pi,\a))$ can be approximated by $\textbf{f}(\pi_k,\a_k)$. Using the idea described in the lecture notes, derive a new online Algorithm with $\bar{\y}^{0}=0$ as the initialization. For here, set $\beta=\sqrt{k}$ at each time point, which is different from the lecture notes where $\beta$ is fixed. How does the dynamic learning algorithm perform on the revenue? Do the approximated dual price vectors $\bar{\y}$ generated from this gradient descent version of online LP algorithm converge to the true vector $\bar{\p}>0$? Explain your observations and findings with the same data in Question 1.

{\bf Question 9:} A key condition for the above algorithms to work is i.i.d. condition on $\{\pi_j,\bm{a}\}_{j=1}^n$. For some of the above algorithms, this condition can be relaxed. However, the essential part is that in the end of each time $k-1$, all left samples are equivalent in the sense that they have same probability to be the $k$-th sample. Is this condition necessary for the two algorithms to achieve sub-linear regret? In other words, can you construct an LP problem such that the i.i.d. assumption is violated and both the two algorithms perform badly? To follow up, how should we relax the i.i.d. assumption so that the two algorithms still perform acceptably well? 

Here, one interesting case is that the reward $\{\pi_j,\a_j\}_{j=1}^n$ is a sequence of random work but not a set of random samples from a fixed distribution, and the resources will be replenished periodically. For example, $\{\pi_j,\a_j\}_{j=1}^n$ satisfies 
$$\pi_j=\pi_{j-1}+randn(2,1),\ a_{ij}=a_{i,j-1}+randn(2,1),\ \forall i,j$$ and $b_i^{(k)}=b_i^{(k-1)}+n/10$ when $k=n/10,2n/10,...,n$. In each period, we can formulate an LP and find its optimal objective value. Will the above algorithms collect near optimal reward in each period? What if the decision maker does not know the length of each period? Can we come up with some better algorithms? Discuss your reason by numerical experiments or theoretical analysis.



\begin{thebibliography}{1}
\bibitem{AD} Shipra Agrawal and Nikhil R. Devanur.
\newblock Fast Algorithms for Online Stochastic Convex Programming
\newblock http://arxiv.org/abs/1410.7596, SODA2015

\bibitem{shipra} S. Agrawal, E. Delage, M. Peters, Z. Wang and Y. Ye.
\newblock A Unified Framework for Dynamic Prediction Market Design.
\newblock Operations Research, 59:3 (2011) 550-568.

\bibitem{shipra1} S. Agrawal, Z. Wang and Y. Ye.
\newblock A Dynamic Near-Optimal Algorithm for Online Linear Programming.
\newblock http://arxiv.org/abs/0911.2974; to appear in Operations Research.

\bibitem{GM} Anupam Gupta and Marco Molinaro
\newblock How the Experts Algorithm Can Help Solve LPs Online.
\newblock https://arxiv.org/abs/1407.5298, 2014.

\bibitem{KRTV} Thomas Kesselheim, Klaus Radke, Andreas Tönnis, Berthold Vöcking.
\newblock Primal Beats Dual on Online Packing LPs in the Random-Order Model.
\newblock https://arxiv.org/abs/1311.2578, STOC 2014.

\bibitem{li} X. Li and Y. Ye.
\newblock Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds.
\newblock https://arxiv.org/abs/1909.05499

\bibitem{peters2} M. Peters, A. M-C. So and Y. Ye.
\newblock Pari-mutuel Markets: Mechanisms and Performance.
\newblock {\em The 3rd International Workshop On Internet And Network Economics}, 2007.

\end{thebibliography}
\end{document}
{\bf Question 3:}  We continue our discussion in Question 2. Assume that the $k$th bidder has a true valuation $\hat{\pi}_k$ per share for his state selection $\a_k$. We solve (\ref{SCPM1}) for the optimal $x_k^*$. Then we charge the bidder by
$$\chi(0)-\chi(x^*_k)$$
where
\begin{equation}
\begin{array}{lll}\label{chi}
\chi(x)=&\mbox{maximize}_{z,\s}& +u(\s)\\
&\mbox{s.t.}& s_i-=b_i-q^{k-1}_i-a_{ik}x, \mbox{  }\forall \mbox{ }i=1,2,...,m.
\end{array}
\end{equation}
{\bf Question 6:} What about the minimal covering problem:
\begin{equation}
\begin{array}{ll}\label{resourcecovering}
\mbox{minimize}_{\x} & \sum_{j=1}^nc_j x_j\\
\mbox{s.t.}& \sum_{j=1}^n a_{ij}x_j\ge b_i, \mbox{  }\forall\mbox{ } i=1,2,...,m\\
& 0\le x_j \le 1,\ \forall\ j=1,...,n;
\end{array}
\end{equation}
where $c_j$ is the cost to select a combination of goods/resources of producer $j$, $a_{ij}$ is the provided quantity of good/resource $i$ from producer $j$, and $b_i$ is the total known needed quantity of good/resource $i$. For simplicity, in this project we assume that $a_{ij}$ is either $0$ or 1. 

Develop an online algorithm to select producer  

Using the incentive compatibility theorem, under this charging method, the optimal strategy for the $k$th bidder is to bid his or her true valuation $\hat{\pi}_k$ per share (assume that $\a_k$ is already determined and fixed) 

{\bf Remark}: A mechanism is truthful (or incentive compatible) if and only if for every agent, reporting his or her truthful belief is always the optimal strategy, 
disregarding what others do. In fact, such an optimal strategy is called dominant strategy in game theory. In fact, the above mechanism is a special case of the VCG mechanism; read references \cite{shipra} and \cite{VCG}. 

\bibitem{Algorithmic} N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani.
\newblock Algorithmic Game Theory
\newblock Cambridge University Press, New York, NY, USA.


\bibitem{VCG} 
\newblock $http://en.wikipedia.org/wiki/Vickrey\underline{\mbox{ }} auction$.
