main.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Masters/Doctoral Thesis 
% LaTeX Template
% Version 2.5 (27/8/17)
%
% This template was downloaded from:
% http://www.LaTeXTemplates.com
%
% Version 2.x major modifications by:
% Vel (vel@latextemplates.com)
%
% This template is based on a template by:
% Steve Gunn (http://users.ecs.soton.ac.uk/srg/softwaretools/document/templates/)
% Sunil Patel (http://www.sunilpatel.co.uk/thesis-template/)
%
% Template license:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass[
11pt, % The default document font size, options: 10pt, 11pt, 12pt
%oneside, % Two side (alternating margins) for binding by default, uncomment to switch to one side
english, % ngerman for German
doublespacing, % line spacing, alternatives: singlespacing, onehalfspacing or doublespacing
%draft, % Uncomment to enable draft mode (no pictures, no links, overfull hboxes indicated)
%nolistspacing, % If the document is onehalfspacing or doublespacing, uncomment this to set spacing in lists to single
%liststotoc, % Uncomment to add the list of figures/tables/etc to the table of contents
%toctotoc, % Uncomment to add the main table of contents to the table of contents
%parskip, % Uncomment to add space between paragraphs
%nohyperref, % Uncomment to not load the hyperref package
headsepline, % Uncomment to get a line under the header
%chapterinoneline, % Uncomment to place the chapter title next to the number on one line
%consistentlayout, % Uncomment to change the layout of the declaration, abstract and acknowledgements pages to match the default layout
]{MastersDoctoralThesis} % The class file specifying the document structure

\usepackage[utf8]{inputenc} % Required for inputting international characters
\usepackage[T1]{fontenc} % Output font encoding for international characters

\usepackage{mathpazo} % Use the Palatino font by default

\usepackage[backend=bibtex,style=authoryear,natbib=true]{biblatex} % Use the bibtex backend with the authoryear citation style (which resembles APA)
\addbibresource{bibs/example,bibs/bib_game,bibs/bib_tech,bibs/bib_mcts,bibs/bib_moba,bibs/bib_mywork,bibs/bib_rl,bibs/bib_eomm,bibs/bib_dda,bibs/bib_churn,bibs/bib_recom,bibs/bib_ethical} % The filename of the bibliography
% \bibliographystyle{apalike}


\usepackage[autostyle=true]{csquotes} % Required to generate language-dependent quotes in the bibliography

\usepackage{xcolor}
%\pagecolor{lightgray!40}
\usepackage{ifdraft}
% \ifoptionfinal{}{\pagecolor[HTML]{FDF6E3}}
% \ifoptionfinal{}{\pagecolor[HTML]{F8DF9C}}
% \ifoptionfinal{}{\pagecolor[HTML]{cac4b5}}

% math
\usepackage{amsmath,amssymb,amsfonts}

% For highlighting
\usepackage{color,soul}

% table row spacing
\newcommand{\ra}[1]{\renewcommand{\arraystretch}{#1}}

% For bold vectors
\newcommand{\vect}[1]{\boldsymbol{#1}}

% For argmax
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}

% merge cell vertically in table
\usepackage{multirow}

% itermize no left margin
\usepackage{enumitem}

% For algorithms
\usepackage[ruled]{algorithm2e} 

% URL line break but doesn't work all the time
\usepackage{etoolbox}
\appto\UrlBreaks{\do\-}

% adjustwidth in table for over wide tables
% see https://stackoverflow.com/questions/722613/centering-a-table-wider-than-the-text-column
\usepackage{chngpage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                 hyperlink for whole citation                    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\DeclareCiteCommand{\cite}
  {\usebibmacro{prenote}}
  {\usebibmacro{citeindex}%
   \printtext[bibhyperref]{\usebibmacro{cite}}}
  {\multicitedelim}
  {\usebibmacro{postnote}}

\DeclareCiteCommand*{\cite}
  {\usebibmacro{prenote}}
  {\usebibmacro{citeindex}%
   \printtext[bibhyperref]{\usebibmacro{citeyear}}}
  {\multicitedelim}
  {\usebibmacro{postnote}}

\DeclareCiteCommand{\parencite}[\mkbibparens]
  {\usebibmacro{prenote}}
  {\usebibmacro{citeindex}%
    \printtext[bibhyperref]{\usebibmacro{cite}}}
  {\multicitedelim}
  {\usebibmacro{postnote}}

\DeclareCiteCommand*{\parencite}[\mkbibparens]
  {\usebibmacro{prenote}}
  {\usebibmacro{citeindex}%
    \printtext[bibhyperref]{\usebibmacro{citeyear}}}
  {\multicitedelim}
  {\usebibmacro{postnote}}

\DeclareCiteCommand{\footcite}[\mkbibfootnote]
  {\usebibmacro{prenote}}
  {\usebibmacro{citeindex}%
  \printtext[bibhyperref]{ \usebibmacro{cite}}}
  {\multicitedelim}
  {\usebibmacro{postnote}}

\DeclareCiteCommand{\footcitetext}[\mkbibfootnotetext]
  {\usebibmacro{prenote}}
  {\usebibmacro{citeindex}%
   \printtext[bibhyperref]{\usebibmacro{cite}}}
  {\multicitedelim}
  {\usebibmacro{postnote}}

\DeclareCiteCommand{\textcite}
  {\boolfalse{cbx:parens}}
  {\usebibmacro{citeindex}%
   \printtext[bibhyperref]{\usebibmacro{textcite}}}
  {\ifbool{cbx:parens}
     {\bibcloseparen\global\boolfalse{cbx:parens}}
     {}%
   \multicitedelim}
  {\usebibmacro{textcite:postnote}}
%---------------------------------------------------------------------------


%----------------------------------------------------------------------------------------
%	MARGIN SETTINGS
%----------------------------------------------------------------------------------------

\geometry{
	paper=a4paper, % Change to letterpaper for US letter
	inner=2.5cm, % Inner margin
	outer=3.8cm, % Outer margin
	bindingoffset=.5cm, % Binding offset
	top=1.5cm, % Top margin
	bottom=1.5cm, % Bottom margin
	%showframe, % Uncomment to show how the type block is set on the page
}

%---------------------------------------------------------------------------------------
%	THESIS INFORMATION
%----------------------------------------------------------------------------------------

% I don't want to say my thesis is just adaptation techniques. Adaptation techniques

% original: Pre-Match Recommendations for Influencing Match Outcomes and Player Engagement in Video Games
\thesistitle{Recommendation Systems for Influencing Player Competence and Engagement in Match-Based Games} % Your thesis title, this is used in the title and abstract, print it elsewhere with \ttitle
\supervisor{Magy Seif El-Nasr (Advisor)} % Your supervisor's name, this is used in the title page, print it elsewhere with \supname
\supervisorone{Christopher Amato}
\supervisortwo{Seth Cooper}
\supervisorthree{Yizhou Sun}
\examiner{} % Your examiner's name, this is not currently used anywhere in the template, print it elsewhere with \examname
\degree{Doctor of Philosophy} % Your degree name, this is used in the title page and abstract, print it elsewhere with \degreename
\author{Zhengxing Chen} % Your name, this is used in the title page and abstract, print it elsewhere with \authorname
\addresses{} % Your address, this is not currently used anywhere in the template, print it elsewhere with \addressname

\subject{Computer Sciences} % Your subject area, this is not currently used anywhere in the template, print it elsewhere with \subjectname
\keywords{} % Keywords for your thesis, this is not currently used anywhere in the template, print it elsewhere with \keywordnames
\university{Northeastern University} % Your university's name and URL, this is used in the title page and abstract, print it elsewhere with \univname
\department{College of Information and Computer Science} % Your department's name and URL, this is used in the title page and abstract, print it elsewhere with \deptname
\group{Research Group Name} % Your research group's name and URL, this is used in the title page, print it elsewhere with \groupname
\faculty{faculty name} % Your faculty's name and URL, this is used in the title page and abstract, print it elsewhere with \facname

\AtBeginDocument{
\hypersetup{pdftitle=\ttitle} % Set the PDF's title to your title
\hypersetup{pdfauthor=\authorname} % Set the PDF's author to your name
\hypersetup{pdfkeywords=\keywordnames} % Set the PDF's keywords to your keywords
}

\begin{document}

\frontmatter % Use roman page numbering style (i, ii, iii, iv...) for the pre-content pages

\pagestyle{plain} % Default to the plain heading style until the thesis style is called for the body content

%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\begin{titlepage}
\begin{center}

%\vspace*{.06\textheight}
{\scshape\LARGE \univname\par}\vspace{0.5cm} % University name
\textsc{\Large Doctoral Dissertation}\\[0.5cm] % Thesis type

\HRule \\[0.4cm] % Horizontal line
{\huge \bfseries \ttitle\par}\vspace{0.4cm} % Thesis title
\HRule \\[1.5cm] % Horizontal line
 
\begin{minipage}[t]{0.4\textwidth}
\begin{flushleft} \large
\emph{Author:}\\
{\authorname} % Author name - remove the \href bracket to remove the link
\end{flushleft}
\end{minipage}
\begin{minipage}[t]{0.4\textwidth}
\begin{flushright} \large
\emph{Committee:} \\
{\supname} \\ % Supervisor name - remove the \href bracket to remove the link  
{\supnameone} \\
{\supnametwo} \\ 
{\supnamethree} 
\end{flushright}
\end{minipage}\\[3cm]
 
\vfill

\large \textit{A dissertation submitted in fulfillment of the requirements\\ for the degree of \degreename}\\[0.3cm] % University requirement text
\textit{in the}\\[0.4cm]
\deptname\\\univname\\[2cm] % department name and university name
 
\vfill

{\large \today}\\[4cm] % Date
%\includegraphics{Logo} % University/department logo - uncomment to place it
 
\vfill
\end{center}
\end{titlepage}

%----------------------------------------------------------------------------------------
%	DECLARATION PAGE
%----------------------------------------------------------------------------------------

\begin{declaration}
\addchaptertocentry{\authorshipname} % Add the declaration to the table of contents
\noindent I, \authorname, declare that this dissertation titled, \enquote{\ttitle} and the work presented in it are my own. I confirm that:

\begin{itemize} 
\item This work was done wholly or mainly while in candidature for a research degree at this University.
\item Where any part of this dissertation has previously been submitted for a degree or any other qualification at this University or any other institution, this has been clearly stated.
\item Where I have consulted the published work of others, this is always clearly attributed.
\item Where I have quoted from the work of others, the source is always given. With the exception of such quotations, this dissertation is entirely my own work.
\item I have acknowledged all main sources of help.
\item Where the dissertation is based on work done by myself jointly with others, I have made clear exactly what was done by others and what I have contributed myself.\\
\end{itemize}
 
\noindent Signed:\\
\rule[0.5em]{25em}{0.5pt} % This prints a line for the signature
 
\noindent Date:\\
\rule[0.5em]{25em}{0.5pt} % This prints a line to write the date
\end{declaration}

\cleardoublepage

%----------------------------------------------------------------------------------------
%	QUOTATION PAGE
%----------------------------------------------------------------------------------------

% \vspace*{0.2\textheight}

% \noindent\enquote{\itshape Thanks to my solid academic training, today I can write hundreds of words on virtually any topic without possessing a shred of information, which is how I got a good job in journalism.}\bigbreak

% \hfill Dave Barry

%----------------------------------------------------------------------------------------
%	ABSTRACT PAGE
%----------------------------------------------------------------------------------------

\begin{abstract}
\addchaptertocentry{\abstractname} % Add the abstract to the table of contents

For years, video games have garnered the attention of people worldwide, providing a unique environment for entertainment, education, scientific problem solving, promotion of health awareness, and socialization. With the increase of video games' popularity, a critical question arises: how do we keep a player engaged?   

In this dissertation, I focused on increasing player engagement, where I define engagement as the continued desire to play a game repeatedly during one session or over a longer period of time. I proposed three recommendation systems targeting different types of in-game elements. I focused on online match-based games, where players competitively play against others. Further, I focused on recommendations in the pre-match stage. My hypothesis is that the recommendation systems I developed will increase player engagement by giving players the ability to make informed choices concerning in-game elements, such as which characters to play as, which items to equip, or which opponents to play against. My theoretical foundation for this work is based on two psychological theories that have shaped understanding of player sustained engagement in games: Self Determination and Flow. In such theories, scholars have shown that competence, or the ability of a player to feel competent given the tasks they are doing within the game, has a direct relation to sustained engagement, or the desire to play the game repeatedly, Additionally, Flow theory describes a state of 'flow' where players are sufficiently challenged, where the task they are doing is neither too easy or too hard. Based on these theories, the recommendation systems I proposed recommend in-game elements to players that influence players' in-game choices, and subsequently will have an impact on the way they play, competence they perceive, and eventually their engagement. 

To develop these recommendation systems, I explored two related research questions. The first research question is concerned with the question of how to develop effective and efficient recommendation systems that can recommend in-game elements that will have a winning potential for players, in both one-vs-one and team-vs-team settings. Targeting this question allows us to focus on developing experiences that are not frustratingly hard to players, and thus help players win more. It should be noted that these systems can also work in reverse, meaning they can also suggest items that make players lose. The second research question is concerned with studying how to balance win/loss of matches through designing in-game element recommendation systems which directly improve player engagement in relation to win/loss ratio and its impact on churn.

For the first research question I proposed two systems: (a) \textit{Q-DeckRec} a recommendation system for one-vs-one Collectible Card Games (CCGs). In these types of games, the player often starts with a deck of cards of their choice. Q-DeckRec recommends winning-effective decks. This system presents a novel approach to search a large space of possible card decks to recommend, using minimal computational resources after a training phase. In addition to cards as starting items to recommend, many games such as MOBA (Multi-player Online Battle Arena) games require players to select a set of characters to play with against another team. For these types of games, I proposed (b) \textit{DraftArtist}, a recommendation system that recommends winning-effective characters. This proposed system presents a novel contribution that efficiently searches for the best possible characters to recommend given a large number of possibilities, uncertainty caused by not knowing what the other team will select, and the desirability to select characters that synergize teammates and counter the opponents. Using a match outcome prediction model trained on real data, we find that teams following our recommendation algorithm have higher predicted win rates against teams constructed by other character selection strategies. Our algorithm maintains sufficient efficiency to be deployed in real-world scenarios.

For the second research question, I proposed an opponent recommendation system, called \textit{Engagement-Optimized Matchmaking} (EOMM). EOMM is the first system that formally treated matchmaking as an optimization problem to maximize player engagement quantitatively. Our system shows significant improvement in enhancing population-wise player engagement as compared to other matchmaking methods.

The contribution of my dissertation is in developing three novel recommendation systems that target improving player engagement through increasing competence by giving players in-game element recommendation that increase possibility of a players feeling competent or entering a state of Flow by either increasing the probability of them winning or balancing the win/loss ratio to decrease the probability that they leave the game. There are much work left for future research, such as studying systems tailored for more specific types of in-game elements, as well as those which can make central decisions on different types of recommendations for any particular player.


% Such variety and richness     match outcomes are believed to be closely related to player engagement and revenues made by game companies. Based on individual players' information and game contexts, personalized recommendation is one family of proposed methods, wherein dynamic game contents are recommended to players in order to influence their win rates. 

% investigating the close relationship in-game competence and player engagement. 

% As there can be various goals for influencing game outcomes and video games sport different designs and in-game elements, I am not able to examine every place where in-game element recommendation can be applied. Rather, I focus on the following boundaries delimiting my research.

% thus Q-DeckRec is designed to be suitable for large-scale or real-time recommendation application.

% i.e., the level of player competence manipulation is directly linked to player engagement. 

% in which an optimization objective is designed to arbitrate the strength of competence manipulation for every player and benefit the overall engagement as the end goal. Specifically, 

%  and in most cases they passively accept what they are matched with

% \linebreak 

% Particularly, I study how to design recommendation systems for the optimization of population-wise player engagement.
% * <czxttkl@gmail.com> 2018-07-25T10:02:11.856Z:
%
% ^.
% * <czxttkl@gmail.com> 2018-07-25T10:02:09.838Z:
%
% ^.

% EOMM presents a new way of thinking opponent recommendation as an optimization problem which can be solved through a graph matching algorithm. 

% The connections between the three proposed recommendation systems are as follows. All the systems use recommendations as a means to influence game outcomes. They can be indirectly or directly used to improve player engagement. The starting item and character recommendation systems aim for increasing the win rate for one player, which can be seen as an indirect step to improve player engagement because they need to work with other systems which decide when to deliver recommendations, while EOMM directly operates on the optimization of population-wise player engagement as the criterion for influencing game outcomes for multiple players.

% In each match, human players (and possibly computer agents) compete with each other.
% First, I focus on recommendations in the pre-match stage in video games played based on small sessions called matches. In the pre-match stage, some in-game elements determined before the match starts could already have an impact on the final match outcome and player engagement.
% Second, I focus on two goals for employing recommendations to influence game outcomes: to increase a player's win rate and to increase player engagement. The two goals are progressive, in a sense that increasing a player's win rate is an intermediate and indirect step to improve player engagement.
% Third, I focus on the recommendations of three specific types of in-game elements: starting items, in-game characters and opponents. These are very common in-game elements in video games nowadays. However, identifying right recommendations of them face different challenges: (1) I propose  personalized recommendation system for suggesting starting items  to optimal for a player's win rate. It could be a challenging task for the player to choose winning-effective starting items since a large amount of choices could be available depending on the strategies of the player and the opponent; (2) I propose an in-game character recommendation system for suggesting team-based video games with the goal to maximize a player's win rate.Last, I propose a matchmaking system for opponent recommendation, in which expected match outcomes within recommended opponents optimize all involved players' engagement. 

% A distinctive feature of personalized recommendation in PvP games is that influencing one's winning probability will adversely change that of the opponent(s) who are human players too. The initial item recommendation system exemplifies \textit{how} match outcomes can be affected positively \textit{from one side}, while the opponent recommendation system exemplifies not only \textit{how} but also \textit{how much} match outcomes should be influenced when we consider \textit{a population of players}.



\end{abstract}

%----------------------------------------------------------------------------------------
%	ACKNOWLEDGEMENTS
%----------------------------------------------------------------------------------------

\begin{acknowledgements}
\addchaptertocentry{\acknowledgementname} % Add the acknowledgements to the table of contents
I would like to thank my advisor Prof. Magy Seif El-Nasr for her patience, motivation, and knowledge. I could not forget our first meeting where she shed lights on game analytics and encouraged me to take on this direction. Without her support over the last five years, I could never have been so fortunate to carve a niche in the interdisciplinary research area of video games and artificial intelligence.

My sincere thanks also go to my dissertation committee members: Prof. Christopher Amato, Prof. Yizhou Sun, and Prof. Seth Cooper. They provided me with enormous helps and inspired my research in diverse perspectives. 

I am grateful to all collaborators I worked with during my research as well as colleagues I met during my internships at Electronic Arts, eBay, Google, and Facebook. My special gratefulness goes to Prof. Truong-Huy Nguyen for suggesting me PhD and life advice, and Dr. Su Xue and Dr. John Kolen for fostering my incredible internship experience at Electronic Arts.

I thank Prof. Karl Lieberherr and Prof. Stephen Intille for their kind helps in the first year of my PhD. I also thank all my friends and lab mates for their support, understanding, and encouragement.

I cannot thank more than enough to my parents and grandparents, who have taught me to become kind, strong, and wise throughout my whole life.

Last but by no means least, I would like to express my thankfulness to my wife, Shiyun, for accompanying me through the so far most challenging yet most memorable time in my life. We will have much more adventure to experience in the future.
\end{acknowledgements}

%----------------------------------------------------------------------------------------
%	LIST OF CONTENTS/FIGURES/TABLES PAGES
%----------------------------------------------------------------------------------------

\tableofcontents % Prints the main table of contents

\listoffigures % Prints the list of figures

\listoftables % Prints the list of tables

% %----------------------------------------------------------------------------------------
% %	ABBREVIATIONS
% %----------------------------------------------------------------------------------------

% \begin{abbreviations}{ll} % Include a list of abbreviations (a table of two columns)

% \textbf{LAH} & \textbf{L}ist \textbf{A}bbreviations \textbf{H}ere\\
% \textbf{WSF} & \textbf{W}hat (it) \textbf{S}tands \textbf{F}or\\

% \end{abbreviations}

% %----------------------------------------------------------------------------------------
% %	PHYSICAL CONSTANTS/OTHER DEFINITIONS
% %----------------------------------------------------------------------------------------

% \begin{constants}{lr@{${}={}$}l} % The list of physical constants is a three column table

% % The \SI{}{} command is provided by the siunitx package, see its documentation for instructions on how to use it

% Speed of Light & $c_{0}$ & \SI{2.99792458e8}{\meter\per\second} (exact)\\
% %Constant Name & $Symbol$ & $Constant Value$ with units\\

% \end{constants}

% %----------------------------------------------------------------------------------------
% %	SYMBOLS
% %----------------------------------------------------------------------------------------

% \begin{symbols}{lll} % Include a list of Symbols (a three column table)

% $a$ & distance & \si{\meter} \\
% $P$ & power & \si{\watt} (\si{\joule\per\second}) \\
% %Symbol & Name & Unit \\

% \addlinespace % Gap to separate the Roman symbols from the Greek

% $\omega$ & angular frequency & \si{\radian} \\

% \end{symbols}

% %----------------------------------------------------------------------------------------
% %	DEDICATION
% %----------------------------------------------------------------------------------------

% \dedicatory{For/Dedicated to/To my\ldots} 

%----------------------------------------------------------------------------------------
%	THESIS CONTENT - CHAPTERS
%----------------------------------------------------------------------------------------

\mainmatter % Begin numeric (1,2,3...) page numbering

\pagestyle{thesis} % Return the page headers back to the "thesis" style

% Include the chapters of the thesis as separate files from the Chapters folder
% Uncomment the lines as you write the chapters

\include{Chapters/Chapter_intro}
\include{Chapters/Chapter_relatework}
\include{Chapters/Chapter_qdeckrec}
\include{Chapters/Chapter_draftart}
\include{Chapters/Chapter_eomm} 
\include{Chapters/Chapter_application}
\include{Chapters/Chapter_future}
\include{Chapters/Chapter_conclusion}
% \include{Chapters/Chapter_format} 


%----------------------------------------------------------------------------------------
%	THESIS CONTENT - APPENDICES
%----------------------------------------------------------------------------------------

\appendix % Cue to tell LaTeX that the following "chapters" are Appendices

% Include the appendices of the thesis as separate files from the Appendices folder
% Uncomment the lines as you write the Appendices

% \include{Appendices/AppendixA}
%\include{Appendices/AppendixB}
%\include{Appendices/AppendixC}

%----------------------------------------------------------------------------------------
%	BIBLIOGRAPHY
%----------------------------------------------------------------------------------------

\printbibliography[heading=bibintoc]

%----------------------------------------------------------------------------------------

\end{document}