deletions | additions       diff --git a/subsectionWinner_Det.tex b/subsectionWinner_Det.tex  index c2b8dca..b9ea2dc 100644  --- a/subsectionWinner_Det.tex  +++ b/subsectionWinner_Det.tex 
...
\subsection{Winner Determination}  Tricks. At the end of each round of the auction, a \emph{provisional allocation} is determined. The provisional allocation is chosen such that it maximizes revenue and allocates non-conflicting bundles for the set of agents included in the allocation. Ties are broken in favor of allocations that include more agents. At a high-level, the winner determination (WD) problem consists of the following components: (1) generating candidate allocations based on agents' bids; (2) checking whether the allocation is feasible, and (3) computing the revenue of each allocation and choosing the candidate allocation that gives the highest revenue.   For example, in the first round of the auction for the problem shown in Figure~\ref{fig:mapf}(a), each agent bids on its shortest paths MDD (Figure~\ref{fig:mapf}(b-d)). The possible candidate allocations include all combinations of allocations:   \begin{itemize}  \item Allocating a bundle to one of the agents only. E.g., allocating $a_1$ its requested bundle and not allocating any bundle to $a_2$ and $a_3$.   \item Allocating bundles to a pair of agents. E.g., allocating to $a_1$ its requested bundle and allocating to $a_2$ one of the bundles represented by its MDD  \end{itemize}  the provisional allocation at the end of the first round will include either $a_1$ and $a_2$ or $a_1$ and $a_3$. This is because there is no combination of the three agents' shortest paths that does not conflict, nor a combination of the paths for $a_2$ and $a_3$ (all paths of $a_2$ and $a_3$ include node $E$ at $t_4$). However, non-conflicting paths can be allocated to $a_1$ and $a_2$ . Therefore, one of these pairs will be chosen (recall ties are broken in favor of more agents, so there is no reason to include only one agent in the provisional allocation). This means that at the end of this iteration two agents will be included in the provisional allocation while the third agent will remain ``unhappy''.  The winner determination problem is computationally hard~\cite{sandholm2002algorithm}. The pathfinding domain poses additional computational challenges for the winner determination process. First, the set of items is very large due to the time dimension. Second, agents have relative valuations for MDDs. Thus, if agents have unlimited budgets, they will keep bidding on all paths they bid on in previous iterations, resulting in a large number of bids and an increasing number of candidate allocations to be considered. Finally, checking whether an allocation is feasible requires solving a sub-problem of the complete pathfinding problem, namely searching for non-conflicting paths for the agents given their MDDs.  We used a Branch and Bound search to generate candidate allocations, pruning allocations that have lower revenue than the best allocation found so far. This approach is similar to that proposed by Sandholm~\cite{sandholm2002algorithm} with some modifications to allow it to work with MDDs rather than searching the space of individual bundles. Using MDDs, we reduce this computational complexity of the feasibility verification, eliminating the need to consider every possible path separately. To check whether a candidate allocation is feasible, we use and algorithm for solving a set of MDDs introduced by Sharon et al.~\cite{sharon2012increasing}. Computing the revenue of an allocation is straightforward (summing the prices of the MDDs in the allocation).