\documentclass{article}
%\usepackage{stix2}
\pdfoutput=1
\usepackage[utf8]{inputenc}
\usepackage[a4paper, margin=1in]{geometry}
\usepackage[active]{srcltx}
\usepackage{babel}
%\usepackage{stix}
\usepackage{verbatim}
\usepackage{mathtools}
\usepackage{bm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{microtype,comment}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{subcaption}
%\usepackage{subfigure}
\usepackage{booktabs} 
\usepackage{verbatim}
\usepackage{mathtools}
\usepackage{bbm}
\usepackage{amsmath}
\usepackage{amssymb} 
\usepackage{amsthm}
\usepackage{babel}
\usepackage{amsthm}
\usepackage{dsfont}
\usepackage{array}
\usepackage{mathrsfs}
\usepackage{color}
\usepackage{natbib}
\usepackage{enumerate}
\usepackage{comment}
\usepackage{url}[sf]
\usepackage{needspace}
\usepackage{enumitem}
\usepackage{etoolbox}
\usepackage[2col]{optional} % 2col/arxiv
\DeclarePairedDelimiterX\set[1]\lbrace\rbrace{\def\given{\;\delimsize\vert\;}#1}

\newlist{pfparts}{description}{1}
\setlist[pfparts,1]{%
  font=\normalfont\textsf,
  itemindent=2pt,
  wide,
  itemsep=0pt,topsep=2pt,
  labelsep=0.75ex
}


\usepackage{tikz}
\usepackage{tikzscale}
\usepackage{pgfplots}
\usepackage{lineno}


%\usepackage{style}

\pgfplotsset{compat=1.17}
\usetikzlibrary{calc}
\usetikzlibrary{positioning}
\usetikzlibrary{intersections}
\usetikzlibrary{backgrounds}

 \bibpunct[, ]{(}{)}{,}{a}{}{,}%
 \def\bibfont{\small}%
 \def\bibsep{\smallskipamount}%
 \def\bibhang{24pt}%
 \def\newblock{\ }%
 \def\BIBand{and}%


% \def\lowint{\mkern3mu\underline{\vphantom{\intop}\mkern40mu}\mkern-20mu\int}
% % %\def\lowiint{\mkern3mu\underline{\vphantom{\intop} \vphantom{\intop} \mkern7mu}\mkern-10mu\iint}

%  \def\upint{\mathchoice%
%     {\mkern3mu\overline{\vphantom{\intop}\mkern40mu}\mkern-20mu}%
%     {\mkern7mu\overline{\vphantom{\intop}\mkern40mu}\mkern-14mu}%
%     {\mkern7mu\overline{\vphantom{\intop}\mkern40mu}\mkern-14mu}%
%     {\mkern7mu\overline{\vphantom{\intop}\mkern40mu}\mkern-14mu}%
%   \int}

% \newcommand{\lowint}[1]{
%   \underline{\int_{#1}}
% }
% \newcommand{\lowint}[2][\text{}]{
%   \underline{\int_{#1}^{#2}}
% }

% \newcommand{\upint}[1]{
%   \overline{\int_{#1}}
% }
% \newcommand{\upint}[2]{
%   \overline{\int_{#1}^{#2}}
% }
\newtheorem{example}{Example}

% \theoremstyle{plain} 
% \newtheorem{lemma}{\textbf{Lemma}} 
% \newtheorem{proposition}{\textbf{Proposition}}
% \newtheorem{theorem}{\textbf{Theorem}}\setcounter{theorem}{0}
% \newtheorem{corollary}{\textbf{Corollary}} 
% \newtheorem{assumption}{\textbf{Assumption}}
% \newtheorem{example}{\textbf{Example}} 
% \newtheorem{definition}{\textbf{Definition}}
% \newtheorem{fact}{\textbf{Fact}}
% \newtheorem{property}{Property}
% \theoremstyle{definition}
% \theoremstyle{remark}
% \newtheorem{condition}{Condition}
% \newtheorem{claim}{Claim}
% \newtheorem*{claim*}{Claim}
% \newtheorem*{lemma*}{Lemma}
% \newtheorem*{theorem*}{Theorem}
% \newtheorem{case}{Case}
% %\theorempostwork{\setcounter{case}{0}}
% \newtheorem{conjecture}{Conjecture}
% \newtheorem{remark}{\textbf{Remark}}
%  \newcommand{\vect}{\textbf} 

\usepackage{braket}
\newcommand{\vect}{\textbf} 

%\theorempostwork{\setcounter{case}{0}}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\defeq}{:=}
\newcommand{\rhovaname}{\rho_{V}}
\newcommand{\rhovbname}{\rho_{VB}}
\newcommand{\rhova}[1]{\rhovaname\left( #1 \right)}
\newcommand{\loRiemannint}[2]{
  \underline{\int_{#1}^{#2}}
}
\newcommand{\rhovb}[1]{\rhovaname\left( #1 \right)}
\newcommand{\Aball}[2]{\mathcal{B}_{#1,#2}}
\newcommand{\Aballsize}[2]{\left| \Aball{#1}{#2} \right|}
\newcommand{\ballsize}[1]{\left| \mathcal{B}_{#1} \right|}

\definecolor{mor}{rgb}{0.8, 0.5, 0.0}
%\newcommand{\zhihao}[1]{ {\color{mor} [ Zhihao: {#1} ]  } }
\newcommand{\sss}[1]{ {\color{orange} [ Sahasrajit: {#1} ]  } }

%\newcommand{\ak}[1]{ {\color{mor} [ Aleksandra: {#1} ]  } }

 \makeatletter
\def\namedlabel#1#2{\begingroup
    #2%
    \def\@currentlabel{#2}%
    \phantomsection\label{#1}\endgroup
}
\makeatother

\makeatletter
\let\original@footnote\footnote
\newcommand{\align@footnote}[1]{%
  \ifmeasuring@
    \chardef\@tempfn=\value{footnote}%
    \footnotemark
    \setcounter{footnote}{\@tempfn}%
  \else
    \iffirstchoice@
      \original@footnote{#1}%
    \fi
  \fi}
\pretocmd{\start@align}{\let\footnote\align@footnote}{}{}
\makeatother

\title{\textbf{Homework on social choice and welfare} }
\begin{document}
\maketitle

%In this problem we study a problem of representation robustness in participatory budgeting. 

% \textbf{Homework deadline: 5 pm on 2 May 2024(Thursday)}


\noindent
Electronic submission to Gradescope due {\bf 5:00pm Saturday 5/2}.
\section{Solving optimization problems in python}

Familiarise yourself with solving optimization problems in python. You may use some common softwares like \cite[CVXPY]{diamond2016cvxpy}, \cite[OR-Tools]{or-tools}. You may visit \url{cvxpy.org} for some examples on how to use cvxpy for the formulation of convex optimization problems. To gain more familiarity, formulate and solve the following problem on an LP solver. A linear program is formulated and solved in the colab notebook \\
\url{https://colab.research.google.com/drive/1dAQF02yok3Y7SUUtoMq69_Hn7DYp8Xxf?usp=sharing}. 

Please do not directly edit the colab notebook. Make a copy of the notebook and then solve the problems on it. While submitting please attach the relevant python scripts and/or excel files 
to enable us to give partial credits.

%An example how to install cvxpy in python in described in \url{cvxpy.org} 
\subsection*{Problem 1}

A pharmaceutical company has 10000mg of a certain drug that it wants to package in capsules of 4 sizes- a) extra-large b) large c) medium and d) small which can hold 100mg, 60 mg, 30 mg and 10 mg respectively. Past consumer research shows that the number of large capsules should be at least twice that of extra-large ones and the number of medium capsules should be at least thrice the number of large capsules. Further there must be at least 100 small capsules. Each extra-large capsule is sold for a profit of 5 dollars, large capsule for a profit of 4 dollars, medium capsule for a profit of 2 dollars and small capsule for a profit of 50 cents. Assuming that the company may manufacture fractional number of capsules, how many capsules of each type should it manufacture to maximise the profit?

Formulate the problem as a linear program and use python or excel to solve it. We recommend you to use python as it maybe useful later. Also report the maximum total profit earned by the company. 

Check which primal constraints are tight and slack and verify whether the dual variables for the slack constraints are zero. Note that you can get the dual variables after solving the LP from either excel or python, as shown in class/on the python demo.

In the next problem we often refer to the set $\{1,2,\ldots,m\}$ as $[m]$.

\section{Scoring based rules for elections}




Consider a generic social choice problem with $n$ voters and $m<n$ candidates with each voter having a preferred ranking over all the candidates. We are interested in studying different scoring based aggregation rules to determine the winner in which a score of $s_k$ is given to a candidate ranked at the $k^{th}$ position and the candidate with highest score wins.


\textbf{Scoring based rules}: A scoring rule is determined by a sequence of real numbers $(s_1,s_2, \ldots, s_m)$ satisfying $s_1 \geq s_2 \geq \ldots \geq s_m$. A candidate who is ranked at $k^{th}$ position by a voter $i$ is assigned score of $s_k$ by voter $i$ and the winner is decided by calculating the cumulative score for each candidate by summing across all voters. Ties of scores maybe broken in an arbitrary way. An example is described below for two different scoring vectors.

\begin{example}
    Consider an election with three candidates $A,B$ and $C$ and three voters. The first voter ranks $A>C>B$, the second candidate ranks $B>A>C$ and the third candidate ranks $B>A>C$. We now discuss the winner under two different scoring vectors.

    \begin{itemize}
        \item Suppose a scoring vector of $(1,3/4,0)$ is chosen. In this case, candidate $A$ gets a cumulative score of $1+3/4+3/4=2.5$, candidate $B$ a cumulative score of $2+0=2$ and candidate $C$ a cumulative score of $3/4$ and thus $A$ is the winner.

        \item Suppose a scoring vector of $(1,1/4,0)$ is chosen. In this case, candidate $A$ gets a cumulative score of $1+1/4+1/4=1.5$, candidate $B$ a cumulative score of $2+0=2$ and candidate $C$ a cumulative score of $1/4$ and thus $B$ is the winner.
    \end{itemize}

    We may observe that different scoring vectors may lead to different winners.
\end{example}

% We now study problems to see if there exists a scoring vector such that a candidate is declared as a winner.

%Each candidate who is ranked at the $k^{th}$ position by a voter is assigned score of $s_k$ and 

% \section*{Problem 2}


% Recall our original setup with $n$ voters and $m$ candidates (denoted by $\mathcal{C}= \{c_1,c_2,\ldots,c_m\}$) and we say a scoring vector $(s_1,s_2, \ldots, s_m)$ as permissible if $s_i \geq s_{i+1}$ for every $i \in [m-1]$. 

% \begin{itemize}
%     \item Suppose each voter $i \in [n]$ submits a ranking over all the $m$ candidates. Formulate a linear program (LP) to check whether there exists a scoring vector such that a candidate $c \in \mathcal{C}$ is the winner. 
%     \item (Constraining the scoring vector): In this problem, we define a scoring vector to be ``valid'' if it satisfies $s_i \geq 2s_{i+1}$ for every $i \in [m-1]$. Formulate a LP to check whether there exists a valid scoring vector such that a candidate $c \in \mathcal{C}$ is the winner. 
% \end{itemize}


% Check the attached file ``vote ranking.csv'' with 5 candidates $A,B,C,D$ and $E$ with each row denoting the preferred ranking of the candidates for every voter. 

% Now solve the LPs formulated above to check for every candidate if it can be the winner. 


\section{Different weights on votes for aggregation}


However, in this problem we consider under-representations of minorities (in the election process) and over-weight/ underweight some votes. Let us denote the weight that we assign to voter $i$ by $w_i$ and denote the weight vector by $\vect{w} \in \mathbbm{R}^n$ satisfying $\sum w_i=1$. 

Observe that in this problem the total score of a candidate is the weighted cumulative score by computing the weighted sum over all voters. We give an example below.

\begin{example}
    Consider an election with three candidates $A,B$ and $C$ and three voters. The first voter ranks $A>C>B$, the second candidate ranks $B>A>C$ and the third candidate ranks $B>A>C$. We now discuss the winner under the scoring vector $(3,2,1)$ under two different weight vectors. We assume a tie-breaking order with $A>B>C$.

    \begin{itemize}
        \item Suppose a weight vector $(1/3,1/3,1/3)$ is chosen. In this case, candidate $A$ gets a cumulative score of $1/3(3+2+2)=7/3$, candidate $B$ a cumulative score of $1/3(3+3+1)=7/3$ and candidate $C$ a cumulative score of $1/3(2+1+1)=4/3$ and thus $A$ is the winner as $A$ is preferred over $B$ under the tie-breaking rule

        \item Suppose a a weight vector $(0,1/2,1/2)$ is chosen. In this case, candidate $A$ gets a cumulative score of $1/2(2+2)=2$, candidate $B$ a cumulative score of $1/2(3+3)= 3$ and candidate $C$ a cumulative score of $1/2(1+1)=1$ and thus $B$ is the winner.
    \end{itemize}

    We may observe that different weighting vectors may lead to different winners.
\end{example}


\section*{Problem 2}

Recall that in this problem, we over-weight and underweight some votes. We now restrict the weights to deviate from the uniform distribution by factor of $\alpha$ and $\beta$ and thus restrict the weight vector $\vect{w}$ to lie in $S(\alpha,\beta) := \{\vect{w}: \sum_{i=1}^{N} w_{i} = 1 ; \frac{\alpha}{N} \leq w_i \leq \frac{\beta}{N}\}$. Suppose, we use the  scoring vector with $s_i$ = $m+1-i$ for every $i \in [m]$.


Now formulate a linear program to check whether there exists a weight vector in $S(\alpha,\beta)$ such that a candidate $c \in \mathcal{C}$ is the winner.

Also solve this linear program for attached file ``vote ranking.csv'' for different values of $\alpha$ and $\beta$ in the table to check whether candidate $A$ can be the winner. Solve the same linear program for candidate $E$ as well.

\begin{table}[!htp]
    \centering
    \begin{tabular}{|c|c|}
        $\alpha$ & $\beta$\\
        \hline
         0.9 & 2 \\
         \hline
         0.8 & 2\\
         \hline
         0.7 & 2\\
         \hline
         0.8 & 3\\
         \hline
         0.7 & 5\\
    \end{tabular}
    \caption{Various values of $\alpha$ and $\beta$}
    \label{tab:my_label}
\end{table}


\section{Knapsack voting problem}

Recall the problem of knapsack voting with $n$ voters and $m$ projects and a total budget of $B$. Each voter $i \in [n]$ votes for a budget $v_i \in \mathbbm{R}_{\geq 0}^m$ \footnote{$\mathbbm{R}_{\geq 0}$ denotes the set of non-negative reals} satisfying the budget constraint $\sum_{i=1}^{m} v_{i,j} \leq B$.


Recall from class that we gave the formulation of a linear program to select a budget $z$ that maximises the 
 cumulative overlap utility by summing across all voters. The overlap utility between a budget $v \in \mathbbm{R}_{\geq 0}^m$ and $z \in \mathbbm{R}_{\geq 0}^m$ is given by  $\sum_{j = 1}^{m} \min(v_j,z_j)$. 

\section*{Problem 3}
 The attached ``austin data clean.csv'' contains the preferred allocations of $n=37,004$ voters to $m=11$ different projects with a total budget of B= 54750 units. Solve the linear program (in python) to select a budget $z \in \mathbb{R}_{\geq 0}^m$ maximising the overlap cumulative utility.

\ \\Note that this problem is too big to solve using excel.

\section*{Problem 4*}
{\em This is much harder than the other problems and is completely optional. If you do this, you can skip all other problems in this HW. Or you can do it for an extra credit of 5\% of the total class grade. You can also ask for one (and only one) hint.}

\ \\Consider the same setup as problem 3. Consider the first vote in the csv file. Now, determine if there are voter weights (using the notation of problem 2) which satisfy $\alpha=0.8, \beta = 2$ which can make this budget the optimum budget.

\ \\Note that this problem is too big to solve using excel.

\section{Rent Division}
This uses the same setup as the class. Four friends want to share the cost of a 4-room apartment. The total cost is \$4,000 and their valuations are given in the attached excel file. Use excel's LP solver to find the assignment that maximizes the total valuation. Without solving another LP, use the dual solution (on the sensitivities sheet) to find  envy-free prices for the rooms under this assignment. The prices should sum to \$4,000 which might require adding or deleting a constant to the prices that you obtain from the dual solution.

{\em It is not an acceptable solution for this problem to just guess the assignments and the prices. You have to actually use the LP solver and show how you used the dual solution to derive prices.}

%We now restrict the weights to deviate from the uniform distribution by factor of $\alpha$ and $\beta$ and thus restrict the weight vector $\vect{w}$ to lie in $S(\alpha,\beta) := \{\vect{w}: \sum_{i=1}^{N} w_{i} = 1 ; \frac{\alpha}{N} \leq w_i \leq \frac{\beta}{n}\}$. 


 
% A farmer has 10000gm of seed and owns three types of land with varying levels of fertility a) good , b) medium and c) poor to cultivate. The a

% We consider a Markowitz portfolio optimization problem with $n$ assets held over a period of time and the total budget being given by $B=1$. Let $x_i$ denote the quantity of asset $i$ being held and let $p_i$ denote the relative price change of asset $i$ and thus, the overall return is given by $p^Tx$ with $p,x \in \mathbbm{R}^n$. 

% We now consider a stochastic model where $p \in \mathbbm{R}^n$ is a stochastic random variable with mean $\bar{p}$ and covarianfollce $\Sigma$. Thus for an investment $x \in \mathbbm{R}^n$, the expected return is given by $$



% To get started you may use the code from the notebook.

% \url{https://colab.research.google.com/drive/1dAQF02yok3Y7SUUtoMq69_Hn7DYp8Xxf?usp=sharing}





% \begin{figure}
%     \centering
%     \includegraphics{figure_allocation.png}
%     \caption{Preferred allocation of projects}
%     \label{fig:allocation}
% \end{figure}

% \begin{figure}
%     \centering
%     \includegraphics{figure_dollar_allocation.png}
%     \caption{Voter per dollar}
%     \label{fig:dollar_allocation}
% \end{figure}




\bibliographystyle{plainnat}
\bibliography{refs}



\end{document}