Equilibria Under the Probabilistic Serial Rule
Paper 101
Haris Aziz
Serge Gaspers
Simon Mackenzie
Nicholas Mattei
NICTA and UNSW
Sydney
Australia
\{haris.aziz
serge.gaspers
simon.mackenzie
nicholas.mattei\
The probabilistic serial (PS) rule is a prominent randomized rule for assigning indivisible goods to agents. Although it is well known for its good fairness and welfare properties, it is not strategyproof. In view of this, we address several fundamental questions regarding equilibria under PS. Firstly, we show that Nash deviations under the PS rule can cycle. Despite the possibilities of cycles, we prove that a pure Nash equilibrium is guaranteed to exist under the PS rule. We then show that verifying whether a given profile is a pure Nash equilibrium is coNP-complete, and computing a pure Nash equilibrium is NP-hard. For two agents, we present a linear-time algorithm to compute a pure Nash equilibrium which yields the same assignment as the truthful profile. Finally, we conduct experiments to evaluate the quality of the equilibria that exist under the PS rule, finding that the vast majority of pure Nash equilibria yield social welfare that is at least that of the truthful profile.
pseq.tex
\documentclass{article}
% The file ijcai15.sty is the style file for IJCAI-15 (same as ijcai07.sty).
\usepackage{ijcai15}

% Use the postscript times font!
\usepackage{times}
\frenchspacing
\setlength{\pdfpagewidth}{8.5in}
\setlength{\pdfpageheight}{11in}



%%% non-AAAI starts here
% \usepackage{tikz}
% \usetikzlibrary{arrows}
% \usepackage{centernot}
% \usetikzlibrary{decorations.pathreplacing}
% \usetikzlibrary{patterns}
\usepackage[boxed]{algorithm}
\usepackage[noend]{algorithmic}
\usepackage{paralist}
% \usepackage[textsize=scriptsize]{todonotes}
% \presetkeys{todonotes}{inline}{}
\usepackage[centertags,fleqn]{amsmath}
\usepackage{amssymb,amsthm,xspace}
\usepackage{booktabs}
% \usepackage{theorem}
\usepackage{nicefrac}
\usepackage{tabularx}
\usepackage{mathtools}
\usepackage{paralist}
\usepackage{balance}

\usepackage[textwidth=15mm,textsize=footnotesize]{todonotes}

% \usepackage{eqparbox}
% \newcommand{\myproof}{\noindent {\bf Proof:\ \ }}
% \newcommand{}{\mbox{$\qed$}}
% \newtheorem{mytheorem}{Theorem}
% \newtheorem{question}{Question}
% \newtheorem{myconjecture}{Conjecture}
\newtheorem{observation}{Observation}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}
% \newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{example}{Example}
\newtheorem{remark}{Remark}
% \newtheorem{conjecture}{Conjecture}
% \newtheorem{fact}{Fact}
% \newcommand{\qed}{\unskip\hspace*{1em}\hspace{\fill}$\Box$}
% \newenvironment{proof}[1][Proof]{\begin{trivlist}
%   \item[\hskip \labelsep {\it #1:}]}{%
%     \qed\end{trivlist}}


\newcommand{\egal}{\ensuremath{ESR}\xspace}
\newcommand{\sr}{\ensuremath{SR}\xspace}
\newcommand{\oldegal}{\ensuremath{OldESR}\xspace}
\newcommand{\propegal}{\ensuremath{PropESR}\xspace}
\newcommand{\guar}{\ell}
			
		
\renewcommand{\algorithmiccomment}[1]{\hfill\% #1}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}
\algsetup{linenodelimiter=\,}
\algsetup{linenosize=\tiny}
\algsetup{indent=2em}
		
\newcommand{\eg}{e.g.,\xspace}

	

	\usepackage{subfig}
	\usepackage{colortbl,color,array,hhline}
	% \usepackage{bbm,dsfont}
	\usepackage{tikz}
	%\usepackage{pgfmath}
	\usetikzlibrary{arrows}
	\usetikzlibrary{decorations.pathreplacing}
	%\usepackage[landscape]{geometry}
	\usepackage{lscape}


	\DeclareSymbolFont{largesymbolsA}{U}{txexa}{m}{n}
	%\DeclareMathSymbol{\varprod}{\mathop}{largesymbolsA}{"10}

	\usepackage{amsmath,amssymb,amsfonts}

	\usetikzlibrary{arrows}
	\usetikzlibrary{decorations.pathreplacing}
	\usetikzlibrary{patterns}

	% Preference PROFILE definitions....NM
	\newcommand{\pref}{\succ \xspace}
	\newcommand{\preffn}[2]{\; \pref_{#1}\!\!\!({#2}) \xspace}

	\newcommand{\prefinv}{\succ^{-1} \xspace}
	\newcommand{\prefinvfn}[2]{\; \pref^{-1}_{#1}\!\!({#2})}

	\newcommand{\prefcloned}{\succ^{\textsc{cloned}} \xspace}
	%\newcommand{\prefclonedbest}{\succ^{\textsc{clonedBest}} \xspace}

	\newcommand{\hclone}{H^{\textsc{cloned}} \xspace}

	\newcommand{\prefbest}{\pref^{\textsc{best}}}
	\newcommand{\prefbestfn}[2]{\; \pref^{\textsc{best}}_{#1}\!\!\!({#2})}

	\newcommand{\bestalloc}{\textsc{Best-Alloc}}

	\newcommand{\prefclonedbest}{\succ^{\textsc{cloned-best}} \xspace}


	\newcommand{\Indiff}[1][]{
		\ifthenelse{\equal{#1}{}}{\mathrel I}{\mathop{I_{#1}}}
	}
	\newcommand{\prefset}[1][]{\ifthenelse{\equal{#1}{}}{\mathcal{R}}{\mathcal{R}_{#1}}}
	\newcommand{\strictpref}{\mathbin P\xspace}
	\newcommand{\indiff}{\mathbin I\xspace}

	%\newcommand{\instance}[1]{\emph{Instance}&\parbox[t]{.37\textwidth}{#1}\\[.3ex]}
	% 
	% \newcommand{\Input}[1]{\textbf{Input}:&\parbox[t]{.4\textwidth}{
	% #1}\\}
	% \newcommand{\Output}[1]{\textbf{Output}:&
	% \parbox[t]{.4\textwidth}{
	% #1}}
	\newcommand{\allocM}{\mathcal H\xspace}


	% \newcommand{\nooutput}{\texttt{none}}

	% end Macros

	\usepackage{enumitem}
	\setenumerate[1]{label=\rm(\it{\roman{*}}\rm),ref=({\it\roman{*}}),leftmargin=*}

	%%% General notation
	% \renewcommand{\mathscr}[1]{\mathcal{#1}}

	%\newcommand{\midd}{\mathrel{:}}
	\newcommand{\sepp}{\mathrel{|}}


	% HEADER END

	% \usepackage{calrsfs}
	\usepackage[mathcal]{euscript}





		\newcommand{\PS}{MRR\xspace}

			\newcommand{\sPref}[1][]{                  
				\ifthenelse{\equal{#1}{}}{\mathrel P}{\mathop{P_{#1}}}
			}


					\newcommand{\ps}{\mbox{\sc PS}}
			\newcommand{\BestEUResPS}{\mbox{\sc BestEUresponsePS}}
			\newcommand{\BestEUResAlgoPS}{\mbox{\sc BestEUresponseAlgoPS}}
			\newcommand{\BestEURes}{\mbox{\sc BestEUresponse}}
			\newcommand{\BestEUResAlgo}{\mbox{\sc BestEUresponseAlgo}}

			\tikzset{
			  treenode/.style = {align=center, inner sep=0pt, text centered,
			    font=\sffamily},
			  arn_n/.style = {treenode, circle, white, font=\sffamily\bfseries, draw=black,
			    fill=black, text width=1.5em},% arbre rouge noir, noeud noir
			  arn_r/.style = {treenode, circle, red, draw=red,
			    text width=1.5em, very thick},% arbre rouge noir, noeud rouge
			  arn_x/.style = {treenode, rectangle, draw=black,
			    minimum width=0.5em, minimum height=0.5em}% arbre rouge noir, nil
			}

		
	

			% \usepackage{enumitem}
			% \setenumerate[1]{label=\rm(\it{\roman{*}}\rm),ref=({\it\roman{*}}),leftmargin=*}
			% \newlength{\wordlength}
			% \newcommand{\wordbox}[3][c]{\settowidth{\wordlength}{#3}\makebox[\wordlength][#1]{#2}}
% 			\newcommand{\mathwordbox}[3][c]{\settowidth{\wordlength}{$#3$}\makebox[\wordlength][#1]{$#2$}}
			
			\newcommand{\set}[1]{\{#1\}}
			\newcommand{\midd}{\mathbin{:}}
			\newcommand{\reals}{\ensuremath{\mathbb{R}}}
			
			% natbib workaround
			% Apt (2000)
			\newcommand{\citet}[1]{\citeauthor{#1}~\shortcite{#1}}
			% (Apt 2000)
			\newcommand{\citep}{\cite}
			% Apt 2000
			\newcommand{\citealp}[1]{\citeauthor{#1}~\citeyear{#1}}
			\DeclareMathOperator{\supp}{supp}


%%% EDITING MACROS
\definecolor{kentuckyblue}{RGB}{0, 93, 170}			%Go Big Blue!
\definecolor{green}{RGB}{0, 102, 0}					%Haris Green
\definecolor{frenchred}{RGB}{250,60,50}				% French Red
\definecolor{unswyellow}{RGB}{255,155,0}			% Andres Orange
\definecolor{bavblue}{RGB}{1,153,213}				%Bavarian Blue

\newcommand{\nick}[1]{\textcolor{kentuckyblue}{\textbf{Nick Says: #1}}}
\newcommand{\haris}[1]{\textcolor{green}{\textbf{Haris Says: #1}}}
\newcommand{\andres}[1]{\textcolor{unswyellow}{\textbf{Andres Says: #1}}}
\newcommand{\simon}[1]{\textcolor{frenchred}{\textbf{Simon Says: #1}}}
\newcommand{\paul}[1]{\textcolor{bavblue}{\textbf{Paul Says: #1}}}

 \begin{document}
	

	
	

\title{Equilibria Under the Probabilistic Serial Rule}
%
 % \author{Paper 101}


\author{Haris Aziz \and  Serge Gaspers  \and Simon Mackenzie \and Nicholas Mattei\\
NICTA and UNSW,
Sydney, Australia \\
\{haris.aziz, serge.gaspers, simon.mackenzie, nicholas.mattei\}@nicta.com.au\\
\AND Nina Narodytska\\ Carnegie Mellon University\\
ninan@gmail.com
\And Toby Walsh\\
NICTA and UNSW,
Sydney, Australia\\
toby.walsh@nicta.com.au
}


\maketitle
\begin{abstract}
The probabilistic serial (PS) rule is a prominent randomized rule for assigning
indivisible goods to agents. Although it is well known for its good fairness and welfare properties, it is not strategyproof. In view of this, we address several fundamental questions regarding equilibria under PS. Firstly, we show that Nash deviations under the PS rule can cycle. Despite the possibilities of cycles, we prove that a pure Nash equilibrium is guaranteed to exist under the PS rule. We then show that verifying whether a given profile is a pure Nash equilibrium is coNP-complete, and computing a pure Nash equilibrium is NP-hard. For two agents, we present a linear-time algorithm to compute a pure Nash equilibrium which yields the same assignment as the truthful profile. Finally, we conduct experiments to evaluate the quality of the equilibria that exist under the PS rule, finding that the vast majority of pure Nash equilibria yield social welfare that is at least that of the truthful profile. 
\end{abstract}




		\section{Introduction}
		
% \nick{Why are there two references for Aziz 2015?}
% \nick{I need to update sample counts tomorrow when the experiments finalize.}

%%%%% Nick's Rewrite.
% Resource allocation is one of the most fundamental and widely applicable area within AI and computer
% science. When resource allocation rules are not strategyproof, it leads to the natural problem of
% examining what happens when one or more agents do not truthfully report their preferences.  Hence,
% central questions focus on manipulation; Nash dynamics; and the existence
% and computation of pure Nash equilibria.


%Haria: minor issues: "area-> areas" "it refers to rules"; "questions focus...wasn't perfectly sure "


Resource allocation is a fundamental and widely applicable area within AI and computer
science. When resource allocation rules are not strategyproof and agents do not have incentive to report their preferences truthfully, it is important to understand the possible manipulations; Nash dynamics; and the existence and computation of equilibria. 


In this paper we consider the  \emph{probabilistic serial (PS)} rule for the \emph{assignment problem}. 
In the \emph{assignment problem} we have a possibly unequal number of agents and objects where
the agents express preferences over 
objects and, based on these preferences, the objects are allocated to the agents~\citep{AGMW14a,BoMo01a,Gard73b,HyZe79a}. The model is applicable to many 
resource allocation and fair division settings where the objects may be public houses, school seats, course enrollments, kidneys for transplant, car park spaces, chores, joint assets, or time slots in schedules. 
The \emph{probabilistic serial (PS)} rule is a randomized (or fractional) assignment rule.
% This class of rules stands in contrast to deterministic rules such as the sequential allocation
% procedure that is often used to ``draft'' objects \cite{KNWX13a}.
% In randomized rules,
% the preferences of the agents are used to allocate a fraction of the objects.
% If the objects are indivisible but allocated in a randomized way, this fraction is interpreted
% as the probability of receiving the object.
A randomized or fractional assignment rule takes the preferences of the agents into account in order to allocate each agent a fraction of the object. If the objects are indivisible but allocated in a randomized way, the fraction can also be interpreted as the probability of receiving the object. 
Randomization is widespread in resource 
allocation as it is a natural way to ensure procedural fairness~\citep{BCKM12a}.


A prominent randomized assignment rule is the PS rule~\citep{BoHe12a,BoMo01a,BCKM12a,KaSe06a,Koji09a,Yilm10a,SaSe13b}.  
PS works as follows: each agent expresses a linear order over the set of houses.\footnote{We use 
the term house throughout the paper though we stress any object could be allocated with these mechanisms.}
Each house is considered to have a divisible probability weight of one. Agents simultaneously and at 
the same speed eat the probability weight of their most preferred house that has not yet been completely
eaten. Once a house has been 
completely eaten by a subset of the agents, each of these agents starts eating his next most preferred 
house that has not been completely eaten (i.e., they may ``join'' other agents already eating a different
house or begin eating new houses). The procedure terminates after all the houses have been completely eaten. 
The random allocation of an agent by PS is the amount of each object he has eaten. 
Although PS was originally defined for the setting where the number of houses is equal to the 
number of agents, it can be used without any modification for any number of  
houses relative to the number agents~\citep{BoMo01a,Koji09a}.

In order to compare random allocations, an agent needs to consider relations between them. 
We consider two well-known relations between random allocation~\cite{ScVa12a,SaSe13b,Cho12a}:
$(i)$ \textit{expected utility (EU)}, 
and $(ii)$ \textit{downward lexicographic (DL)}. %$(ii)$ \textit{stochastic dominance (SD)}, 
For EU, an agent prefers an allocation that yields more expected utility. 
% For SD, one of the most fundamental relations between fractional allocations, an agent
% SD-preferrers one allocation over another if and only if, for every utility function consistent with
% the ordinal preferences, the former yields at least as much expected utility as the latter.
For DL, an agent prefers an allocation that gives a higher probability to the most preferred 
alternative that has different probabilities in the two allocations. 
%  The DL relation
% is a refinement of the SD relation based on lexicographic comparisons between fractional allocations.
Throughout the paper, we assume that agents express \emph{strict} preferences over houses, 
i.e., they are not indifferent between any two houses. 

The PS rule fares well in terms of 
fairness and welfare~\citep{BoHe12a,BoMo01a,BCKM12a,Koji09a,Yilm10a}.
It satisfies strong envy-freeness and efficiency with respect to the DL 
relation~\citep{BoMo01a,ScVa12a,Koji09a}. Generalizations of the PS rule have been 
recommended and applied in many settings~\citep{AzSt14a,BCKM12a}.  The PS rule also satisfies some 
desirable incentive properties: if the number of objects is at most the number of agents, then PS is  
DL-strategyproof~\citep{BoMo01a,ScVa12a}. 
%PS also does not provide any incentive for agents to truncate  their preference list by expressing acceptable objects as unacceptable~\citep{UKK+13a}.
Another well-established rule, \emph{random serial dictator (RSD)}, is not envy-free, not as efficient 
as PS~\citep{BoMo01a}, and the fractional allocations under RSD are \#P-complete 
to compute~\citep{ABB13b}. 

Although PS performs well in terms of fairness and welfare, unlike RSD, it is not strategyproof. \citet{AGM+15c} showed
that, in the scenario where one agent is strategic, computing his best
response (manipulation) under complete information of the other agents' strategies is NP-hard for 
the EU relation, but polynomial-time computable for the DL relation.
% This problem of computing the optimal manipulation has already been studied
% in great depth for voting rules~\citep{FHH10a} and is an active area of research in computational
% social choice.  The key idea is: if it is computationally hard for an agent to compute a beneficial
% manipulation, agents may default to being truthful.
In this paper, we consider the situation where \emph{all} agents are strategic. We especially focus on pure Nash equilibria (PNE) --- reported preferences profiles for which no agent has an incentive to report a different preference.
We examine the following natural questions for the first time: \emph{(i) What is the nature of best response dynamics under the PS rule? (ii) Is a (pure) Nash equilibrium always guaranteed to exist? (iii) How efficiently can a (pure) Nash equilibrium be computed?  (iv) What is the difference in quality of the various equlibria that are possible under the PS rule?} In related work,
\citet{EkKe12a} showed that when agents are not truthful, the outcome of 
PS may not satisfy desirable properties related to efficiency and envy-freeness. 
\citet{HeMa12a} provided a necessary and sufficient condition for implementability of Nash equilibrium  for the random assignment problem. % and show that a Pareto efficient and envy-free solution is Nash implementable.

\bigskip
\noindent
\textbf{Contributions.\;} 
%We initiate a detailed study of Nash equilibria for the PS mechanism.
For the PS rule we show that expected utility best responses can cycle for \emph{any} cardinal utilities consistent with the ordinal preferences. This is significant as Nash dynamics in matching theory 
has been an active area of research, especially for the stable matching problem~\cite{AGM+11a}, and the 
presence of a cycle means that following a sequence of best responses is not guaranteed to result in an 
equilibrium profile.
We then prove that a pure Nash equilibrium (PNE) is guaranteed to exist for any number of agents and houses and any utilities.
To the best of our knowledge, this is the first proof of the existence of a Nash equilibrium for the PS rule. 
For the case of two agents we present a linear-time algorithm to compute a preference profile that is in PNE with respect to the original preferences.
% For the case of two agents we present two different linear-time algorithms to compute a preference profile that
% is in Nash equilibrium with respect to the original preferences. One of our algorithms creates equilibrium profiles
% which results in the \emph{same} assignment as the one in which the agents report their true preference.
We show that the general problem for computing a PNE is NP-hard. Finally, we run a set of 
experiments on real and synthetic preference data to evaluate the welfare achieved by PNE profiles compared to the welfare achieved under the truthful profile. 
%We find that the vast majority of pure Nash equilibria yield social welfare that is at least as great as that of the truthful profile. 

%%%%% OLD INTRO

%Resource allocation is one of the most fundamental and wide applicable area within AI. 
%When resource allocation rules are not strategyproof, it leads to the natural problem of examining the Nash dynamics and existence and computation of pure Nash equilibria. 
%We consider the \emph{assignment problem} in which agents express preferences over objects and, based on these preferences, the objects are allocated to the agents~\citep{AGMW14a,BoMo01a,Gard73b,HyZe79a}. The model is applicable to many resource allocation or fair division settings where the objects may be public houses, school seats, course enrollments, kidneys for transplant, car park spaces, chores, joint assets, or time slots in schedules. 
%
%
%A randomized or fractional assignment rule takes the preferences of the agents into account in order to allocate each agent a fraction of the object. If the objects are indivisible but allocated in a randomized way, the fraction can also be interpreted as the probability of receiving the object. Randomization is widespread in resource allocation since it is one of the most natural ways to ensure procedural fairness~\citep{BCKM12a,BCKM12a}.
%Among the various randomized/fractional assignment rules, the \emph{probabilistic serial (PS)} rule is one of the most prominent rules~\citep{AzSt14a,BoHe12a,BoMo01a,BCKM12a,KaSe06a,Koji09a,Yilm10a,SaSe13b}.  PS works as follows. 
%Each agent expresses a linear order over the set of houses (we use the term house throughout the paper though we stress any object could be allocated with these mechanisms). Each house
%is considered to have a divisible probability weight of one, and agents simultaneously and with the same speed eat the probability weight of their most preferred house. Once a house has been eaten by a subset of agents, these agents proceed to eat their next most preferred house that has not been completely eaten. The procedure terminates after all the houses have been eaten. The random allocation of an agent by PS is the amount of each object he has eaten. Although PS was originally defined for the setting where the number of houses is equal to the number of agents, it can be used without any modification for fewer or more houses than agents~\citep{BoMo01a,Koji09a}.
%
%		The \emph{probabilistic serial (PS)} rule fares better  than any other random assignment rule in terms of fairness and welfare~\citep{BoHe12a,BoMo01a,BCKM12a,Koji09a,Yilm10a}.
%		In particular, it satisfies strong envy-freeness and efficiency with respect to both \emph{stochastic dominance (SD)} and \emph{downward lexicographic (DL)} relations~\citep{BoMo01a,ScVa12a,Koji09a}.
%		% relation between lotteries.\footnote{Both are well-known ways to compare fractional allocations and will be defined formally.}
%		  SD is one of the most fundamental relations between fractional allocations because one allocation is SD-preferred over another if for every utility function consistent with the ordinal preferences, the former yields at least as much expected utility as the latter. DL is a refinement of SD and based on lexicographic comparisons between fractional allocations.
%		Generalizations of the PS rule have been recommended in many settings~\citep{BCKM12a}.
%		The PS rule also satisfies some desirable incentive properties. If the number of objects is at most the number of agents, then PS is weak SD-strategyproof~\citep{BoMo01a}. %PS also does not provide any incentive for agents to truncate their preference list by expressing acceptable objects as unacceptable~\citep{UKK+13a}.
%		Another well-established rule \textit{random serial dictator (RSD)} is not envy-free, not as efficient as PS~\citep{BoMo01a} and the fractional allocations under RSD  are \#P-complete to compute~\citep{ABB13b}. However, unlike RSD,  PS is not strategyproof.
%
%
%		%Although strategic properties of the PS rule have been examined in the past decade~\citep{BoMo01a,KoMa10a,ChKo10a},
%
%\citet{AGM+15b} examined PS under the scenario where one agent is strategic and computes his best response under complete information of othe agents' strategies. 
%This problem of computing the optimal manipulation has already been studied in great depth for voting rules~\citep{FHH10a}.
%In this paper, we consider the situation where \emph{all} agents are strategic.
%We examine the following natural question for the  first time:
%  \emph{What is the nature of best response dynamic under the PS rule? Is a (pure) Nash equilibrium always guaranteed to exist? How efficiently can a (pure) Nash equilibria be computed?}
%\citet{EkKe12a} showed that when agents are not truthful, the outcome of PS may not satisfy desirable properties related to efficiency and envy-freeness. 
%
%
%
%% \emph{what is the computational complexity of an agent computing a different preference to report so as to get a better PS outcome?}\footnote{This problem of computing the optimal manipulation has already been studied in great depth for voting rules~\cite{FHH10a}.}
%% Additionally, we investigate \emph{how often would a random agent benefit from manipulating a given profile?}
%% %We assume that the manipulating agent has full information of the preferences of the other agents.
%% The complexity of manipulation of the PS rule has bearing on another issue that has recently been studied---preference profiles that are in Nash equilibrium.  
%
%
%% Hence, it is important to check that even if agents can in principle manipulate, how hard it is to compute a beneficial misreport of their preferences. 
%% It is also interesting to identify  preference profiles for which no agent has an incentive to unilaterally deviate to gain utility with respect to his actual preference.
%% Hence, we consider the following problem: \emph{for a preference profile, does a (pure) Nash equilibrium exist or not and if it exists how efficiently can it be computed?}
%%
%% TODO: MOTIVATE WHY ONE WOULD WANT TO COMPUTE A NASH EQUILIBRIUM.
%
%In order to compare random allocations, an agent needs to consider relations between them. We consider three well-known relations between random allocation~\cite{BoMo01a,ScVa12a,SaSe13b,Cho12a}:
%$(i)$ \textit{expected utility (EU)}, $(ii)$ \textit{stochastic dominance (SD)},  and $(iii)$ \textit{downward lexicographic (DL)}.
%For EU, an agent seeks a different allocation that yields more expected utility. For SD, an agent seeks a different allocation that yields more expected utility for all cardinal utilities consistent with the ordinal preferences. For DL, an agent seeks an allocation that gives a higher probability to the most preferred alternative that has different probabilities in the two allocations.
%Throughout the paper, we assume that agents express \emph{strict} preferences, i.e., they are not indifferent between any two houses. % Some of our results are for the special case of two agents. 	The two-agent case is also of special importance since various disputes arise between two parties.
%
%%Our contributions are as follows.
%
%\paragraph{Contributions}
%
%
%We initiate a detailed study of Nash equilibria for the PS mechanism --- one of the most established randomized rules for the assignment problem.
%%Relations between various problems---such as computing a better or best response and verifying Nash equilibrium with respect to different lottery extensions---are clarified.
%%We then examine situations in which all agents are strategic.
%We first show that expected utility best responses can cycle. Nash dynamics in matching theory has been an active area of research, especially for the stable matching problem~\cite{AGM+11a}.
%We then prove that a (pure) Nash equilibrium (PNE) exists for any number of agents and houses.
%To the best of our knowledge, this is the first proof of the existence of a Nash equilibrium for the PS rule. 
%%For the case of two agents, we identify a way of constructing a preference profile in linear time that is in Nash equilibrium.
%For the case of two agents we present two different linear-time algorithms to compute a preference profile that 
%is in Nash equilibrium with respect to the original preferences. One type of equilibrium profiles
%results in the \emph{same} assignment as the one in which the agents report their true preference. Finally, we show that the general problem for computing a PNE is NP-hard.
%
%Finally, we run a detailed set of experiments on real as well as syntethically generated preference data to check the welfare achieved by pure Nash equilibrium profiles in contrast to the welfare acheived under the truthful profile. 
%
%
%
%%HARIS: MADE SOME EDITS TO NICK PARAGRAPH BELOW.
%
%% Finally, we perform an experimental study of the frequency and effect of manipulability on assignments generated by the PS mechanism.
%% We investigate, under a variety of utility functions and preference distributions, the likelihood that some agent
%% has an incentive to misreport his preference. The experiments identify settings and utility models in which PS is less susceptible to manipulation.  and that, 
%% often, when manipulations can occur, they do not severely effect the utility of the non-manipulating agents.
%%We find that, for some mild restrictions on the form of profiles,
%%agents would not have an incentive to misreport their preferences.
%% Due to space limitations, details of some proofs and experiments are deferred to the full report \url{http://dropproxy.com/f/43B}.
%
%%The equilibrium is also a DL-Nash equilibrium and SD-Nash equilibrium.
%
%
%
%% We present a constructive proof that a DL-Nash-equilibrium and hence an SD-Nash-equilibrium exists for two agents.
%% To the best of our knowledge, this is the first proof of existence of Nash equilibrium with respect to the PS rule.
%
%
%
%%We also show that for the case of two agents, a DL-Nash equilibrium and hence an SD-Nash equilibrium exists and can be computed in linear time (TOBY).

		\section{Preliminaries}

		% TODO: UNIFY NOTATION $\pref$ AND $\succ$. FOR STRICT PREFERENCES $\succ$ SEEMS BETTER.

		An \emph{assignment problem} $(N, H, \pref)$ consists  of a set of agents $N=\{1,\ldots, n\}$, a set of houses $H=\{h_1, \ldots, h_m\}$ and a preference profile $\pref=(\pref_1,\ldots, \pref_n)$ in which $\pref_i$ denotes a complete, transitive and strict ordering on $H$ representing the preferences of agent $i$ over the houses in  $H$.
		%Since each $\pref_i$ will be strict throughout the paper, we will also refer to it simply as $\succ_i$.
			A \emph{fractional assignment} is an $(n\times m)$ matrix $[p(i)(h_j)]_{\substack{1\leq i\leq n, 1\leq j\leq m}}$ such that for all $i\in N$, and $h_j\in H$, $0\leq p(i)(h_j)\leq 1$;  and for all $j\in \{1,\ldots, m\}$, $\sum_{i\in N}p(i)(h_j)= 1$. %$\sum_{h_j\in H}p_{ij}=\sum_{h\in H}w(h)/n$;
		The value $p(i)(h_j)$ is the fraction of house $h_j$ that agent $i$ gets. Each row $p(i)=(p(i)(h_1),\ldots, p(i)(h_m))$ represents the \emph{allocation} of agent $i$.
	A fractional assignment can also be interpreted as a random assignment where $p(i)(h_j)$ is the probability of agent $i$ getting house $h_j$.
	%We will also denote $p(i)(j)$ by $p(i)(h_j)$.





		% \paragraph{Relations between allocations}
			%In this paper, we will reason about lotteries.
		% 	A standard method to compare random allocations is to use the \emph{SD (stochastic dominance)} relation. %.\footnote{Stochastic dominance is equivalent to the \emph{majorization} relation used in mathematics~\citep[see
		% %	\begin{definition}
		% 	%  Given two random assignments $p$ and $q$, $p(i) \succsim_i^{SD} q(i)$ i.e.,  a player $i$ \emph{weakly SD~prefers} allocation $p(i)$ to $q(i)$ if
		% 	% $\sum_{h_j\in \set{h_k\midd h_k\pref_i h}}p(i)(h_j) \ge \sum_{h_j\in \set{h_k\midd h_k\pref_i h}}q(i)(h_j) \text{ for all } h\in H.$
		% 	%
		% 	 Given two random assignments $p$ and $q$, $p(i) \succ_i^{SD} q(i)$ i.e.,  a player $i$ \emph{SD~prefers} allocation $p(i)$ to $q(i)$ if
		% 	$\sum_{h_j\in \set{h_k\midd h_k\pref_i h}}p(i)(h_j) \ge \sum_{h_j\in \set{h_k\midd h_k\pref_i h}}q(i)(h_j)$  for all  $h\in H$ and
		% 	$\sum_{h_j\in \set{h_k\midd h_k\pref_i h}}p(i)(h_j) > \sum_{h_j\in \set{h_k\midd h_k\pref_i h}}q(i)(h_j) \text{ for some } h\in H.$

			Given two random assignments $p$ and $q$, $p(i) \pref_i^{DL} q(i)$ i.e.,  a player $i$ \emph{DL~(downward lexicographic) prefers}  allocation $p(i)$ to $q(i)$ if $p(i)\neq q(i)$ and for the most preferred house $h$ such that $p(i)(h)\neq q(i)(h)$, we have that $p(i)(h)>q(i)(h)$.
When agents are considered to have cardinal utilities for the objects, we denote by $u_i(h)$ the utility that agent $i$ gets from house $h$. We will assume that the total utility of an agent equals the sum of the utilities that he gets from each of the houses. Given two random assignments $p$ and $q$, $p(i) \pref_i^{EU} q(i)$, i.e.,  a player $i$ \emph{EU (expected utility)~prefers} allocation $p(i)$ to $q(i)$ if
			$\sum_{h\in H}u_i(h) \cdot p(i)(h)> \sum_{h\in H}u_i(h) \cdot q(i)(h).$
			%\end{definition}
		Since for all $i\in N$, agent $i$ compares assignment $p$ with assignment $q$ only with respect to his allocations $p(i)$ and $q(i)$, we will sometimes abuse the notation and use $p\pref_i^{EU} q$ for $p(i)\pref_i^{EU} q(i)$.

		A \emph{random assignment rule} takes as input an assignment problem $(N,H,\pref)$ and returns a random assignment which specifies what fraction or probability of each house is allocated to each agent.
We will primarily focus on the expected utility setting but will comment 
on and use DL wherever needed.

\paragraph{The Probabilistic Serial Rule and Equilibria.}
The \emph{Probabilistic Serial (PS) rule} is a random assignment algorithm in which we consider each house as infinitely divisible.
At each point in time, each agent is eating (consuming the probability mass of) his most preferred house that has not been completely eaten. Each agent eats at the same unit speed. Hence all the houses are eaten at time $m/n$ and each agent receives a total of $m/n$ units of houses.
The probability of house $h_j$ being allocated to $i$ is the fraction of house $h_j$ that $i$ has eaten. The PS fractional assignment can be computed in time $O(mn)$.
We refer the reader to \citet{BoMo01a} or \citet{Koji09a} for alternative definitions of PS. % The following example adapted from \cite{BoMo01a} shows how PS works.
 The following example from \citet{BoMo01a,AGM+15c} shows how PS works.


\begin{example}[PS rule]\label{example:PS}
	Consider an assignment problem with the following preference profile.
\begin{align*}
	\centering
	%\succ_1: h_1,h_2,h_3 &\quad \succ_2: h_2,h_1,h_3 & \succ_3:  h_2,h_3,h_1
	\succ_1:&\quad h_1,h_2,h_3 \\ \succ_2:&\quad h_2,h_1,h_3 \\ \succ_3:&\quad  h_2,h_3,h_1
	% \succ_2:\quad& h_2,h_1,h_3\\
	%\succ_3:\quad& h_2,h_3,h_1
	\end{align*}
	Agents $2$ and $3$ start eating $h_2$ simultaneously whereas agent $1$ eats $h_1$. When $2$ and $3$ finish $h_2$, agent $3$ has only eaten half of $h_1$.  The timing of the eating can be seen below.
\begin{center}
             \begin{tikzpicture}[scale=0.2]
                 \centering
                 \draw[-] (0,0) -- (0,6);
                 \draw[-] (0,0) -- (20,0);

                 \draw[-] (20,6) -- (20,0);


\draw[-] (0,2) -- (20,2);
\draw[-] (0,4) -- (20,4);
\draw[-] (20,0) -- (20,6);


\draw[-] (10,0) -- (10,6);

\draw[-] (0,6) -- (20,6);





\draw[-] (15,0) -- (15,6);



                                        \draw (0,-.8) node(c){\small $0$};
                             \draw (20/2,-1.2) node(c){\small $\frac{1}{2}$};

 \draw (20/2,-2.5) node(c){\small Time};


                             \draw (20,-1) node(c){\small$1$};



\draw (15,-1.2) node(c){\small$\frac{3}{4}$};

             %    \draw(-.7,15) node(z){\small $10$};
    \draw(-3,6) node(z){\small Agent $1$};
                 \draw(-3,4) node(z){\small Agent $2$};
                 \draw(-3,2) node(z){\small Agent $3$};


\draw(5,6.8) node(z){\small $h_1$};

\draw(5,4.8) node(z){\small $h_2$};

\draw(5,2.8) node(z){\small $h_2$};


\draw(12.5,6.8) node(z){\small $h_1$};

\draw(12.5,4.8) node(z){\small $h_1$};

\draw(12.5,2.8) node(z){\small $h_3$};


\draw(17.5,6.8) node(z){\small $h_3$};

\draw(17.5,4.8) node(z){\small $h_3$};

\draw(17.5,2.8) node(z){\small $h_3$};
  \end{tikzpicture}
 %       \] 
 %\caption{Illustration of PS with agents eating their preferred objects over time for the preference profile in Example~\ref{example:PS}.}
%\label{figure:muli-ps}
% \end{figure}
\end{center}

\noindent
	The final allocation computed by PS is
\[
PS(\succ_1,\succ_2,\succ_3)=\begin{pmatrix}
	3/4&0&1/4\\
  1/4&1/2& 1/4 \\
  0&1/2 &  1/2

 \end{pmatrix}.
\]


\end{example}

% We write the formal definition of PS from \cite{Koji09a} as an algorithm. For any $h\in H'\subset H$, let $N(h,H')=\{i\in N\midd a\succsim_i b \text{  for every } b\in H'\}$ be the set of agents whose most preferred house in $H'$ is $h$. PS is defined by the following steps:
%
%
% 	\begin{algorithm}[h!]
% 	  \caption{PS}
% 	  \label{PS}
% %	\small
% 	\renewcommand{\algorithmicrequire}{\wordbox[l]{\textbf{Input}:}{\textbf{Output}:}}
% 	 \renewcommand{\algorithmicensure}{\wordbox[l]{\textbf{Output}:}{\textbf{Output}:}}
% 	\begin{algorithmic}
% 		\REQUIRE $(N,H,\succ)$
% 		\ENSURE $p$ the random assignment returned by PS
% 	\end{algorithmic}
% 	\algsetup{linenodelimiter=\,}
% 	  \begin{algorithmic}[1]
% 		
% \STATE $s\longleftarrow 0$ ($s$ is the stage of the algorithm)
% \STATE $H^O\longleftarrow H$; $t^0\longleftarrow 0$; $p_{ih}^0\longleftarrow 0$ for all $i\in N$ and $h\in H$.
%
% \WHILE{$H^s\neq \emptyset$}
% \STATE $t^{s+1}(h)=\sup\{t\in [0,|H|]\midd \sum_{i\in N} p_{ih}^s+|N(h,H^s)|(t-t^s)<1\}$
% \STATE $t^{s+1}\longleftarrow \min_{h\in H^s}t^s(h)$
% \STATE $H^s=H^s\setminus \{h\in H^{s-1}\midd t(h)=t^s\}$
% \FOR{all $i\in N$ and $h\in H$}
% \IF{$ i\in N(h,H^s)$}
% \STATE  $p_{ih}^{s+1} \longleftarrow  p_{ih}^{s}+t^{s+1}-t(s) $
% \ELSE
% \STATE $ p_{ih}^{s+1} \longleftarrow  p_{ih}^{s} $
% \ENDIF
% \ENDFOR
%
%  \STATE $s\longleftarrow s+1$
% \ENDWHILE	
%
%
% \RETURN $p=p^s$
%
%
% 	 \end{algorithmic}
% 	\label{algo:subroutine}
% 	\end{algorithm}




% \begin{remark}
	% Under DL preferences, if $m\leq n$, then the truthful preference profile is in PNE. The reason is that under DL preferences and  $m\leq n$, truth-telling is a dominant strategy.
% \end{remark}
Consider the assignment problem in Example~\ref{example:PS}. If agent $1$ misreports his preferences as follows: $\succ_1':\quad h_2,h_1,h_3,$ then \[
		PS(\succ_1',\succ_2,\succ_3)=\begin{pmatrix}
			1/2&1/3&1/6\\
		  1/2 & 1/3 & 1/6 \\
		  0 & 1/3 & 2/3
			\end{pmatrix}.
		\]
		\noindent
		If we suppose that $u_1(h_1)=7$, $u_1(h_2)=6$, and $u_1(h_3)=0$, then agent $1$ gets more expected utility when he reports $\succ_1'$. In the example,
the truthful profile is in PNE with respect to DL preferences but not expected utility. 		
		

%The following example adapted from \cite{BoMo01a}, shows that the PS rule is susceptible to manipulation.
%
%
%\begin{example}\label{example:EUmanip}
	%%[Manipulating the PS rule to increase expected utility]
	%Consider the assignment problem in Example~\ref{example:PS}.
	%% \begin{align*}
%% 	\succ_1:\quad& h_1,h_2,h_3\\
%% 	\succ_2:\quad& h_2,h_1,h_3\\
%% 	\succ_3:\quad& h_2,h_3,h_1
%% 	\end{align*}
%%
%% \[
%% PS(\succ_1,\succ_2,\succ_3)=\begin{pmatrix}
%% 	3/4&0&1/4\\
%%   1/4&1/2& 1/4 \\
%%   0&1/2 &  1/2
%%
%%  \end{pmatrix}
%% \]
%If agent $1$ misreports his preferences as follows: $\succ_1':\quad h_2,h_1,h_3,$
%% \begin{align*}
%% 	\succ_1':\quad& h_2,h_1,h_3,
%% 	\end{align*}
%then \[
%PS(\succ_1',\succ_2,\succ_3)=\begin{pmatrix}
	%1/3&1/2&1/6\\
  %1/3 & 1/2 & 1/6 \\
  %1/3 & 0 & 2/3
	%\end{pmatrix}
%\]
%
%Then, if $u_1(h_1)=100+\epsilon$, $u_1(h_2)=100$, and $u_1(h_3)=0$, then for a suitable $\epsilon$, agent $1$ gets more expected utility when he reports $\succ_1'$.
%
%\end{example}
%
% \begin{observation}
% 	Example~\ref{example:EUmanip} shows that a DL-optimal response may not be an EU-optimal response. If the number of houses is not more than the number of agents, then reporting the truthful preference is a DL-optimal response~\cite{ScVa12a}. However, we note that $\succ_1'$ gives strictly more utility than reporting the truth.
% \end{observation}


%
%
%
%\begin{example}
%\begin{align*}
	%\succ_1:\quad& h_1,h_2,h_3\\
	%\succ_2:\quad& h_1,h_3,h_2\\
	%\succ_3:\quad& h_2,h_1,h_3\\
	%\end{align*}
%
%\[
%PS(\succ_1,\succ_2,\succ_3)=\begin{pmatrix}
  %1/2 & 1/4 & 1/4 \\
  %1/2 & 0 & 1/2 \\
	%0&3/4&1/4
 %\end{pmatrix}
%\]
%
%However, if agent $3$ misreports his preferences:
%
%\begin{align*}
	%\succ_3':\quad& h_1,h_2,h_3,\\
	%\end{align*}
%
%then \[
%PS(\succ_1,\succ_2,\succ_3'))=\begin{pmatrix}
  %1/3 & 1/2 & 1/6 \\
  %1/3 & 0 & 2/3 \\
	%1/3&1/2&1/6
 %\end{pmatrix}
%\]
%
%Then, if $u_3(h_2)=100+\epsilon$, $u_3(h_1)=100$, and $u_3(h_3)=0$, then for a suitably defined $\epsilon$, agent $3$ gets more expected utility when he reports $\succ_3'$.
%
%\end{example}

% Examples 1 and 2 of \cite{Koji09a} show that manipulating the PS mechanism can lead to an SD improvement when each agent can be allocated more than one house. % In light of the fact that the PS rule can be manipulated, we examine the complexity of a single agent computing a manipulation, in other words, the best response for the PS rule.\footnote{Note that if an agent is risk-averse and does not have information about the other agent's preferences, then his maximin strategy is to be truthful. The reason is that if all all agents have the same preferences, then the optimal strategy is to be truthful.}
 We study the existence and computation of Nash equilibria.
For a preference profile $\pref$, we denote by $(\pref_{-i},\pref_i')$ the preference profile obtained from $\pref$ by replacing agent $i$'s preference by $\pref_i'$.
% For $\mathcal{E}\in \{SD, EU, DL\}$, we define the problem \textsc{$\mathcal{E}$BestResponse}: given $(N,H,\pref)$,
%  compute a preference $\pref_1'$ for agent $1$  such that there exists no preference $\pref_1''$ such that $PS(N,H,(\pref_1'',\pref_{-1})) \succ_1^{\mathcal{E}} PS(N,H,(\pref_1',\pref_{-1}))$.
% For a constant $m$, the problem \textsc{$\mathcal{E}$BestResponse} can can be solved by brute force by trying out each of the $m!$ preferences. Hence we will not assume that $m$ is a constant.

% We will denote the eating starting time of some house $h$ by $t_s(h, (N,H,\pref))$.
% We establish some more notation and terminology for the rest of the paper.
% We will often refer to the PS outcomes for partial lists of houses and preferences.
% We will denote by $PS(\pref_i^{L}, \pref_{-i})(i)$, the allocation that agent $i$ receives when
% his preference is according to ordered list $L$.
% Note that preferences and ordered lists are interchangeable, except that a list need not contain all houses in $H$.
% When an agent runs out of houses
% in his preference list, he stops eating.
% The \emph{length} of a list $L$ is denoted $|L|$, and we refer to the $k$th house in $L$ as $L(k)$.
% In the PS rule, the \emph{eating start time} of a house is the time point at which the house starts to be eaten by some agent. In Example~\ref{example:PS}, the eating start times of $h_1,h_2$ and $h_3$ are $0,0$ and $0.5$, respectively.


\section{Nash Dynamics}

%In contrast to the previous sections where a single agent is strategic, we consider the setting when all the agents are strategic. In particular we examine the problem of checking whether a  (pure) Nash equilibrium exists or not and how to compute such an equilibrium profile.



% \begin{quote}
% \textsc{$\mathcal{E}$Nash}: Given $(N,H,\pref)$, does there exist a preference profile $\pref'$ such that $PS(N,H,\pref') \succ_i^{\mathcal{E}} PS(N,H,(\pref_i'',\pref_{-i}'))$ for all $i\in N$ and all $\pref_i''$? If yes, then return such a preference profile.
% \end{quote}


%\pbDef{\textsc{$\mathcal{E}$Nash}}
 %{$(N,H,\pref)$}
 %{Does there exist a preference profile $\pref'$ such that $PS(N,H,\pref') \succ_i^{\mathcal{E}} PS(N,H,(\pref_i'',\pref_{-i}'))$ for all $i\in N$ and all $\pref_i''$? If yes, then return such a preference profile.
%}
% In contrast to the previous sections where a single agent is strategic, we consider the setting where all agents are strategic. 


When considering Nash equilibria of any setting, one of the most natural ways of proving that a PNE always exists is to show that better or best responses do not cycle which implies that eventually, Nash dynamics terminate at a Nash equilibrium profile. Our first result is that DL and EU best responses can cycle. For EU best responses, this is even the case when agents have Borda utilities.  %This means
%that it is possible that self-interested agents, acting unilaterally,
%may never stop reacting.

\begin{theorem}\label{th:cycle}
With 2 agents and 5 houses where agents have Borda utilities, 
EU best responses can lead to a cycle in the profile.
\end{theorem}

\begin{proof}
The following 5 step sequence of best responses leads
to a cycle.  We use $U$ to denote
the matrix of utilities of the agents over the houses such that
$U[1,1]$ is the utility of agent $1$ for house $h_1$.
Note that $P$ starts as the truthful reporting in our example.
%
The initial preferences and utilities of the agents are:

\noindent
\begin{minipage}{.48\columnwidth}
\begin{align*}
	\succ_1:\quad & h_2,h_3,h_5,h_4,h_1  \\
	\succ_2:\quad & h_5,h_3,h_4,h_1,h_2  
 \end{align*}
\end{minipage}
\begin{minipage}{.48\columnwidth}
\[
 U_0 = \begin{pmatrix}
	0 & 4 & 3 & 1 & 2 \\
	1 & 0 & 3 & 2 & 4  
 \end{pmatrix}.
\]
\end{minipage}

\smallskip
\noindent
This yields the following allocation and utilities at the start:

\noindent
% \begin{minipage}{.55\columnwidth}
\[
 PS(\succ_1,\succ_2) = \begin{pmatrix}
	1/2 	& 1	 & 1/2	 & 1/2	& 0	 \\
	1/2 	& 0	 & 1/2	 & 1/2	& 1	 \\
 \end{pmatrix},  EU_0 = \begin{pmatrix}
	6  \\
 	7 
 \end{pmatrix}.
\]
%%% STEP 1

\noindent
In Step 1, agent 1 deviates to increase his utility.
He reports the preference $\succ_1': h_3,h_4,h_2,h_1,h_5$;
which results in
\[
 PS(\succ_1',\succ_2) = \begin{pmatrix}
	0 	& 1	 & 1	 	& 1/2		& 0	 \\
	1 	& 0	 & 0		& 1/2		& 1	 \\
 \end{pmatrix}, EU_1 = \begin{pmatrix}
	7.5  \\
 	6 
 \end{pmatrix}.
\]

\noindent
In Step 2, agent 2 changes his report to
$\succ_2': h_3,h_4,h_5,h_1,h_2.$
This increases his utility to 7 and decreases
the utility of agent 1 to 6.


In Step 3, Agent 1 changes his report
to $\succ_1'': h_3,h_5,h_2,h_1,h_4.$ This 
increases the utility of agent 1 to 7.5 and
decreases the utility of agent 2 to 4.5.


In Step 4, Agent 2 changes his report to
$\succ_2'': h_5,h_3,h_4,h_1,h_2.$ which 
increases his expected utility to 6.5 while 
decreasing the expected utility of agent 1
to 7.


%%% STEP 5
In Step 5, Agent 1 changes his report
to $\succ_1''': h_3, h_4, h_2, h_1, h_5.$
Notice that $\succ_1''' = \succ_1'$ and 
$\succ_2'' = \succ_2$.
%
% and yields 
%
%\noindent
%\[
% PS(\succ_1''',\succ_2'') = \begin{pmatrix}
%	0 	& 1	 & 1	 	& 1/2		& 0	 \\
%	1 	& 0	 & 0		& 1/2		& 1	 \\
% \end{pmatrix}, EU_5 = \begin{pmatrix}
%	7.5  \\
% 	6 
% \end{pmatrix}.
%\]
This is the same profile as the one of Step 1, so we have 
cycled. 
\end{proof}
It can be verified that every response in this example is both an EU best response (with respect to any cardinal utilities consistent with the ordinal preferences) and also 
a DL best response.  Hence,  DL best responses and EU best responses (with respect to any cardinal utilities consistent with the ordinal preferences) can cycle.



%\haris{We don't say anything about DL dynamics. Is it possible to test it out as well?}
%\nick{done, revised above.}

%%%% STEP 1
%\noindent
%In Step 1, Agent 1 lies to increase his utility.
%
%\noindent
%\begin{minipage}{.30\textwidth}
%\[
%P_1=\begin{pmatrix}
%	h_3 & h_4 & h_2 & h_1 & h_5  \\
%	h_5 & h_3 & h_4 & h_1 & h_2  
% \end{pmatrix}
%\]
%\end{minipage}
%\begin{minipage}{.25\textwidth}
%\[
% PS_1 = \begin{pmatrix}
%	0 	& 1	 & 1	 	& 1/2		& 0	 \\
%	1 	& 0	 & 0		& 1/2		& 1	 \\
% \end{pmatrix}
%\]
%\end{minipage}
%\hfill
%\begin{minipage}{.2\textwidth}
%\[
% EU_1 = \begin{pmatrix}
%	7.5  \\
% 	6 
% \end{pmatrix}.
%\]
%\end{minipage}
%\bigskip
%
%%%% STEP 2
%\noindent
%In Step 2, Agent 2 changes his report in response.
%
%\noindent
%\begin{minipage}{.30\textwidth}
%\[
%P_2=\begin{pmatrix}
%	h_3 & h_4 & h_2 & h_1 & h_5  \\
%	h_3 & h_4 & h_5 & h_1 & h_2  
% \end{pmatrix}
%\]
%\end{minipage}
%\begin{minipage}{.25\textwidth}
%\[
% PS_2 = \begin{pmatrix}
%	1/2 	& 1	 & 1/2	 & 1/2	& 0	 \\
%	1/2 	& 0	 & 1/2	 & 1/2	& 1	 \\
% \end{pmatrix}
%\]
%\end{minipage}
%\hfill
%\begin{minipage}{.2\textwidth}
%\[
% EU_2 = \begin{pmatrix}
%	6  \\
% 	7 
% \end{pmatrix}.
%\]
%\end{minipage}
%\bigskip
%
%%%% STEP 3
%\noindent
%In Step 3, Agent 1 changes his report in response.
%
%\noindent
%\begin{minipage}{.30\textwidth}
%\[
%P_3=\begin{pmatrix}
%	h_3 & h_5 & h_2 & h_1 & h_4  \\
%	h_3 & h_4 & h_5 & h_1 & h_2  
% \end{pmatrix}
%\]
%\end{minipage}
%\begin{minipage}{.25\textwidth}
%\[
% PS_3 = \begin{pmatrix}
%	0 	& 1	 & 1/2	 & 0		& 1	 \\
%	1 	& 0	 & 1/2	 & 1		& 0	 \\
% \end{pmatrix}
%\]
%\end{minipage}
%\hfill
%\begin{minipage}{.2\textwidth}
%\[
% EU_3 = \begin{pmatrix}
%	7.5  \\
% 	4.5 
% \end{pmatrix}.
%\]
%\end{minipage}
%\bigskip
%
%
%%%% STEP 4
%\noindent
%In Step 4, Agent 2 changes his report in response.
%
%\noindent
%\begin{minipage}{.30\textwidth}
%\[
%P_4=\begin{pmatrix}
%	h_3 & h_5 & h_2 & h_1 & h_4  \\
%	h_5 & h_3 & h_4 & h_1 & h_2  
% \end{pmatrix}
%\]
%\end{minipage}
%\begin{minipage}{.25\textwidth}
%\[
% PS_4 = \begin{pmatrix}
%	1/2 	& 1	 & 1	 	& 0		& 0	 \\
%	1/2 	& 0	 & 0		& 1		& 1	 \\
% \end{pmatrix}
%\]
%\end{minipage}
%\hfill
%\begin{minipage}{.2\textwidth}
%\[
% EU_4 = \begin{pmatrix}
%	7  \\
% 	6.5 
% \end{pmatrix}.
%\]
%\end{minipage}
%\bigskip
%
%
%%%% STEP 5
%\noindent
%In Step 5, Agent 1 changes his report in response.
%
%\noindent
%\begin{minipage}{.30\textwidth}
%\[
%P_5=\begin{pmatrix}
%	h_3 & h_4 & h_2 & h_1 & h_5  \\
%	h_5 & h_3 & h_4 & h_1 & h_2  
% \end{pmatrix}
%\]
%\end{minipage}
%\begin{minipage}{.25\textwidth}
%\[
% PS_5 = \begin{pmatrix}
%	0 	& 1	 & 1	 	& 1/2		& 0	 \\
%	1 	& 0	 & 0		& 1/2		& 1	 \\
% \end{pmatrix}
%\]
%\end{minipage}
%\hfill
%\begin{minipage}{.2\textwidth}
%\[
% EU_5 = \begin{pmatrix}
%	7.5  \\
% 	6 
% \end{pmatrix}.
%\]
%\end{minipage}
%\bigskip
%
%\noindent
%This last step is the same profile as Step 1, which means we have 
%cycled.
%\end{proof}

% \begin{theorem}\label{th:cycle}
% With 3 agents and 6 houses where agents have Borda utilities, 
% a series of expected utility best responses by the agents can lead to a cycle
% in the profile.
% \end{theorem}

The fact that best responses can cycle means that simply following best responses need not result in a PNE. Hence the normal form game induced by the PS rule is not a potential game~\citep{MoSh96a}.
% A normal form game is a \emph{potential game} is there exists a finite \emph{potential function} which takes as input the action profile of the agents and which increases if an agent changes his action to a best response.
% We call the PS game the normal form game in which the actions of the agents are their preferences and the outcome of a preference profile is the resultant assignment under the PS rule. Then, we get the following as a corollary. 
% 
% \begin{corollary}
% 	The PS game is not a potential game.
% \end{corollary}
Checking whether an instance has a Nash equilibrium appears to be a challenging problem. The naive method requires going through $O({m!}^n)$ profiles, which is super-polynomial even when $n=O(1)$ or $m=O(1)$. 


\section{Existence of Pure Nash Equilibria}
%
 % \haris{I hope someone will read this section to verify the details. }
Although it seems that computing a Nash equilibrium is a challenging problem (we give hardness results in the next section),
we show that at least one (pure) Nash equilibrium is guaranteed to exist for any number of houses, any number of agents, and any preference relation over fractional allocations.\footnote{We already know from Nash's original result that a \emph{mixed} Nash equilibrium exists for any game.} The proof relies on showing that the PS rule can be modelled as a perfect information extensive form game. 	% In Figure~\ref{fig:extensiveggame}, we illustrate the perfect information extensive form game corresponding to PS.

\begin{theorem}
A PNE is guaranteed to exist under the PS rule for any number of agents and houses, and for any relation between allocations.
\end{theorem}
		
		\begin{proof}[Proof sketch]
		
			%
			%
			% Let $t^0,\dots, t^k$ be the $k+1$ different time steps in the PS algorithm. Let $g=\text{GCD}(\{t^{i+1}-t^i\midd i\in \{0,\ldots, k-1\}\})$ where GCD denotes the greatest common divisor.
		
%%%% Revised to Serge's Rewrite..
		
%			Consider running PS on all possible ${m!}^n$ preference profiles for $n$ agents and $m$ objects. In each profile $i$, let $t_i^0,\dots, t_i^{k_i}$ be the $k_i+1$ different time points in the PS algorithm run for the $i$-th profile when at least one house is finished.
%			% \todo{What is a step in this context?: thanks, now addressed/clarified}
%			%
%			Let $g_i=\text{GCD}(\{t_i^{j+1}-t_i^j\midd j\in \{0,\ldots, k_i-1\}\})$ where GCD denotes the greatest common divisor. Since $t_i^{j+1}-t_i^j>0$ for all $j\in \{0,\ldots, k_i-1\}$, each $g_i$ is finite and greater than zero. We let $G$ denote the set of different $g_i$'s for all preference profile and let $g$ equal to $\text{GCD}(G)$.
%				\todo[inline]{The $g_i$'s and $G$ are not used anymore after defining $g$. I suggest to simplify this as follows:\\
%			Consider running PS on all possible ${m!}^n$ preference profiles for $n$ agents and $m$ objects. In each profile $i$, let $t_i^1,\dots, t_i^{k_i}$ be the $k_i$ different time points in the PS algorithm run for the $i$-th profile when at least one house is finished.
%			% \todo{What is a step in this context?: thanks, now addressed/clarified}
%			%
%			Let $g=\text{GCD}(\{t_i^{j+1}-t_i^j\midd j\in \{1,\ldots, k_i-1\}, i\in \{1,\dots,m!^n\})$ where GCD denotes the greatest common divisor. Since in each profile $i$, $t_i^{j+1}-t_i^j>0$ for all $j\in \{0,\ldots, k_i-1\}$, we have that $g$ is finite and greater than zero.}
			
	Consider running PS on all possible ${m!}^n$ preference profiles for $n$ agents and $m$ objects. In each profile $i$, let $t_i^1,\dots, t_i^{k_i}$ be the $k_i$ different time points in the PS algorithm run for the $i$-th profile when at least one house is finished. Let $g=\text{GCD}(\{t_i^{j+1}-t_i^j\midd j\in \{1,\ldots, k_i-1\}, i\in \{1,\dots,m!^n\})$ where GCD denotes the greatest common divisor. Since in each profile $i$, $t_i^{j+1}-t_i^j>0$ for all $j\in \{0,\ldots, k_i-1\}$, we have that $g$ is finite and greater than zero.
			
			
	The time interval length $g$ is small enough such that each run of the PS rule can be considered to have $m/g$ stages of duration $g$. Each stage can be viewed as having $n$ sub-stages so that in each stage, agent $i$ eats $g/n$ units of a house in sub-stage $i$ of a stage.
		In each sub-stage only one agent eats $g/n$ units of the most favoured house that is available. Hence we now view PS as consisting of a total of $mn/g$ sub-stages and the agents keep coming in order $1,2,\ldots, n$ to eat $g$ units of the most preferred house that is still available. If an agent eats $g$ units of a house in a stage then it will eat $g$ units of the same house in his sub-stage of the next stage as long as the house has not been fully eaten.
		Consider a perfect information extensive form game tree.
		For a fixed reported preference profile, the PS rule unravels accordingly along a path starting at the root and ending at a leaf. Each level of the tree represents a sub-stage in which a certain agent has his turn to eat $g$ units of his most preferred available house. Note that there is a one-to-one correspondence between the paths in the tree and the ways the PS algorithm can be implemented, depending on the reported preference. %For each path in the tree, we know the house eaten by each agent at each time point. For the other direction, for each unique way the agents
		%ate the houses during the PS algorithm, there is a unique path in the extensive game tree.

		A subgame perfect Nash equilibrium (SPNE) is guaranteed to exist for such a game via backward induction:
		starting from the leaves and moving towards the root of the tree, the agent at the specific node chooses an action that maximizes his utility given the actions determined for the children of the node. The SNPE identifies at least one such path from a leaf to the root of the game. The path can be used to read out the most preferred house of each agent at each point. The information provided is sufficient to construct a preference profile that is in Nash equilibrium. Those houses that an agent did not eat at all can conveniently be placed at the end of the preference list. Such a preference profile is in Nash equilibrium. %Hence, a PNE exists under the PS rule.
		\end{proof}

% In Figure~\ref{fig:extensiveggame}, we illustrate the perfect information extensive form game corresponding to PS.
%
% 	\begin{figure}[htb]
% 		\centering
% 		\scalebox{0.5}{
% 	\begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
% 	  level distance = 1.5cm}]
% 	\node [arn_n] {\Large 1}
% 	    child{ node [arn_r] {\Large 2}
% 	            child{ node [arn_n] {\Large 1}
% 	            	child{ node [arn_r] {\Large 2}child{ node [arn_x] {}
% 		edge from parent node[left]{\Large$h_2$}
% 	}
% 	edge from parent node[left]{\Large$h_2$}
% 	}
% 		edge from parent node[above left]
%                  {\Large$h_1$}
% 	            }
% 	            child{ node [arn_n] {1}
% 								child{ node [arn_r] {\Large 2}
% 								child{ node [arn_x] {}
% 					edge from parent node[left]{\Large$h_2$}
% 								}
% 						edge from parent node[left]{\Large$h_1$}
% 								}
% 				edge from parent node[above right]{\Large$h_2$}
% 	            }
% 	edge from parent node[above left]{\Large$h_1$}
% 	    }
% 	%%%%%
% 	    child{ node [arn_r] {\Large 2}
% 	            child{ node [arn_n] {\Large1}
% 								child{ node [arn_r] {\Large 2}
% 								child{ node [arn_x] {}
% 						edge from parent node[left]{\Large$h_1$}
% 								}
% 						edge from parent node[left]{\Large$h_2$}
% 								}
% 						edge from parent node[above left]{\Large$h_1$}
% 	            }
% 	            child{ node [arn_n] {1}
% 								child{ node [arn_r] {\Large 2}
% 								child{ node [arn_x] {}
% 	edge from parent node[left]{\Large$h_1$}
% 								}
% 							edge from parent node[left]{\Large$h_1$}
% 								}
% 				edge from parent node[above right]{\Large$h_2$}
% 							%	child{ node [arn_x] {}}
% 	            }
% 	edge from parent node[above right]{\Large$h_2$}
% 			}
% 	;
% 	\end{tikzpicture}
% 	}
% 	\caption{A perfect information extensive form game based on breaking down the PS algorithm into a series of stages. For the case of two agents, each agent eats half a house in his turn. An agent has to continue eating a house if he eats it in a previous stage.
% 	}
% \label{fig:extensiveggame}
% \end{figure}


%Hence a DL-Nash equilibrium and an SD-Nash equilibrium exists.



% 	\begin{figure}[h!]
% 		\centering
% 		\scalebox{0.5}{
% 	\begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
% 	  level distance = 1.5cm}]
% 	\node [arn_n] {\Large 1}
% 	    child{ node [arn_r] {\Large 2}
% 	            child{ node [arn_n] {\Large 1}
% 	            	child{ node [arn_r] {\Large 2}child{ node [arn_x] {}
% 		edge from parent node[left]{\Large$h_2$}
% 	}
% 	edge from parent node[left]{\Large$h_2$}
% 	}
% 		edge from parent node[above left]
%                  {\Large$h_1$}							
% 	            }
% 	            child{ node [arn_n] {\Large 1}
% 								child{ node [arn_r] {\Large 2}
% 								child{ node [arn_x] {}
% 					edge from parent node[left]{\Large$h_2$}
% 								}
% 						edge from parent node[left]{\Large$h_1$}	
% 								}
% 				edge from parent node[above right]{\Large$h_2$}
% 	            }
% 	edge from parent node[above left]{\Large$h_1$}
% 	    }
% 	%%%%%
% 	    child{ node [arn_r] {\Large 2}
% 	            child{ node [arn_n] {\Large1}
% 								child{ node [arn_r] {\Large 2}
% 								child{ node [arn_x] {}
% 						edge from parent node[left]{\Large$h_1$}
% 								}
% 						edge from parent node[left]{\Large$h_2$}
% 								}
% 						edge from parent node[above left]{\Large$h_1$}			
% 	            }
% 	            child{ node [arn_n] {\Large 1}
% 								child{ node [arn_r] {\Large 2}
% 								child{ node [arn_x] {}
% 	edge from parent node[left]{\Large$h_1$}
% 								}
% 							edge from parent node[left]{\Large$h_1$}		
% 								}
% 				edge from parent node[above right]{\Large$h_2$}		
% 							%	child{ node [arn_x] {}}
% 	            }
% 	edge from parent node[above right]{\Large$h_2$}	
% 			}
% 	;
% 	\end{tikzpicture}
% 	}
% 	\caption{A perfect information extensive form game based on breaking down the PS algorithm into a series of stages. For the case of two agents, each agent eats half a house in his turn. An agent has to continue eating a house if he eats it in a previous stage.
% 	}
% \label{fig:extensiveggame}
% \end{figure}


 % We also know that a DL-Nash equilibrium is an SD-Nash equilibrium because if there is an SD deviation, then it is also a DL deviation.


\section{Complexity of Pure Nash Equilibrium}

% \haris{I hope someone will read this section to verify the details. }

Our argument for the existence of a Nash equilibrium is constructive. However, naively constructing the extensive form game and then computing a subgame perfect Nash equilibrium requires exponential space and time. It is unclear whether a sub-game perfect Nash equilibrium or any Nash equilibrium preference profile can be computed in polynomial time.


\subsection{General Complexity Results}


In this section, we show that computing a PNE is NP-hard and verifying whether a profile is a PNE is coNP-complete. Recently it was shown that computing an expected utility best response is NP-hard~\citep{AGM+15b,AGM+15c}. Since equilibria and best responses are somewhat similar, one would expect that problems related to equilibria under PS are also hard. However, there is no general reduction from best response to equilibria computation or verification. In view of this, we prove results regarding PNE by closely analyzing the reduction in \citep{AGM+15b}.
First, we show that checking whether a given preference profile is in PNE under the PS rule is coNP-complete.


\begin{theorem}
	Given agents' utilities, checking whether a given preference profile is in PNE under the PS rule is coNP-complete.
	
	\end{theorem}
	
												\begin{proof}[Proof sketch]
									Consider the reduction from 3SAT to an assignment setting from~\citep{AGM+15b,AGM+15c}. We show that checking whether the truthful preference profile is in PNE is coNP-complete. The problem is in coNP, since a Nash deviation is a polynomial time checkable No-certificate.
									The original reduction considers one manipulator (agent 1) while the other agents $N\setminus \{1\}$ are `non-manipulators'. 
							In the original reduction, the utility functions of agents in $N'=N\setminus \{1\}$ are not specified. We specify the utility function of agents in $N'$ as follows: the utility of an agent in $N'$ for his $j$-th most preferred house is ${(8n)}^{m-j+1}$, where $n=|N|$ and $m$ is the number of houses. These utility functions can be represented in space that is polynomial in $O(n+m)$. We rely on 2 main observations about the original reduction.
							First, in the truthful profile, whenever an agent finishes eating a house all houses have either been fully allocated or are only at most half eaten.
							% Is the previous sentence true for the prize house?
							Second, in the truthful profile every house except the prize house (the last house that is eaten) is eaten by at least 2 agents.
							We  now show that due to the utility function constructed, each agent from $N'$ is compelled to report truthfully. 		
 Assume for contradiction that this is not the case, and let us consider the earliest house (when running the PS rule) that some agent $i\in N'$ starts to eat although he prefers another available house $h$. Let $k$ denote the number of agents who eat a fraction of $h$ under the truthful profile. 
	% Let us assume that $k\geq 2$.
						By reporting truthfully, we show that agent $i$ can get $\frac{1/n-1/{2n}}{2}=1/{4n}$  more of $h$ than by delaying eating $h$. 
						%To be precise it can get at least $\frac{1/n-1/{2n}}{2}=1/{4n}$ more of $h$. 
						Let us consider how much additional fraction of $h$ agent $i$ can consume by reporting truthfully. If he reports truthfully, he can start eating $h$ earlier and, in the worst case, he can only start $1/2n$ time units earlier. This means that $h$ is consumed earlier by a time of $1/2n$ if $i$ reports truthfully. Consider the time interval of length $1/2n$ between the time when $h$ is finished when $i$ is truthful about $h$ and the time $h$ is finished when $i$ delays eating $h$. In this last stretch of time interval $1/2n$, $i$ gets $\frac{1}{k}\cdot \frac{1}{2n}$ of $h$ extra when he does not report truthfully.
					%\todo[inline]{it $\rightarrow$ he? (mulyiple times)}
						%Thanks fixed!
						Hence by reporting truthfully, $i$ gets at least $\frac{1/n-1/kn}{2}$ more  of $h$ which is at least $1/4n$ since $k\geq 2$. Due to the utilities constructed, even if $i$ gets all the less preferred houses, he cannot make up for the loss in utility for getting only $1/4n$ of $h$. 
						
Now that we have established that the agents in $N'$ report truthfully in a PNE, it follows that the truthful preference profile is in PNE iff the manipulator's truthful report is his best EU response. Assuming that the  agents in $N\setminus \{1\}$ report truthfully, checking whether the truthful preference is agent $1$'s best response  was shown to be NP-hard.
We have shown that the agents $N'$ report truthfully in a PNE. Hence checking whether the truthful profile is in PNE is coNP-hard.
	\end{proof}			

% 												\begin{proof}[Proof sketch]
% 									Consider the reduction from 3SAT to an assignment setting from~\citep{AGM+15b,AGM+15c}. We show that checking whether the truthful preference profile is in PNE is NP-hard.
% 									The original reduction considers one manipulator (agent 1) while the other agents $N\setminus \{1\}$ are `non-manipulators'.
% 							In the original reduction, the utility functions of agents in $N'=N\setminus \{1\}$ are not specified. We specify the utility function of agents in $N'$ as follows: the utility of an agent in $N'$ for his $j$-th most preferred house is ${(8n)}^{m-j+1}$, where $n=|N|$ and $m$ is the number of houses. These utility functions can be represented in space that is polynomial in $O(n+m)$. We rely on 2 main observations about the original reduction.
% 							First, in the truthful profile, whenever an agent finishes eating a house all houses have either been fully allocated or are only at most half eaten.
% 							% Is the previous sentence true for the prize house?
% 							Second, in the truthful profile every house except the prize house (the last house that is eaten) is eaten by at least 2 agents.
% 							We may now show that due to the utility function constructed, each agent from $N'$ is compelled to report truthfully.
% 						We claim via induction that for the agents in $N'$, their truthful preference order is their unique expected utility best response. For the base case we show that each agent in $N'$ truthfully reports his most preferred house.
% 						Assume for contradiction that this is not the case, then there is a most preferred house $h$ of one of the agents $i\in N'$ that is not in the truthful position but later in the preference order.  If the agents in $N'$ report truthfully,
% 						Let $k$ be the number of agents who eat a fraction of $h$ under the truthful profile.
% 	% Let us assume that $k\geq 2$.
% 						By reporting truthfully, the agent in $N'$ can get a bit more of $h$ than by delaying eating $h$.
% 						To be precise it can get at least $\frac{1/n-1/{2n}}{2}=1/{4n}$ more of $h$.
% 						Let us consider how much additional fraction of $h$ that $i$ can consume by reporting truthfully. If he reports truthfully, he can start eating $h$ earlier and, even in the worst case, he can start $1/2n$ time units earlier. This means that $h$ is consumed earlier by a time of $1/2n$ if $i$ reports truthfully. Consider the time interval of length $1/2n$ between the time when $h$ is finished when $i$ is truthful about $h$ and the time $h$ is finished when $i$ delays eating $h.$ In this last stretch of time interval $1/2n$, $i$ gets $1/k\times 1/2n$ of $h$ extra when he does not report truthfully.
% 					%\todo[inline]{it $\rightarrow$ he? (mulyiple times)}
% 						%Thanks fixed!
% 						Hence by reporting truthfully, $i$ gets at least $\frac{1/n-1/kn}{2}$ more  of $h$ which is at least $1/4n$ if $k\geq 2$. Due to the utilities constructed, even if $i$ gets all the less preferred houses, he cannot make up for the loss in utility for getting only $1/4n$ of $h$. Now that we know that all agents in $N'$ report truthfully about their most preferred house, we inductively use the same argument. To show that they report truthfully for the subsequent houses
%
% 						Since the agents in $N'$ report truthfully in a PNE, it follows that the truthful preference profile is in PNE iff the manipulator's truthful report is his best EU response. Assuming that the  agents in $N\setminus \{1\}$ report truthfully, checking whether the truthful preference is agent $1$'s best response  was shown to be NP-hard.
% We have shown that the agents $N'$ report truthfully in a PNE. Hence checking whether the truthful profile is in PNE is NP-hard.
% 	\end{proof}

			
			


Next, we show that computing a PNE with respect to the underlying utilities of the agents is NP-hard.

% \begin{theorem}
% 	Given agents' utilities, checking whether a given preference profile is in PNE under the PS rule is coNP-complete.
%
% 	\end{theorem}
	
	
	\begin{theorem}\label{th:verifyPNE-NPhard}
	Given agent's utilities, computing a preference profile that is in PNE under the PS rule is NP-hard.		
		\end{theorem}
			\begin{proof}
				The same argument as above shows that the  agents in $N'$ play truthfully in a PNE. Hence, a preference profile is in PNE iff agent $1$ reports his EU best response.
		It has already been shown that computing this EU best response is NP-hard~\citep{AGM+15b} when the other agents are $N\setminus \{1\}$ and report truthfully. %By a similar argument, it can also be shown that computing agent 1's EU best response is NP-hard when the other agents are $N'$ and they report truthfully. 
		Thus computing a PNE is NP-hard.
				\end{proof}
	% \begin{proof}
	% 	The problem is in coNP, since a Nash deviation is a polynomial time checkable No-certificate.
	% 	The argument above shows that the  agents in $N'$ play truthfully in a PNE and that the manipulator must declare a preference profile corresponding to a satisfying assignment if one exists. Therefore answering if the preference profile consisting of all truthful preferences is a PNE is equivalent to asking if there is no satisfying assignment for the corresponding Boolean formula.
	% \end{proof}
	
	

\subsection{Case of Two Agents}


In this section, we consider the case of two agents since many disputes involve two parties. Since an EU best response can be computed in linear time for the case of two agents~\citep{AGM+15b,AGM+15c}, it follows that it can be verified whether a profile is a PNE in polynomial time as well. 


We can prove the following theorem for the ``threat profile'' whose construction is shown in Algorithm~\ref{algo:2agent-DL-Nash}.

		%We show that if the number of agents is two, then there exists linear-time algorithms for the problem. Under PS and for two agents, there exists a preference profile that is in DL-Nash equilibrium. We will call the particular preference profile we identify as the ``threat profile''.
		% For two agents, a DL best response gives the same allocation as an EU best response. Hence a DL-Nash equilibrium is also an EU Nash equilibrium.

		%\begin{corollary}
			%A DL-Nash equilibrium and an SD-Nash equilibrium exists.
		%\end{corollary}




		%
		% 	\begin{figure}
		% 		\centering
		% 		\scalebox{0.5}{
		% 	\begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 5cm/#1,
		% 	  level distance = 1.5cm}]
		% 	\node [arn_n] {\Large 1}
		% 	    child{ node [arn_r] {\Large 2}
		% 	            child{ node [arn_n] {\Large 1}
		% 	            	child{ node [arn_r] {\Large 2}child{ node [arn_x] {}
		% 		edge from parent node[left]{\Large$h_2$}
		% 	}
		% 	edge from parent node[left]{\Large$h_2$}
		% 	}
		% 		edge from parent node[above left]
		%                  {\Large$h_1$}							
		% 	            }
		% 	            child{ node [arn_n] {1}
		% 								child{ node [arn_r] {\Large 2}
		% 								child{ node [arn_x] {}
		% 					edge from parent node[left]{\Large$h_2$}
		% 								}
		% 						edge from parent node[left]{\Large$h_1$}	
		% 								}
		% 				edge from parent node[above right]{\Large$h_2$}
		% 	            }
		% 	edge from parent node[above left]{\Large$h_1$}
		% 	    }
		% 	%%%%%
		% 	    child{ node [arn_r] {\Large 2}
		% 	            child{ node [arn_n] {\Large1}
		% 								child{ node [arn_r] {\Large 2}
		% 								child{ node [arn_x] {}
		% 						edge from parent node[left]{\Large$h_1$}
		% 								}
		% 						edge from parent node[left]{\Large$h_2$}
		% 								}
		% 						edge from parent node[above left]{\Large$h_1$}			
		% 	            }
		% 	            child{ node [arn_n] {1}
		% 								child{ node [arn_r] {\Large 2}
		% 								child{ node [arn_x] {}
		% 	edge from parent node[left]{\Large$h_1$}
		% 								}
		% 							edge from parent node[left]{\Large$h_1$}		
		% 								}
		% 				edge from parent node[above right]{\Large$h_2$}		
		% 							%	child{ node [arn_x] {}}
		% 	            }
		% 	edge from parent node[above right]{\Large$h_2$}	
		% 			}
		% 	;
		% 	\end{tikzpicture}
		% 	}
		% 	\caption{A perfect information extensive form game based on breaking down the PS algorithm into a series of stages. For the case of two agents, each agent eats half a house in his turn. An agent has to continue eating a house if he eats it in a previous stage.
		% 	}
		%
		% \end{figure}

		% \begin{theorem}
		% For two agents, a DL best response gives the same allocation as an EU best response. Hence a DL-Nash equilibrium is also an EU Nash equilibrium.
		% \end{theorem}
		% \begin{proof}
		%
		% \end{proof}



		%
		% We first show that PS has some intimate connections with sequential allocation of houses. Let $\pi^1$ be the discrete assignment mechanism corresponding to alternating policy $1212...$ in which agent $1$ selects his most preferred object, then agent $2$ selects his most preferred object from among the remaining objects and so on. Similarly, let $\pi^2$ be the discrete assignment mechanism corresponding to alternating policy $2121...$.
		%
		% \begin{theorem}
		% 	$1/2(\pi^1(N,H,\pref))+1/2(\pi^2(N,H,\pref))=PS(N,H,\pref)$.
		% \end{theorem}
		% \begin{proof}
		% We prove by induction on the number of stages, where each stage indicates the simultaneous eating of two different houses or the same house. The base case for stage number one holds. Now assume that the statement holds for all stages up to $k$. Then, for the $k+1$-st stage either the agents eat the same house $h$ or they eat different houses $h'$ and $h''$.
		% Let $\pi'$ and $\pi''$ be the distinct orderings in $\{\pi^1,\pi^2\}$.
		% Then, if agent $1$ gets $h$ in $\pi$, then it does not get $h$ in $\pi''$.
		% On the other hand, if the agents eat different houses $h'$ and $h''$, then agent $1$ gets $h$ in both $\pi'$ and $\pi''$.
		% \end{proof}
		%

		%\begin{theorem}
			%For the sequential allocation problem with alternating policy, the expected utility best response allocation is equivalent to the DL best response allocation.
		%\end{theorem}
		%\begin{proof}
			%Consider the algorithm in \citep[Problem~1, ][]{KoCh71a} to compute an expected utility best response.
			%From the construction of the algorithm it is also clear that the best response is also a DL best response. The reason is that for each $h_i$ in $h_1,\ldots, h_m$, it tries to allocate $h_i$ to the manipulator while making sure that the set of objects allocated to him among $h_1,\ldots, h_{i-1}$ still remain allocated to him.
		%\end{proof}
			%
			%The response is independent of the cardinal utilities specified by the agents to the objects. Hence the optimal response of the a




		%
		%\begin{lemma}
			%DL-Nash equilibrium is also an SD-Nash equilibrium.
		%\end{lemma}
		%\begin{proof}
			%If there is an SD deviation, then it is also a DL deviation.
		%\end{proof}



		% \begin{example}\label{example:manip1}
		% \begin{align*}
		% 	\succ_1:\quad& h_1,h_2,h_3,h_4\\
		% 	\succ_2:\quad& h_2,h_3,h_1,h_4
		% 	\end{align*}
		% 	
		% 	
		% 	\begin{align*}
		% 		\succ_1':\quad& h_4,h_1,h_3,h_2\\
		% 		\succ_2':\quad& h_4,h_3,h_2,h_1
		% 		\end{align*}
		% 	
		% 	
		% 		\[
		% 		PS(\succ_1,\succ_2)=\begin{pmatrix}
		% 		  1 & 0 & 1/2 & 1/2 \\
		% 		  0 & 1 & 1/2 & 1/2
		% 		 \end{pmatrix}
		% 		\]
		% 	
		%
		% \[
		% PS(\succ_1',\succ_2')=\begin{pmatrix}
		%   1 & 1/2 & 0 & 1/2 \\
		%   0 & 1/2 & 1 & 1/2
		%  \end{pmatrix}
		% \]
		%
		% $PS(\succ_1',\succ_2')$ is not an SD Nash equilibrium because agent $2$ can submit the following preference:
		%
		% \begin{align*}
		% 	\succ_2'':\quad& h_3,h_2,h_1, h_4
		% 	\end{align*}
		%
		%
		% 	\[
		% 	PS(\succ_1',\succ_2'')=\begin{pmatrix}
		% 	  1 & 0 & 0 & 1 \\
		% 	  0 & 1 & 1 & 0
		% 	 \end{pmatrix}
		% 	\]
		%
		% Even this is not an SD Nash equilibrium
		%
		%
		% \end{example}



		



		\begin{theorem}\label{th:threat}
			Under PS and for two agents, there exists a preference profile that is in DL-Nash equilibrium and results in the same assignment as the assignment based on the truthful preferences. Moreover, it can be computed in linear time.
		\end{theorem}
		\begin{proof}
			The proof is by induction over the length of the constructed preference lists.
			The main idea of the proof is that if both agents compete for the same house then they do not have an incentive to delay eating it. If the most preferred houses do not coincide, then both agents get them with probability one but will not get them completely if they delay eating them. The algorithm is described as Algorithm~\ref{algo:2agent-DL-Nash}.
		
		% Let the preferences of agents 1 and 2 be represented by the lists $P_1$ and $P_2$. We present an algorithm to compute preferences $Q_1$ and $Q_2$ that are in DL-Nash equilibrium.
		% Initialise $Q_1$ and $Q_2$ to empty lists. Now consider the maximal elements  $h$ from $P_1$ and $h'$ from $P_2$.
		% Element $h$ is appended to the list $Q_1$ and $h'$ is appended to the list $Q_2$. At the same time  $h$ is deleted from $P_1$ and $h'$ is deleted from $P_2$. Now if $h\neq h'$, then $h'$ is appended to $Q_1$ and $h'$ is appended to $Q_2$. The process is repeated until $P_1$ and $P_2$ are empty. The algorithm is described as Algorithm~\ref{algo:2agent-DL-Nash}.

%\todo[inline]{If we need to save space, the remainder of the proof can be skipped if we make it a proof sketch.}

		We now prove that $Q_1$ is a DL best response against $Q_2$ and $Q_2$ is a DL best response against $Q_1$. The proof is by induction over the length of the preference lists.
		For the first elements in the preference lists $Q_1$ and $Q_2$, if the elements coincide, then no agent has an incentive to put the element later in the list since the element is both agents' most preferred house. If the maximal elements do not coincide i.e. $h\neq h'$, then $1$ and $2$ get $h$ and $h'$ respectively with probability one. However they still need to express these houses as their most preferred houses because if they don't, they will not get the house with probability one. The reason is that $h$ is the next most preferred house after $h'$ for agent $2$ and $h'$ is the next most preferred house after $h$ for agent $1$. Agent $1$ has no incentive to change the position of $h'$ since $h'$ is taken by agent $2$ completely before agent $1$ can eat it. Similarly, agent $2$ has no incentive to change the position of $h$ since $h$ is taken by agent $1$ completely before agent $2$ can eat it.
		Now that the positions of $h$ and $h'$ have been completely fixed, we do not need to consider them and can use induction over $Q_1$ and $Q_2$ where $h$ and $h'$ are deleted.
			\end{proof}


		The desirable aspect of the threat profile is that since it results in the same assignment as the assignment based on the truthful preferences, the resulting assignment satisfies all the desirable properties of the PS outcome with respect to the original preferences. 
	Since a DL best response algorithm is also an EU best response algorithm for the case of two agents~\citep{AGM+15c}, we get the following corollary.



		%\begin{proof}
		%Let the original preferences of agent 1 and agent 2 be represented by lists $P_1$ and $P_2$. We present an algorithm to compute preferences $Q_1$ and $Q_2$ that are in DL-Nash equilibrium.
		%Initialise $Q_1$ and $Q_2$ to empty lists. Now consider the maximal elements  $h$ from $P_1$ and $h'$ from $P_2$.
		%Element $h$ is appended to the list $Q_1$ and $h'$ is appended to the list $Q_2$. At the same time  $h$ is deleted from $P_1$ and $h'$ is deleted from $P_2$. Now if $h\neq h'$, then $h'$ is appended to $Q_1$ and $h'$ is appended to $Q_2$. The process is repeated until $Q_1$ and $Q_2$ are complete lists and $P_1$ and $P_2$ are empty lists. The algorithm is described as Algorithm~\ref{algo:2agent-DL-Nash}.
		%
		%
		%We now prove that $P_1$ is a DL best response against $P_2$ and $P_2$ is a DL best response against $P_1$. The proof is by induction over the length of the preference lists.
		%For the first elements in the preference lists $P_1$ and $P_2$, if the elements coincide, then no agent has an incentive to put the element later in the list since the element is both agents' most preferred house. If the maximal elements do not coincide i.e. $h\neq h'$, then $1$ and $2$ get $h$ and $h'$ respectively with probability one. However they still need to express these houses as their most preferred houses because if they don't, they will not get the house with probability one. The reason is that $h$ is the next most preferred house after $h'$ for agent $2$ and $h'$ is the next most preferred house after $h$ for agent $1$. Agent $1$ has no incentive to change the position of $h'$ since $h'$ is taken by agent $2$ completely before agent $1$ can eat it. Similarly, agent $2$ has no incentive to change the position of $h$ since $h$ is taken by agent $1$ completely before agent $2$ can eat it.
		%Now that the positions of $h$ and $h'$ have been completely fixed, we do not need to consider them and we reason in the same manner over the updated lists $P_1$ and $P_2$.
			%\end{proof}



		% From the previous section, we know that for two agents, an EU best response is a best response with respect to any utilities. Since PS for two agents only involves fractions $0,\frac{1}{2}$, and $1$, hence a DL best response is also equivalence to an EU best response.


		\begin{corollary}
			Under PS and for 2 agents, there exists a preference profile that is in Nash equilibrium for any utilities consistent with the ordinal preferences. Moreover it can be computed in linear time.
		\end{corollary}

		%\begin{corollary}
			%Under PS and for two agents, there exists a preference profile that is in SD-Nash equilibrium. Moreover it can be computed in linear time.
		%\end{corollary}
		
		
		
		\begin{algorithm}[tb]
			  \caption{Threat profile DL-Nash equilibrium for $2$ agents (which also is an EU-Nash equilibrium) which provides the same allocation as the truthful profile.}
			  \label{algo:2agent-DL-Nash}
			\renewcommand{\algorithmicrequire}{\wordbox[l]{\textbf{Input}:}{\textbf{Output}:}}
			 \renewcommand{\algorithmicensure}{\wordbox[l]{\textbf{Output}:}{\textbf{Output}:}}
			 \footnotesize
			% \begin{algorithmic}
				\textbf{Input:}  $(\{1,2\},H,(\succ_1,\succ_2))$\\
				\textbf{Output:} The \emph{``threat profile''} $(Q_1,Q_2)$ where $Q_i$ is the preference list of agent $i$ for $i\in \{1,2\}$.
			% \end{algorithmic}
				%	\footnotesize
			\algsetup{linenodelimiter=\,}
			  \begin{algorithmic}[1]
				   \footnotesize
		\STATE Let $P_i$ be the preference list of agent $i\in \{1,2\}$
		%Let the original preferences of agent 1 and agent 2 be represented by lists $P_1$ and $P_2$.
		\STATE
		Initialise $Q_1$ and $Q_2$ to empty lists.
		\WHILE{$P_1$ and $P_2$ are not empty}
		\STATE Let $h= \text{first}(P_1)$ and $h'=\text{first}(P_2)$
		\STATE Append $h$ to $Q_1$; Append $h'$ to $Q_2$
		%Serge's comment implemented below.
%		\STATE Delete $h$ from $P_1$; Delete $h'$ from $P_2$
%		\todo[inline]{I believe $h'$ should be deleted from $P_1$ as well and $h$ from $P_2$. Should this be changed to the following?\newline
%			Delete $h$ and $h'$ from $P_1$ and $P_2$}
		\STATE Delete $h$ and $h'$ from $P_1$ and $P_2$
		\IF{$h\neq h'$}
		\STATE Append $h'$ to $Q_1$; Append $h$ to $Q_2$;
		\ENDIF
		\ENDWHILE	

		\RETURN $(Q_1,Q_2)$.

			 \end{algorithmic}
			\end{algorithm}
	
		
	

		
		%
% 			In this next example, we show how Algorithm~\ref{algo:2agent-DL-Nash} is used to compute a preference profile that is in DL-Nash equilibrium. The example also shows that it can be the case that one preference profile is in DL-Nash equilibrium and the other is not, even if both profiles yield the same outcome.
%
%
%
% 			\begin{example}[Computing a threat profile]\label{example:manip1} Consider the preferences:
% 				\begin{align*}
% 					\succ_1:\quad& h_1,h_2,h_3,h_4&\succ_2:\quad& h_2,h_3,h_1,h_4.%\\
% 				%	\succ_2:\quad& h_2,h_3,h_1,h_4
% 					\end{align*}
% 			We use Algorithm~\ref{algo:2agent-DL-Nash} to compute a preference profile $(\succ_1',\succ_2')$ that is in DL-Nash equilibrium:
% \begin{align*}
% 					\succ_1':\quad& h_1,h_2,h_3,h_4& \succ_2':\quad& h_2,h_1, h_3,h_4.
% \end{align*}
% \vspace{-1em}
% \[
% PS(\succ_1,\succ_2) = PS(\succ_1',\succ_2')=\begin{pmatrix}
% 			  1 & 0 & 1/2 & 1/2 \\
% 			  0 & 1 & 1/2 & 1/2
% 			 \end{pmatrix}.
% \]
%
% \noindent
% Although $PS(\succ_1,\succ_2)=PS(\succ_1',\succ_2')$, we see that $(\succ_1,\succ_2)$ is not a DL-Nash equilibrium (agent 1 can swap $h_1$ and $h_2$ in $\succ_1$ to receive strictly more utility).
%
% 			% \begin{align*}
% 			% 		\succ_1':\quad& h_1,h_2,h_3,h_4&
% 			% 		\succ_2':\quad& h_2,h_1 h_3,h_4
% 			% 		\end{align*}
% 				% \[
% 				% 	PS(\succ_1',\succ_2')=\begin{pmatrix}
% 				% 	  1 & 0 & 1/2 & 1/2 \\
% 				% 	  0 & 1 & 1/2 & 1/2
% 				% 	 \end{pmatrix}.
% 				% 	\]
%
% 			\end{example}




			% In this next example, we show how Algorithm~\ref{algo:2agent-DL-Nash} is used to compute a preference profile that is in DL-Nash equilibrium. The example also shows that it can be the case that one preference profile is in DL-Nash equilibrium and the other is not, even if both profiles yield the same outcome.



			% \begin{example}[Computing a threat profile]\label{example:manip1}
			% 	\begin{align*}
			% 		\succ_1:\quad& h_1,h_2,h_3,h_4&\succ_2:\quad& h_2,h_3,h_1,h_4%\\
			% 	%	\succ_2:\quad& h_2,h_3,h_1,h_4
			% 		\end{align*}
			% 
			% We now use Algorithm~\ref{algo:2agent-DL-Nash} to compute a preference profile that is in DL-Nash equilibrium.
			% \begin{align*}
			% 	\succ_1':\quad& h_1,h_2,h_3,h_4&\succ_2':\quad& h_2,h_1 h_3,h_4
			% 	\end{align*}
			% 	\[
			% 	PS(\succ_1',\succ_2')=\begin{pmatrix}
			% 	  1 & 0 & 1/2 & 1/2 \\
			% 	  0 & 1 & 1/2 & 1/2
			% 	 \end{pmatrix}.
			% 	\]
			% 	Although $PS(\succ_1,\succ_2)=PS(\succ_1',\succ_2')$, we see that $(\succ_1',\succ_2')$ is in DL-Nash equilibrium but
			% $(\succ_1,\succ_2)$ is not!	
			% \end{example}
			
	
	
	
	%%commenting out		
	% 	In the sequential allocation setting $(N,O,\pref',\pi)$, there is an agent set $N$, an object set $O=\{o_1,\ldots o_{m'}\}$, a preference profile $\pref'$ that specifies for each agent $i\in N$ his preferences $\pref_i'$ over $O$,
% 		and a policy $\pi:\{1,\ldots, m'\}\rightarrow N$. The sequential allocation rule works as  follows. Starting from $j=1$ to $m'$, agent $\pi(j)$ gets his most preferred object that is not yet allocated. If no unallocated object is on the preference list of the agent, then the agent does not get any object when his turn comes. The assignment as a result of sequential allocation is denoted by $SA(N,O,\pref',\pi)$.
% 		We will restrict ourselves to the case where $N=\{1,2\}$ and will only consider the alternating policy $\pi^*=1212\ldots$ in which agent $1$ starts first and then the agents keep alternating. The sequential allocation setting was introduced by
% 		~\citet{KoCh71a} where they showed that the best response can be computed in linear time when $|N|=2$ and the policy is the alternating sequence.
%
% 		For the random assignment setting $(\{1,2\},H,\pref)$, the \emph{half-house reduction} gives us the sequential allocation setting $(\{1,2\},O,\pref',\pi^*)$. In the reduction, each house $h_j\in H$ is cloned so that we have two half-houses $h_j^1$ and $h_j^2$ for each house $h_j$:  $O=\{h_j^1,h_j^2\midd j=1,\ldots, m\}$.  Both agents have preferences over half-houses that are consistent with their preferences over houses and for each house, each agent prefers the first half-house slightly more than the second half-house: if $h_j\pref_i h_k$, then $h_j^{1}\pref_i' h_j^{2}\pref_i'h_k^{1}\pref_i' h_k^2$.
% 					We note that in the half-house reduction, each preference list $\pref_i'$ satisfies the \emph{consecutivity property}: half-houses corresponding to the same house are placed consecutively in the preference list. We will use the consecutivity property in our argument.
%
%
% 			Next we show how our identified links with sequential allocation of indivisible houses leads us to another Nash equilibrium profile called the \emph{crossout profile}. The algorithm to compute the crossout profile is stated as  Algorithm~\ref{algo:2agent-DL-crossout-Nash}.
%
%
% 			\begin{algorithm}[tb]
% 				  \caption{Crossout profile DL-Nash equilibrium for $2$ agents (which also is an EU Nash equilibrium)}
% 				  \label{algo:2agent-DL-crossout-Nash}
%
% 				\renewcommand{\algorithmicrequire}{\wordbox[l]{\textbf{Input}:}{\textbf{Output}:}}
% 				 \renewcommand{\algorithmicensure}{\wordbox[l]{\textbf{Output}:}{\textbf{Output}:}}
% 				% \begin{algorithmic}
% 					\textbf{Input:}  $(\{1,2\},H,(\succ_1,\succ_2))$\\
% 					\textbf{Output:}  The \emph{``crossout profile''} $(Q_1,Q_2)$ where $Q_i$ is the preference list of agent $i$ for $i\in \{1,2\}$.
% 				% \end{algorithmic}
%
% 				\algsetup{linenodelimiter=\,}
% 				  \begin{algorithmic}[1]
% 			\STATE Let $P_i'$ be the preference of agent $i\in \{1,2\}$ in the half-house reduction of
% 			$(\{1,2\},H,\pref)$.
% 			%Let the original preferences of agent 1 and agent 2 be represented by lists $P_1$ and $P_2$.
% 			\STATE
% 			Initialise $Q_1'$ and $Q_2'$ to empty lists.
% 			\WHILE{$P_1'$ and $P_2'$ are not empty}
% 			\STATE Let $h= last(P_1')$; Prepend $h$ to $Q_2'$; Delete $h$ from $P_1'$ and $P_2'$;
% 						\STATE Let $h= last(P_2')$; Prepend $h$ to $Q_1'$; Delete $h$ from $P_1'$ and $P_2'$;
% 			% % and $h'=last(P_2')$
% 			% \STATE Prepend $h$ to $Q_2'$%; Prepend $h'$ to $Q_1'$
% 			% \STATE Delete $h$ from $P_1'$ and $P_2'$; %Delete $h'$ from $P_2'$ and $P_1'$
% 			\ENDWHILE
% 			\STATE extend $Q_1'$ and $Q_2'$ to have the consecutivity property but the same allocation.
% 			\STATE Implement the inverse of the house-house reduction to get corresponding profile $(Q_1,Q_2)$ from the sequential allocation setting profile $(Q_1',Q_2')$.
% 			%change $Q_1$ and $Q_2$ via the order-preserving join of $Q_1'$ and $Q_2'$.
% 			\RETURN $(Q_1,Q_2)$.
%
% 				 \end{algorithmic}
% 				\end{algorithm}
%
%
%
% 				%
% 				% \begin{algorithm}[h!]
% 				% 	  \caption{Crossover profile DL-Nash equilibrium for $2$ agents (which also is an EU Nash equilibrium)}
% 				% 	  \label{algo:2agent-DL-crossout-Nash}
% 				% 	\small
% 				% 	\renewcommand{\algorithmicrequire}{\wordbox[l]{\textbf{Input}:}{\textbf{Output}:}}
% 				% 	 \renewcommand{\algorithmicensure}{\wordbox[l]{\textbf{Output}:}{\textbf{Output}:}}
% 				% 	\begin{algorithmic}
% 				% 		\REQUIRE $(\{1,2\},H,(\succ_1,\succ_2))$
% 				% 		\ENSURE The \emph{``crossout profile''} $(Q_1,Q_2)$ where $Q_i$ is the preference list of agent $i$ for $i\in \{1,2\}$.
% 				% 	\end{algorithmic}
% 				% 	\algsetup{linenodelimiter=\,}
% 				% 	  \begin{algorithmic}[1]
% 				% \STATE Let $P_i'$ be the order-preserving bisection of preference list of agent $i\in \{1,2\}$
% 				% %Let the original preferences of agent 1 and agent 2 be represented by lists $P_1$ and $P_2$.
% 				% \STATE
% 				% Initialise $Q_1'$ and $Q_2'$ to empty lists.
% 				% \WHILE{$P_1'$ and $P_2'$ are not empty}
% 				% \STATE Let $h= last(P_1')$ and $h'=last(P_2')$
% 				% \STATE Prepend $h$ to $Q_2'$; Prepend $h'$ to $Q_1'$
% 				% \STATE Delete $h$ from $P_1'$ and $P_2'$; Delete $h'$ from $P_2'$ and $P_1'$
% 				% \ENDWHILE
% 				% \STATE extend $Q_1'$ and $Q_2'$ to have the consecutivity property but the same allocation.
% 				% \STATE change $Q_1$ and $Q_2'$ via  order-preserving join of $Q_1'$ and $Q_2'$.
% 				% \RETURN $(Q_1,Q_2)$.
% 				%
% 				% 	 \end{algorithmic}
% 				% 	\label{algo:subroutine}
% 				% 	\end{algorithm}
%
%
% 				In Algorithm~\ref{algo:2agent-DL-crossout-Nash}, the Nash equilibrium problem for PS is changed into the same problem for sequential allocation by changing each house into a half house. The idea behind the crossout profile for the sequential allocation setting is that no agent will choose the least preferred object unless it is the only object left. Thus agent $2$ will be forced to get the least preferred object of agent $1$~\citep{LeSt12a,KoCh71a}. In Algorithm~\ref{algo:2agent-DL-crossout-Nash}, we use this idea recursively to build sequences of objects 	$Q_1'$ and $Q_2'$ for each agent that are allocated to them.
% 	% 			\haris{The following text is very imprecise...}
% 	% If one agent gets a half house and the other agent gets the other half house, it can be proved that the positions of the half houses in $Q_1'$ and $Q_2'$ are same.
%
% This sequence of objects for each agent is then extended to preferences that give the same allocations under sequential allocation and which also satisfy the consecutivity property. The preferences for the sequential allocation are then transformed via the inverse of the half-house reduction  to obtain the crossout Nash equilibrium profile for the PS rule. Due to the argument in the proof of Theorem~2 in \citep{AGM+15b},
% the preference profile $(Q_1,Q_2)$ has a better response for an agent under PS iff $(Q_1',Q_2')$ has a better response for an agent under SA.
% Next we show that the threat profile and crossout profile are different and may also give different assignments.
%
% \begin{example}[Crossout profile]\label{example:crossover}
% Consider the following profile.
% \begin{align*}
% 	\succ_1:\quad& h_1,h_2,h_3,h_4&\succ_2:\quad& h_2,h_3,h_1,h_4
% \end{align*}
%
% We now use Algorithm~\ref{algo:2agent-DL-crossout-Nash} to compute a preference profile $(\succ_1',\succ_2')$ that is in DL-Nash equilibrium:
% \begin{align*}
% 	\succ_1':\quad& h_2,h_1,h_4,h_3&\succ_2':\quad& h_2,h_3 ,h_4,h_1
% \end{align*}
% \[
% 		PS(\succ_1',\succ_2')=\begin{pmatrix}
% 				  1 & 1/2 &0 & 1/2 \\
% 				  0 & 1/2 & 1 & 1/2
% \end{pmatrix}.
% \]
%
% Note that the crossout Nash equilibrium profile is different from the threat Nash equilibrium profile for the problem instance. %Hence there can be multiple Nash equilibria.
%
% 							% 							\succ_1':\quad& h_2,h_1,h_4,h_3&
% 							% \succ_2':\quad& h_2,h_3 ,h_4,h_1
%
% 							% \begin{align*}
% 							% 							\succ_1':\quad& h_2,h_1,h_4,h_3&
% 							% \succ_2':\quad& h_2,h_3 ,h_4,h_1
% 							% 							\end{align*}
% 							% 							\[
% 							% 							PS(\succ_1',\succ_2')=\begin{pmatrix}
% 							% 							  1 & 1/2 &0 & 1/2 \\
% 							% 							  0 & 1/2 & 1 & 1/2
% 							% 							 \end{pmatrix}.
% 							% 							\]
%
%
%
% 							\end{example}
%
%

%commented out!



\begin{figure*}[ht!]
\centering
\includegraphics[width=0.9\textwidth]{./fig/increase_decrease}
\caption{Classification of equilibria 
in settings consisting of four agents with preferences drawn from the six models over 2 to 4 houses.
We can see that the vast majority of the equilibria that were 
found across all samples had the same social welfare as the
truthful profile. In general, we see there are roughly the same number of
equilibria that increase or decrease social welfare.}
\label{fig:percent-change}
\end{figure*}

\begin{figure*}[ht!]
\begin{minipage}[b]{0.65\textwidth}
	\centering
	\includegraphics[width=.9\textwidth]{./fig/percent_change}
	(A)
\end{minipage}
\hfill
\begin{minipage}[b]{0.33\linewidth}
	\centering
	\includegraphics[width=.9\textwidth]{./fig/avg_num_nash}
	(B)
\end{minipage}	
\caption{(A) The maximum and minimum percentage increase 
or decrease in social welfare over all 300 samples for each of the six models with
2 to 4 houses and four agents.  We see 
that the gain of the best profile is, in general, slightly
more than the loss in the worst profile with respect to the truthful profile. (B) The average
number of the $4!^4=331,776$ profiles that are in 
equilibria per instance across all combinations of parameters.  The more uncorrelated
models (IC and SP-IC) admit the highest number of equilibria.}
\label{fig:increase-num}
\end{figure*}

\section{Experiments}

%\haris{Let's stick to houses not items or objects or resources for the sake of consistency. I have made this consistent for the other sections for now. }
%\nick{cool!, updated graphics.}

We conducted a series of experiments to understand the number and quality
of equilibria that are possible under the PS rule. 
For quality, we use the utilitarian social welfare (SW) function, i.e., the sum of the utilities of the agents.
%  In earlier
% experiments we found that,
% though single agent manipulation under the PS rule was NP-hard,
% randomized or brute force search was often and easily able to
% find an beneficial misreporting.  These misreports, which were
% beneficial to a single agent, sometimes \emph{increased} the overall
% utility of the assignment.
We are
limited by the large search space needed to examine equilibria.  
For instance, for each set of cardinal preferences we generate, we
% need to
consider all misreports ($m!$) for all agents ($n$) leaving us with a search 
space of size $m!^n$ for each of the samples for each combination of parameters. % of the models we checked.
Thus, we only report results for small numbers of agents and houses in this section.  
We generated 300 samples for each combination 
of preference model, number of agents, and number of items; reporting
the aggregate statistics for these experiments for 4 agents 
in Figures~\ref{fig:percent-change} and ~\ref{fig:increase-num}.
Each individual sample with 4 agents and 4 houses took about 15 minutes to complete using one core on
an Intel Xeon E5405 CPU running at 2.0 GHz with 4 GB of RAM running Debian 2.6.32.
The results for 2 agents and up to 5 houses as well as 3 agents and up to 4 houses are similar.


We used a variety of common statistical models to generate data (see, e.g.,~\cite{Matt11a,Mall57a,LuBo11a,Berg85a}):
the Impartial Culture (\textbf{IC}) model generates all 
preferences uniformly at random; the Single Peaked Impartial Culture
(\textbf{SP-IC}) generates all preference profiles that are single peaked
uniformly at random; Mallows Models (\textbf{Mallows}) is a correlated
preference model where the population is distributed around a 
reference ranking proportional to the Kendall-Tau distance; 
Polya-Eggenberger Urn Models (\textbf{Urn}) creates correlations
between the agents, once a preference order has been randomly
selected, it is subsequently selected with higher probability.
In our experiments we set the probability that the second order
is equivalent to the first to 0.5.
We also used real world data from
\textsc{PrefLib}
\cite{MaWa13a}: AGH Course Selection (ED-00009). This data 
consists of students bidding on courses to attend in 
the next semester.  We sampled students
from this data (with replacement) as the agents after 
we restricted the preference 
profiles to a random set of houses of a specified size. 

To compare the different allocations achieved under PS we need 
to give each agent not only a preference order but also a utility for each
house.  Formally we have, for all $i \in N$ and all $h_j \in H$, a value $u_i(h_j) \in \reals$.
To generate these utilities we use what we call the \emph{Random} model: 
we uniformly at random generate a real number between $0$ and 
$1$ for each house.  We sort this list in strictly decreasing order, if we cannot, 
we generate a new list (we discarded 0 lists in our experiments). 
We normalize these utilities such that each agent's utility sums to a constant value (here, the number of houses)
that is the same for all agents. In prior experiments we 
found the Random utility model to be the most manipulable and admit
the worst equilibria.
Therefore, we only focus on this utility model here 
(over Borda or Exponential utilities) as it represents, empirically, a worst case.
% Our central question is, \emph{how bad can non-truthful equilibria be?}
% To answer this question we need to able to objectively compare two equilibria.
% We use the utilitarian social welfare (SW) of the agents at equilibria as our measuring stick,
% i.e. $\sum_{i \in N,h_j \in H} p(i)(h_j) \cdot u_i(h_j)$.
We separate equilibria into three categories: those where the SW is the same
as in the truthful profile, those where we have a decrease in SW, 
and those where we have an increase in SW.  
% We compare the percentage difference of $SW_$ SW under a PNE with that under the truthful profile as follows:
%
Given the social 
welfare of two different profiles, $SW_1$ and $SW_2$, we use percentage
change ($\frac{|SW_1 - SW_2|}{SW_1}\cdot 100$) to understand the magnitude of this difference.


For all models, for all combinations of 2 to 4 agents and 2 to 5 houses there are, generally, 
slightly more equilibria that increase social welfare compared to the truthful profile than those 
that decrease it, as illustrated in Figure~\ref{fig:percent-change}.  However, the vast majority
of equilibria have the same social welfare as the truthful profile, and the 
best equilibria are, in general, slightly better than the worst
equilibria, as illustrated in Figure~\ref{fig:increase-num}.  Hence, if any or all of the 
agents manipulate, there may be a loss of SW at equilibria,
but there is also the potential for large gains; and the most common outcome of all these 
agents being strategic is that, dynamically, we will wind up in an equilibria 
which provides the same SW as the truthful one.  
%These results
%seem to be slightly more pronounced in situations where the preference profiles have a strong degree of %correlation, 
%such as the Urn and AGH 2004 models, but all generative and real world models showed the same trends. 
Our main observations are:
% \bigskip
% \noindent
% \textbf{Key Messages}
\begin{inparaenum}[(i)]
\item The vast majority of equilibria have social welfare
equal to the social welfare in the truthful profile.
\item In general, the number of PNE that have
increased social welfare (with respect to the truthful profile) is slightly more than the  
number of PNE that have decreased social welfare.
\item The maximum increase and decrease in SW in equilibria compared to the truthful profile was observed to be under 23\% and 18\% respectively .
% \item However, those equilibria with increased
% social welfare than the truthful profile, in general,
% have slightly higher overall social welfare (up to 20\% increase).
% \item Equilibria with decreased
% social welfare than the truthful profile, in general,
% have slightly less overall social welfare (up to 22\% decrease).
\item There are very few profiles that are in equilibria, overall.  Profiles
with relatively high degrees of correlation between the preferences (Urn and AGH 2004) have fewer equilibrium profiles than the less correlated
models (IC and SP-IC).
\item These trends appear stable with small numbers of agents and houses.
We observed similar results for all combinations.% 2 to 4 agents splitting between 2 and 5 houses.
\end{inparaenum}




\section{Conclusions}

We conducted a detailed analysis of strategic aspects of the PS rule including the complexity of computing and verifying PNE.
The fact that PNE are computationally hard to compute in general may act as a disincentive or barrier to strategic behavior.
Our experimental results show PS is relatively robust, in terms of social welfare, even in the presence of strategic behaviour. 
Our study leads to a number of new research directions. 
It will be interesting to extend our algorithmic results to the extension of PS for indifferences~\cite{KaSe06a}.
 % Two problems are still open. Firstly, what is the complexity of computing an expected utility best response for more than two agents? The problem is particularly intriguing because even for the related and conceptually simpler setting of discrete allocation, computing an expected utility  best response for more than two agents remains an open problem~\cite{BoLa11a}.
 % Another problem is the complexity of computing a Nash equilibrium for more than two agents. 	%We have studied the problem of computing a best response of a single agent. 
% It will also be interesting to examine coalitional manipulations and coalitional Nash equilibria.
% 	Finally, a deeper analysis of Nash dynamics under the PS rule is an intriguing research problem.
Additionally, studying \emph{strong} Nash equilibria and a deeper analysis of Nash dynamics are other interesting directions.
	
	


%Is there ever incentive to misreport by reporting ties when none are present?
 %Initial analysis shows that EU and DL best responses can cycle.


%\section{Acknowledgements}

% A related issue is that of existence and computation of \emph{coalitional} Nash equilibrium.  Our argument for the existence of a Nash equilibrium does not naturally extend to that for coalitional Nash equilibrium. It will be interesting to check whether a preference profile exists that is in coalitional Nash equilibrium.



%
% We have also not considered the strong-SD-Nash equilibrium. What is the complexity of checking whether a strong
%


%The most straightforward definition of coalitional Nash equilibrium is a preference profile such that there exists no subset of agents than can misreport their preferences so as to get a better assignment.

% The PS rule is naturally associated with DL relation since it is DL-efficient and DL envy-free. A dual relationship upward lexicographic (UL), in which an agent wants to minimise the probability of his least preferred houses. It will be interesting to extend our analysis to that of UL.


 % To begin the analysis, it may be easier to first focus on the original PS mechanism for strict preferences.


%\begin{table}[h]
	%\centering
		%\scalebox{1}{
%\centering
%%\scriptsize
%\begin{tabular}{llll}
%\toprule
%&	\small \textsc{BestEUresponse} &\small\textsc{BestDLresponse}	&\small	\textsc{BestSDresponse}\\%\textsc{BetterSDresponseThanTruth}\\
%\midrule
%constant $m$&$O(n)$&$O(n)$&$O(n)$\\%&$O(n)$\\
%$n=2$&$O(m^2)$&$O(m^2)$&$O(m)$\\%&$O(m^2)$\\
%%constant $n$&?&$O(m^2n)$&?\\
%%$m\leq n$&?&$O(mn)$&$O(n)$\\%&?\\
%$n>2$&?&$O(m^2n)$&$O(m^2n)$\\  %&?\\
%\bottomrule
%\end{tabular}
%}
%
%
%
%% \begin{tablenotes}
%% 	\item[a] only for strict preferences.
%% 	%\item[b]
%% \end{tablenotes}
%
%\caption{Computational complexity of manipulating the PS rule}
%\label{table:summary:rsd}
%\end{table}



% \begin{table}[h]
% 	\centering
% 		\scalebox{1}{
% \centering
% %\scriptsize
% \begin{tabular}{llll}
% \toprule
% &	\small \textsc{EUNash} &\small\textsc{DLNash}	&\small	\textsc{SDNash}\\
% \midrule
% %constant $m$&?&?&?\\
% $n=2$&$O(mn)$&$O(mn)$&$O(mn)$\\
% %constant $n$&?&?&?\\
% $m\leq n$&?&$O(mn)$&$O(mn)$\\
% &NP-hard&?&?\\
% \bottomrule
% \end{tabular}
% }
%
% % \begin{tablenotes}
% % 	\item[$\ast$] An equilibrium is guaranteed to exist.
% % 	%\item[b]
% % \end{tablenotes}
%
% \caption{Computational complexity of computing pure Nash equilibrium under PS.}
% \label{table:summary:rsd}
% \end{table}





% \section{Expected utility best response for the alternation policy}\label{s:alt_bestresp}



	%\begin{algorithm}[h!]
		  %\caption{Best EU response for $2$ agents for sequential allocation (Algorithm of \citet{KoCh71a})}
		  %\label{algo:2agent-EU-Nash}
	%%	\small
		%\renewcommand{\algorithmicrequire}{\wordbox[l]{\textbf{Input}:}{\textbf{Output}:}}
		 %\renewcommand{\algorithmicensure}{\wordbox[l]{\textbf{Output}:}{\textbf{Output}:}}
		%\begin{algorithmic}
			%\REQUIRE $(\{1,2\},H,(\succ_1,\succ_2))$ where $\succ 2: h_1,\succ_2 \ldots,\succ_2 h_m$
			%\ENSURE
		%\end{algorithmic}
		%\algsetup{linenodelimiter=\,}
		  %\begin{algorithmic}[1]
	%\STATE let $I^k = \{h_{2k-1},h_{2k}\}$, $k=1,\ldots,m/2$
	%\STATE $J^1 = \max_{\succ_1}(\{h_{1},h_2\}$ and $J^k = \{h_{2k-1},h_{2k}\}$, $k=2,\ldots,m/2$.
	%\STATE $\overline{J}^1= J^1$ and $\overline{J}^k = \{h_{j}| h_{j} \in \overline{J}^{k-1} \cup J^k; V_{1j} \geq k \mathrm{th\ maximal\ of\ } \{V_{1l}| h_{l}  \in \overline{J}^{k-1} \cup J^k\}\}.$
	%\STATE $\overline{J}^{m/2}$ is the optimal set that agent $1$ reports and gets.
		 %\end{algorithmic}
		%\label{algo:subroutine}
		%\end{algorithm}
%
%
%
	%\begin{algorithm}[h!]
		  %\caption{Best EU response for $2$ agents and PS rule}
		  %\label{algo:2agent-EU-Nash}
	%%	\small
		%\renewcommand{\algorithmicrequire}{\wordbox[l]{\textbf{Input}:}{\textbf{Output}:}}
		 %\renewcommand{\algorithmicensure}{\wordbox[l]{\textbf{Output}:}{\textbf{Output}:}}
		%\begin{algorithmic}
			%\REQUIRE $(\{1,2\},H,(\succ_1,\succ_2))$ where $\succ 2: h_1,\succ_2 \ldots,\succ_2 h_m$
			%\ENSURE
		%\end{algorithmic}
		%\algsetup{linenodelimiter=\,}
		  %\begin{algorithmic}[1]
	%\STATE Construct order-preserving bisection of $\succ$.
	%\STATE Run the Best EU response for $2$ agents for sequential allocation (Algorithm of \citet{KoCh71a})
	%\STATE If the best response for sequenial allocation has the consecutivity property, return the reverse order-preserving bisection.
	%\STATE Otherwise, we know that the full houses that agent $1$ gets and the half-houses that agent $1$ does not get satisfy consecutive property. For
	%each half-house of which type agent $1$ gets only once in the same round as when the same type house is allocated to agent $2$.
	%\STATE Return the reverse order-preserving bisection.
				 %\end{algorithmic}
			%\label{algo:subroutine}
		%\end{algorithm}

\section{Acknowledgments}
NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program. Serge Gaspers is also supported by the Australian Research Council grant DE120101761.


% \renewcommand*{\bibfont}{\small}
% \newpage
\bibliographystyle{named}
 % \bibliography{../../../research/papers/pamas/abbshort,../../../research/papers/pamas/pamas.bib,../../../research/papers/pamas/aziz.bib}
% % %
%  % \bibliography{../../adtbib/abb,../../adtbib/adt}
%


\begin{thebibliography}{}

\bibitem[\protect\citeauthoryear{Ackermann \bgroup \em et al.\egroup
  }{2011}]{AGM+11a}
H.~Ackermann, P.~W. Goldberg, V.~S. Mirrokni, H.~R{\"o}glin, and
  B.~V{\"o}cking.
\newblock Uncoordinated two-sided matching markets.
\newblock {\em SIAM Journal on Computing}, 40(1):92--106, 2011.

\bibitem[\protect\citeauthoryear{Aziz and Stursberg}{2014}]{AzSt14a}
H.~Aziz and P.~Stursberg.
\newblock A generalization of probabilistic serial to randomized social choice.
\newblock In {\em Proc.~of 28th AAAI Conference}, pages 559--565. AAAI Press,
  2014.

\bibitem[\protect\citeauthoryear{Aziz \bgroup \em et al.\egroup
  }{2013}]{ABB13b}
H.~Aziz, F.~Brandt, and M.~Brill.
\newblock The computational complexity of random serial dictatorship.
\newblock {\em Economics Letters}, 121(3):341--345, 2013.

\bibitem[\protect\citeauthoryear{Aziz \bgroup \em et al.\egroup
  }{2014}]{AGMW14a}
H.~Aziz, S.~Gaspers, S.~Mackenzie, and T.~Walsh.
\newblock Fair assignment of indivisible objects under ordinal preferences.
\newblock In {\em Proc.~of 13th AAMAS Conference}, pages 1305--1312, 2014.

\bibitem[\protect\citeauthoryear{Aziz \bgroup \em et al.\egroup
  }{2015a}]{AGM+15c}
H.~Aziz, S.~Gaspers, S.~Mackenzie, N.~Mattei, N.~Narodytska, and T.~Walsh.
\newblock Manipulating the probabilistic serial rule.
\newblock In {\em Proc.~of 14th AAMAS Conference}, 2015.

\bibitem[\protect\citeauthoryear{Aziz \bgroup \em et al.\egroup
  }{2015b}]{AGM+15b}
H.~Aziz, S.~Gaspers, S.~Mackenzie, N.~Mattei, N.~Narodytska, and T.~Walsh.
\newblock Manipulating the probabilistic serial rule.
\newblock Technical report, arXiv.org, 2015.

\bibitem[\protect\citeauthoryear{Berg}{1985}]{Berg85a}
S.~Berg.
\newblock Paradox of voting under an urn model: The effect of homogeneity.
\newblock {\em Public Choice}, 47:377--387, 1985.

\bibitem[\protect\citeauthoryear{Bogomolnaia and Heo}{2012}]{BoHe12a}
A.~Bogomolnaia and E.~J. Heo.
\newblock Probabilistic assignment of objects: Characterizing the serial rule.
\newblock {\em Journal of Economic Theory}, 147:2072--2082, 2012.

\bibitem[\protect\citeauthoryear{Bogomolnaia and Moulin}{2001}]{BoMo01a}
A.~Bogomolnaia and H.~Moulin.
\newblock A new solution to the random assignment problem.
\newblock {\em Journal of Economic Theory}, 100(2):295--328, 2001.

\bibitem[\protect\citeauthoryear{Budish \bgroup \em et al.\egroup
  }{2013}]{BCKM12a}
E.~Budish, Y.-K. Che, F.~Kojima, and P.~Milgrom.
\newblock Designing random allocation mechanisms: {T}heory and applications.
\newblock {\em American Economic Review}, 103(2):585--623, 2013.

\bibitem[\protect\citeauthoryear{Cho}{2012}]{Cho12a}
W.~J. Cho.
\newblock Probabilistic assignment: A two-fold axiomatic approach.
\newblock {M}imeo, 2012.

\bibitem[\protect\citeauthoryear{Ekici and Kesten}{2012}]{EkKe12a}
O.~Ekici and O.~Kesten.
\newblock An equilibrium analysis of the probabilistic serial mechanism.
\newblock Technical report, {\"O}zye{\u g}in University, Istanbul, May 2012.

\bibitem[\protect\citeauthoryear{G{\"a}rdenfors}{1973}]{Gard73b}
P.~G{\"a}rdenfors.
\newblock Assignment problem based on ordinal preferences.
\newblock {\em Management Science}, 20:331--340, 1973.

\bibitem[\protect\citeauthoryear{Heo and Manjunath}{2012}]{HeMa12a}
E.~J. Heo and V.~Manjunath.
\newblock Probabilistic assignment: Implementation in stochastic dominance nash
  equilibria.
\newblock Technical Report 1809204, SSRN, 2012.

\bibitem[\protect\citeauthoryear{Hylland and Zeckhauser}{1979}]{HyZe79a}
A.~Hylland and R.~Zeckhauser.
\newblock The efficient allocation of individuals to positions.
\newblock {\em The Journal of Political Economy}, 87(2):293--314, 1979.

\bibitem[\protect\citeauthoryear{Katta and Sethuraman}{2006}]{KaSe06a}
A-K. Katta and J.~Sethuraman.
\newblock A solution to the random assignment problem on the full preference
  domain.
\newblock {\em Journal of Economic Theory}, 131(1):231--250, 2006.

\bibitem[\protect\citeauthoryear{Kojima}{2009}]{Koji09a}
F.~Kojima.
\newblock Random assignment of multiple indivisible objects.
\newblock {\em Mathematical Social Sciences}, 57(1):134---142, 2009.

\bibitem[\protect\citeauthoryear{Lu and Boutilier}{2011}]{LuBo11a}
T.~Lu and C.~Boutilier.
\newblock Learning {M}allows models with pairwise preferences.
\newblock In {\em Proc.~of 28th ICML}, pages 145--152, 2011.

\bibitem[\protect\citeauthoryear{Mallows}{1957}]{Mall57a}
C.~L. Mallows.
\newblock Non-null ranking models.
\newblock {\em Biometrika}, 44(1/2):114--130, 1957.

\bibitem[\protect\citeauthoryear{Mattei and Walsh}{2013}]{MaWa13a}
N.~Mattei and T.~Walsh.
\newblock Pref{L}ib: A library for preference data.
\newblock In {\em Proc.~of 3rd ADT}, volume 8176 of {\em Lecture Notes in
  Artificial Intelligence (LNAI)}, pages 259--270. Springer, 2013.

\bibitem[\protect\citeauthoryear{Mattei}{2011}]{Matt11a}
N.~Mattei.
\newblock Empirical evaluation of voting rules with strictly ordered preference
  data.
\newblock In {\em Proc.~of 2nd ADT}, pages 165--177. 2011.

\bibitem[\protect\citeauthoryear{Monderer and Shapley}{1996}]{MoSh96a}
D.~Monderer and L.~S. Shapley.
\newblock Potential games.
\newblock {\em Games and Economic Behavior}, 14(1):124--143, 1996.

\bibitem[\protect\citeauthoryear{Saban and Sethuraman}{2014}]{SaSe13b}
D.~Saban and J.~Sethuraman.
\newblock A note on object allocation under lexicographic preferences.
\newblock {\em Journal of Mathematical Economics}, 50:283--289, 2014.

\bibitem[\protect\citeauthoryear{Schulman and Vazirani}{2012}]{ScVa12a}
L.~J. Schulman and V.~V. Vazirani.
\newblock Allocation of divisible goods under lexicographic preferences.
\newblock Technical Report arXiv:1206.4366, arXiv.org, 2012.

\bibitem[\protect\citeauthoryear{Yilmaz}{2010}]{Yilm10a}
O.~Yilmaz.
\newblock The probabilistic serial mechanism with private endowments.
\newblock {\em Games and Economic Behavior}, 69(2):475--491, 2010.

\end{thebibliography}



\end{document}
1502.04888.extracted_bib
[\protect\citeauthoryear{Ackermann \bgroup \em et al.\egroup {2011]{AGM+11a H.~Ackermann, P.~W. Goldberg, V.~S. Mirrokni, H.~R{\"oglin, and B.~V{\"ocking. \newblock Uncoordinated two-sided matching markets. \newblock {\em SIAM Journal on Computing, 40(1):92--106, 2011.
1502.04888.extracted_bib
[\protect\citeauthoryear{Aziz and Stursberg{2014]{AzSt14a H.~Aziz and P.~Stursberg. \newblock A generalization of probabilistic serial to randomized social choice. \newblock In {\em Proc.~of 28th AAAI Conference, pages 559--565. AAAI Press, 2014.
1502.04888.extracted_bib
[\protect\citeauthoryear{Aziz \bgroup \em et al.\egroup {2013]{ABB13b H.~Aziz, F.~Brandt, and M.~Brill. \newblock The computational complexity of random serial dictatorship. \newblock {\em Economics Letters, 121(3):341--345, 2013.
1502.04888.extracted_bib
[\protect\citeauthoryear{Aziz \bgroup \em et al.\egroup {2014]{AGMW14a H.~Aziz, S.~Gaspers, S.~Mackenzie, and T.~Walsh. \newblock Fair assignment of indivisible objects under ordinal preferences. \newblock In {\em Proc.~of 13th AAMAS Conference, pages 1305--1312, 2014.
1502.04888.extracted_bib
[\protect\citeauthoryear{Aziz \bgroup \em et al.\egroup {2015a]{AGM+15c H.~Aziz, S.~Gaspers, S.~Mackenzie, N.~Mattei, N.~Narodytska, and T.~Walsh. \newblock Manipulating the probabilistic serial rule. \newblock In {\em Proc.~of 14th AAMAS Conference, 2015.
1502.04888.extracted_bib
[\protect\citeauthoryear{Aziz \bgroup \em et al.\egroup {2015b]{AGM+15b H.~Aziz, S.~Gaspers, S.~Mackenzie, N.~Mattei, N.~Narodytska, and T.~Walsh. \newblock Manipulating the probabilistic serial rule. \newblock Technical report, arXiv.org, 2015.
1502.04888.extracted_bib
[\protect\citeauthoryear{Berg{1985]{Berg85a S.~Berg. \newblock Paradox of voting under an urn model: The effect of homogeneity. \newblock {\em Public Choice, 47:377--387, 1985.
1502.04888.extracted_bib
[\protect\citeauthoryear{Bogomolnaia and Heo{2012]{BoHe12a A.~Bogomolnaia and E.~J. Heo. \newblock Probabilistic assignment of objects: Characterizing the serial rule. \newblock {\em Journal of Economic Theory, 147:2072--2082, 2012.
1502.04888.extracted_bib
[\protect\citeauthoryear{Bogomolnaia and Moulin{2001]{BoMo01a A.~Bogomolnaia and H.~Moulin. \newblock A new solution to the random assignment problem. \newblock {\em Journal of Economic Theory, 100(2):295--328, 2001.
1502.04888.extracted_bib
[\protect\citeauthoryear{Budish \bgroup \em et al.\egroup {2013]{BCKM12a E.~Budish, Y.-K. Che, F.~Kojima, and P.~Milgrom. \newblock Designing random allocation mechanisms: {Theory and applications. \newblock {\em American Economic Review, 103(2):585--623, 2013.
1502.04888.extracted_bib
[\protect\citeauthoryear{Cho{2012]{Cho12a W.~J. Cho. \newblock Probabilistic assignment: A two-fold axiomatic approach. \newblock {Mimeo, 2012.
1502.04888.extracted_bib
[\protect\citeauthoryear{Ekici and Kesten{2012]{EkKe12a O.~Ekici and O.~Kesten. \newblock An equilibrium analysis of the probabilistic serial mechanism. \newblock Technical report, {\"Ozye{\u gin University, Istanbul, May 2012.
1502.04888.extracted_bib
[\protect\citeauthoryear{G{\"ardenfors{1973]{Gard73b P.~G{\"ardenfors. \newblock Assignment problem based on ordinal preferences. \newblock {\em Management Science, 20:331--340, 1973.
1502.04888.extracted_bib
[\protect\citeauthoryear{Heo and Manjunath{2012]{HeMa12a E.~J. Heo and V.~Manjunath. \newblock Probabilistic assignment: Implementation in stochastic dominance nash equilibria. \newblock Technical Report 1809204, SSRN, 2012.
1502.04888.extracted_bib
[\protect\citeauthoryear{Hylland and Zeckhauser{1979]{HyZe79a A.~Hylland and R.~Zeckhauser. \newblock The efficient allocation of individuals to positions. \newblock {\em The Journal of Political Economy, 87(2):293--314, 1979.
1502.04888.extracted_bib
[\protect\citeauthoryear{Katta and Sethuraman{2006]{KaSe06a A-K. Katta and J.~Sethuraman. \newblock A solution to the random assignment problem on the full preference domain. \newblock {\em Journal of Economic Theory, 131(1):231--250, 2006.
1502.04888.extracted_bib
[\protect\citeauthoryear{Kojima{2009]{Koji09a F.~Kojima. \newblock Random assignment of multiple indivisible objects. \newblock {\em Mathematical Social Sciences, 57(1):134---142, 2009.
1502.04888.extracted_bib
[\protect\citeauthoryear{Lu and Boutilier{2011]{LuBo11a T.~Lu and C.~Boutilier. \newblock Learning {Mallows models with pairwise preferences. \newblock In {\em Proc.~of 28th ICML, pages 145--152, 2011.
1502.04888.extracted_bib
[\protect\citeauthoryear{Mallows{1957]{Mall57a C.~L. Mallows. \newblock Non-null ranking models. \newblock {\em Biometrika, 44(1/2):114--130, 1957.
1502.04888.extracted_bib
[\protect\citeauthoryear{Mattei and Walsh{2013]{MaWa13a N.~Mattei and T.~Walsh. \newblock Pref{Lib: A library for preference data. \newblock In {\em Proc.~of 3rd ADT, volume 8176 of {\em Lecture Notes in Artificial Intelligence (LNAI), pages 259--270. Springer, 2013.
1502.04888.extracted_bib
[\protect\citeauthoryear{Mattei{2011]{Matt11a N.~Mattei. \newblock Empirical evaluation of voting rules with strictly ordered preference data. \newblock In {\em Proc.~of 2nd ADT, pages 165--177. 2011.
1502.04888.extracted_bib
[\protect\citeauthoryear{Monderer and Shapley{1996]{MoSh96a D.~Monderer and L.~S. Shapley. \newblock Potential games. \newblock {\em Games and Economic Behavior, 14(1):124--143, 1996.
1502.04888.extracted_bib
[\protect\citeauthoryear{Saban and Sethuraman{2014]{SaSe13b D.~Saban and J.~Sethuraman. \newblock A note on object allocation under lexicographic preferences. \newblock {\em Journal of Mathematical Economics, 50:283--289, 2014.
1502.04888.extracted_bib
[\protect\citeauthoryear{Schulman and Vazirani{2012]{ScVa12a L.~J. Schulman and V.~V. Vazirani. \newblock Allocation of divisible goods under lexicographic preferences. \newblock Technical Report arXiv:1206.4366, arXiv.org, 2012.
1502.04888.extracted_bib
[\protect\citeauthoryear{Yilmaz{2010]{Yilm10a O.~Yilmaz. \newblock The probabilistic serial mechanism with private endowments. \newblock {\em Games and Economic Behavior, 69(2):475--491, 2010.