From f292c5a0e54c010bb7a00586a6e3c1b14831a5bc Mon Sep 17 00:00:00 2001
From: Yigit Sever
Date: Sat, 7 Nov 2020 03:38:07 +0300
Subject: Polish question 2

---
 main.tex | 34 +++++++++++++++++++++++-----------
 1 file changed, 23 insertions(+), 11 deletions(-)

diff --git a/main.tex b/main.tex
index 3778cd4..21235f0 100644
--- a/main.tex
+++ b/main.tex
@@ -304,7 +304,7 @@ We have implemented \emph{Gale-Shapley} and an instance set creation script to t
 \section{Stable Matching Variation}%
 \label{sec:stable_matching_variation}
 
-% stable matching question ALMOST {{{1 %
+% stable matching question ✅ {{{1 %
 
 \begin{question}
     Consider a Stable Matching problem with men and women.
@@ -313,12 +313,15 @@ We have implemented \emph{Gale-Shapley} and an instance set creation script to t
     Either give a proof that shows such an improvement is impossible, or give an example preference list for which an improvement for $w$ is possible.
 \end{question}
 
-Example preference list for men; $M = {x,y,z}$ and women: $W = {a,b,c}$.
+We will give an example instance.
+Let's take the example preference list for men; $M = {x,y,z}$ and women: $W = {a,b,c}$.
 
 \begin{table}[!htb]
-    \caption{Preference lists of women.}
+    \caption{Preference lists of women}%
+    \label{table:2_general}
     \begin{minipage}{.5\linewidth}
-        \caption{Everyone is being truthful}
+        \caption{Everyone is being truthful}%
+        \label{table:2_true}
         \centering
         \begin{tabular}{l|lll}
             \textbf{a} & y & x & z \\
@@ -328,19 +331,22 @@ Example preference list for men; $M = {x,y,z}$ and women: $W = {a,b,c}$.
     \end{minipage}%
     \begin{minipage}{.5\linewidth}
         \centering
-        \caption{a is lying about their preference}
+        \caption{a is lying about their preference}%
+        \label{table:2_lie}
         \begin{tabular}{l|lll}
             \textbf{a} & y & z & x \\
             \textbf{b} & x & y & z \\
             \textbf{c} & x & y & z
         \end{tabular}
         \begin{tikzpicture}[overlay]
-         \draw[red, line width=1pt] (-0.72,0.52) ellipse (0.70cm and 0.2cm);
+            \draw[red, line width=1pt] (-0.72,0.52) ellipse (0.70cm and 0.2cm);
         \end{tikzpicture}
     \end{minipage}
 \end{table}
 
-% TODO: final polish, highlight the lies <06-11-20, yigit> %
+In the example given above in Table~\ref{table:2_general}, we have two cases for women, Table~\ref{table:2_true} where everyone has given their actual preference list and Table~\ref{table:2_lie} where $a$ has lied about their \nth{2} and \nth{3} preferences.
+
+The following is the men's preference table;
 
 \begin{table}[htb]
     \centering
@@ -353,7 +359,7 @@ Example preference list for men; $M = {x,y,z}$ and women: $W = {a,b,c}$.
     \label{tab:men_pref}
 \end{table}
 
-The trace of \emph{Gale-Shapley} algorithm for the truth telling case;
+The trace of \emph{Gale-Shapley} algorithm for the truth telling case with Table~\ref{table:2_true} and Table~\ref{tab:men_pref} is below;
 
 \begin{enumerate}
     \item Matching x with a (a)
@@ -363,30 +369,36 @@ The trace of \emph{Gale-Shapley} algorithm for the truth telling case;
     \item Matching z with c (a)
 \end{enumerate}
 
+Which produces the following matching. Note that $a$ is matched with their \nth{2} choice.
+
 \begin{align*}
     x &\rightarrow a \\
     y &\rightarrow b \\
     z &\rightarrow c
 \end{align*}
 
-The trace of \emph{Gale-Shapley} algorithm when \emph{a} lies about their preferences;
+Now let's examine the trace of the algorithm when $a$ lies by providing an altered preference table. The trace below uses Table~\ref{table:2_lie} and Table~\ref{tab:men_pref};
 
 \begin{enumerate}
     \item Matching y with b (a)
     \item Matching z with a (a)
-    \item x proposes to a but gets rejected because a prefers z more (c)
+    \item \textbf{x proposes to a but gets rejected because a lies by saying that they like z more (c)}
     \item Matching x with b, y is now free (b)
-    \item Matching y with a, z is now free (b)
+    \item \textbf{Matching y with a, z is now free (b)}
     \item z proposes to b but gets rejected because b prefers x more (c)
     \item Matching z with c (a)
 \end{enumerate}
 
+The highlighted lines show that $a$ lies when proposed by $x$ and then is able to trade up to $y$. The following it the final matching;
+
 \begin{align*}
     x &\rightarrow b \\
     y &\rightarrow a \\
     z &\rightarrow c
 \end{align*}
 
+Woman $a$ was able to get their highest preferred option $y$ by telling a lie. We have proved that an improvement is possible.
+
 % 1}}} %
 
 \section{Asymptotics}%
-- 
cgit v1.2.3-70-g09d2