deletions | additions       diff --git a/Some_algorithms_for_.tex b/Some_algorithms_for_.tex  index 5ff5c4a..cbf7dc7 100644  --- a/Some_algorithms_for_.tex  +++ b/Some_algorithms_for_.tex 
...
Assume we have a centralized algorithm (e.g., $A^*$) that asks agents for their costs and then computes an allocation of paths that minimizes the total cost for the agents. If the agents report their paths truthfully, the algorithm will find the optimal allocation, according to which $a_1$ will go to its goal through $X$ (cost of 2.5) and $a_2$ will go through $Y$ (cost 2). This will result in a total cost of 4.5. Note, however, that $a_1$ would have preferred the path that goes through $Y$ as it only costs 2. If $a_1$ is self-interested, it might try to manipulate the outcome by reporting its costs untruthfully. Specifically, it could report that the cost of the edge from $s_1$ to $X$ costs 4 instead of 1.5. Then, the centralized algorithm will allocate $a_1$ the path that goes through $X$ and will allocate $a_2$ the path that goes through $Z$, thinking that these paths, with a total cost of 4.7 are the optimal allocation. Thus, this mechanism is not strategyproof.   In contrast with the MAPF literature, the auction literature have typically considered self-interested settings and thus developed mechanisms that are robust to various types of manipulation***cite stuff***. manipulations.  Mapping MAPF problems to CA thus suggests an approach for solving self-interested MAPF problems. Specifically, the auction mechanism elicits agents' preferences over paths through their bids and determines an allocation of paths. The mechanism then provides each agent with a permit to the path that was sold to it. We further assume an enforcement mechanism (e.g., fines) that prevents agents from traversing paths that were not allocated to them. An example for an auction mechanism that is robust to the type of manipulation exhibited above is the \emph{Vickrey–Clarke–Groves} (VCG) auction~\cite{clarke1971multipart,vickrey1961counterspeculation,groves1973incentives}. In this mechanism, agents submit bids on multiple items based on their valuation for the items. However, they are then asked to pay based on the ``harm'' they caused to other bidders. ***add formal***