\documentclass[11pt]{article}
\usepackage{palatino}
\usepackage{fullpage}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{xifthen}%
\usepackage[linesnumbered,ruled,vlined]{algorithm2e}
\usepackage{nicefrac}
\usepackage{booktabs}
\usepackage{diagbox}
\usepackage{tikz}
\usetikzlibrary{positioning}


\usepackage{sgame} % Martin Osborne's game package
\usepackage{color} % needed by Martin Osborne's game package

\newcounter{question}
\setlength\parindent{0pt}

\newcommand{\question}[2]{%
	\stepcounter{question}
	\vspace{.25in} \textbf{Q\arabic{question} 
		\ifthenelse{\isempty{#1}}%
		{}% if no points
		{[#1 Points]\ }% if #1 is not empty
		#2} \vspace{.10in}
}

\newcommand{\qpart}[2]{%
	\vspace{.10in} \textbf{(#1)}
	\ifthenelse{\isempty{#2}}%
	{}% if no points
	{[#2 Points]}% if #1 is not empty
}

%\newcommand{\qpart}[2] {\vspace{.10in} \textbf{(#1)} [#2 Points]}
\newcommand{\solution}[1] {\vspace{.25in} \textbf{Solution to Q#1} \vspace{.10in}}
\newcommand{\solpart}[1] {\vspace{.10in} \textbf{(#1)}}
\newcommand{\set}[1]{\{#1\}}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\newcommand{\vA}{\mathbf{A}}
\DeclareMathOperator{\sw}{sw}
\let\sc\relax
\DeclareMathOperator{\sc}{sc}
\DeclareMathOperator{\med}{med}
\renewcommand{\vec}{\overrightarrow}
\newcommand{\bbR}{\mathbb{R}}
\renewcommand{\tilde}{\widetilde}
\renewcommand{\succeq}{\succcurlyeq}
\begin{document}\allowdisplaybreaks

\medskip
\begin{center}
{\Large CSC2421 \, Spring'24}\\[0.2cm]
{\Large Assignment 2}\\[0.2cm]
{\Large Due Date: Apr 15, 2024}\\[0.2cm]
\end{center}

\textbf{Notes}

\begin{enumerate}
\itemsep0em
	\item \emph{Citation policy:} 
	\begin{itemize}
		\item It is certainly preferable for you to solve the questions without consulting a peer, an AI, or an online source. However, if you do consult and obtain useful insights, you must cite the name of the peer/AI or the link of the source you referred. 
		\item Further, you should write the solution in your own words. The best way to do so is to not take any notes during discussions, spend at least a few hours playing a video game or reading a novel, and then construct the solution on your own. 
	\end{itemize}
	
	\item \emph{No garbage policy:} Leaving an answer blank will get you $20\%$ of the points (this also applies to a subproblem). This does not apply to any bonus questions.
	
	\item Typed assignments are highly preferred (LaTeX or Word), especially if your handwriting is possibly illegible or if you do not have access to a good quality scanner. Please submit {\em a single PDF} on MarkUs.	
\end{enumerate}

\textbf{Total Marks:} 65 across 3 questions.

\newcommand{\calX}{\mathcal{X}}

\question{15}{Diversity}

\emph{[This is a non-technical question with no correct answer. Any reasonable answer will receive at least 80\% marks, and particularly insightful answers will receive more.]}\\[-0.2cm]

A commonly advocated position is that companies should hire employees that come from diverse backgrounds (not only in terms of race and gender, but also in terms of birthplace, educational discipline, etc.), with the argument that this will result in the AI systems developed by the companies being more ``ethical''.\\[-0.2cm]

Consider Netflix hiring employees to build a classifier, which classifies each user into ``high-value'' vs ``low-value'', depending on how much revenue Netflix is expected to make from the user over the next year. This will in turn be used for decision-making by a number of programs within Netflix (marketing, recommendations, etc.). Netflix wants the classifier to be fair with respect to gender.\\[-0.2cm] 

Describe some mechanisms by which hiring a diverse team of employees can result in the eventual classifier built being ``fairer''. For this question, do not restrict yourself to interpreting ``fairness'' as a concrete definition (e.g., equalized odds) under a specific modeling; after all, the team of employees can affect how the problem is modeled in the first place. But please do interpret ``fairness'' to still refer to the general aspect of ethics that a definition like equalized odds aims to capture. 

\newpage
\question{25}{Fair Classification}

A company designs a classifier $h : \calX \to \set{0,1}$, which takes in an input $x$ describing an applicant (e.g., their work experience, educational experience, race, gender, etc.) and outputs a binary label $y = h(x)$ indicating whether the applicant should be made an offer ($y=1$) or not ($y=0$). The company wants the classifier to be fair with respect to the gender of the applicant. For this problem, assume the company is using binary gender (M/F).\\[-0.2cm]

The ML engineering team has worked hard to gather data from 40 past applicants along with their ``true labels'', indicating whether they were truly qualified for the job. Here is a summary:

\begin{center}
\begin{tabular}{|c||c|c||c|}
    \hline
    \diagbox[width=10em]{\makebox[3em]{Gender}}{\makebox[4em]{Qualified}} & Yes & No & Total\\
    \hline\hline
    M & 16 & 12 & 28 \\
    F & 8 & 4 & 12 \\
    \hline
\end{tabular}
\end{center}

\qpart{a}{15} Eight engineers ended up designing eight different classifiers. Below, you can see the number of applicants from each of the four categories in the above table that these classifiers would make offers to in the training data. We use the abbreviation Q = qualified and U = unqualified. First, write down what demographic parity and equalized odds constraints are using fractions written in plain words such as $\frac{\text{\# of accepted QM applicants}}{\text{\# of accepted applicants}}$. Then, determine which of the following classifier satisfies each of demographic parity and equalized odds (no need to show your calculation). 

\begin{itemize}
	\item $h_1$ makes an offer to 7 QM and 3 QF applicants. No unqualified applicants are made an offer.
	\item $h_2$ makes an offer to 4 QM, 2 QF, 12 UM applicants.
	\item $h_3$ makes an offer to 4 QM, 2 QF, 9 UM, 3 UF applicants.
	\item $h_4$ makes an offer to 7 UM and 3 QF applicants.
	\item $h_5$ makes an offer to all QM and QF applicants. Like $h_1$, no unqualified applicants are made an offer.
	\item $h_6$ makes an offer to all UM and UF applicants. No qualified applicants are made an offer! 
	\item $h_7$ makes no offers.
	\item $h_8$ makes an offer to exactly half of the applicants from each of the 4 categories (QM, QF, UM, UF), thus essentially acting as a random coin flip classifier.
\end{itemize}

\qpart{b}{10} Describe all classifiers that achieve both demographic parity and equalized odds on the training data by fully characterizing the set of 4-tuples of \# of offers that can be made to applicants from the four categories (QM,QF,UM,UF). 

\question{25}{Fair Clustering}

Recall the clustering problem from class. We are given a metric space $M = (X,d)$, where $d$ is a distance metric (satisfying the triangle inequality) over a set of points $X$, a set of $P \subseteq X$ with $|P| = n$, and a desired number of cluster centers $k$. Our goal is to find the set of locations $C \subseteq X$ of $|C| = k$ cluster centers. Once $C$ is chosen, each data point $x \in P$ is assigned to its nearest cluster center (pardon the slight abuse of notation) $C(x) = \arg\min_{c \in C} d(x,c)$.\\[-0.2cm] 

Recall that a clustering $C$ is said to be in the $\alpha$-core if there is no set of data points $S \subseteq P$ with $|S| \ge n/k$ and a new center $c' \in X$ such that $\alpha \cdot d(x,c') < d(x,C(x))$ for all $x \in S$.\\[-0.2cm]

Recall the Greedy Capture algorithm: it grows balls at each point in $X$ simultaneously and with equal speed. As soon as any ball captures at least $n/k$ data points from $P$, its center $c$ is added to $C$. Subsequently, any data point captured by an already existing ball centered at a location in $C$ is assigned to that ball, and for any new $c'$ to be added to $C$, its ball must capture at least $n/k$ data points from $P$ that are not already captured by any ball centered at any location in $C$. The process terminates when all the points in $P$ are captured. In class, you saw a proof that Greedy Capture satisfies $(1+\sqrt{2})$-core for any metric.

\qpart{a}{15} Prove that it satisfies $2$-core for the metric $(\bbR^p, d=L^2)$ (i.e., $L^2$ norm in the $p$-dimensional Euclidean space) for any $p$. For this, assume the following fact about this metric: For any $x,y \in \bbR^p$, the set of points $\set{z \in \bbR^p : 2 \cdot d(z,y) \le d(z,x)}$ is a ball of radius $(\nicefrac{2}{3}) \cdot  d(x,y)$.\\[-0.2cm]

\emph{[Hint: Suppose for contradiction that the clustering returned is not in $2$-core, so there exists a violation $S,c'$ as per the definition. Let $i \in S$ be the first point of $S$ that was captured (say, by a ball centered at $c \in C$) during the execution of Greedy Capture. Use the fact provided to find a ball of radius less than $(\nicefrac{2}{3}) \cdot  d(c,c')$ that must contain all of $S$. Prove $(\nicefrac{2}{3}) \cdot d(c,c') < d(i,c)$ to derive a contradiction.]}

\qpart{b}{10} Now, consider the metric $(\bbR^2,d=L^1)$ (i.e., $L^1$ norm in the $2$-dimensional Euclidean space). Consider the following $7$ points:

\begin{minipage}[c]{0.6\textwidth}
\begin{align*}
p_1 = (0, 1), p_2 = (1, 0), p_3 = (0, -1), p_4 = (-1, 0),\\
p_5 = (0, \sqrt{2}), p_6 = (1+\epsilon,\sqrt{2}), p_7 = (-1-\epsilon,\sqrt{2}).
\end{align*}
\end{minipage}%
\begin{minipage}[c]{0.4\textwidth}
\begin{tikzpicture}[scale=1.5]
    % Points
    \coordinate (p1) at (0,1);
    \coordinate (p2) at (1,0);
    \coordinate (p3) at (0,-1);
    \coordinate (p4) at (-1,0);
    \coordinate (p5) at (0,{sqrt(2)});
    \coordinate (p6) at (1.2,{sqrt(2)});
    \coordinate (p7) at (-1.2,{sqrt(2)});
    
    % Axes
    \draw[->] (-1.5,0) -- (1.5,0) node[right] {$x$};
    \draw[->] (0,-1.5) -- (0,2) node[above] {$y$};
    
    % Points
    \foreach \point/\label in {p1/1, p2/2, p3/3, p4/4, p5/5, p6/6, p7/7} {
        \fill (\point) circle (1pt) node[above right] {$p_{\label}$};
    }
    
    % Epsilon
    \draw[<->] (1,0.8) -- node[above] {$\varepsilon$} (1.2,0.8);
    \draw[<->] (-1.2,0.8) -- node[above] {$\varepsilon$} (-1,0.8);
\end{tikzpicture}
\end{minipage}

\medskip 
Consider an instance with $n=28$ points divided into four sets of $7$ points, each set isomorphic to the set of $7$ points above, and each set located sufficiently far from all the other sets. Let $k=7$. Prove that the approximation ratio to the core achieved by Greedy Capture on this instance is $1+\sqrt{2}$ as $\epsilon \to 0$. That is, the improvement we see for $L^2$ in part (a) does not apply to $L^1$.\\[-0.2cm] 

\emph{[Hint: There will be one of the four sets of points where Greedy Capture will only place one cluster center at its $(0,0)$. In this set of points, find four that can deviate and be significantly better.]}
\end{document}

