deletions | additions       diff --git a/Some_algorithms_for_.tex b/Some_algorithms_for_.tex  index 483f7c0..986959a 100644  --- a/Some_algorithms_for_.tex  +++ b/Some_algorithms_for_.tex 
...
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***. 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. 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*** For example, assume that both $a_1$ and $a_2$ get a value of 10 for acheiving their goal and incur a cost for traversing a path based on the edges' costs. Then, the value for $a_1$ from getting the path $s_{1} \rightarrow $X$ \rightarrow g_1$ is $10-2.5=7.5$, while its value for the path $s_{1} \rightarrow $Y$ \rightarrow g_1$ is $10-2=8$. Similarly the values for $a_2$ are 8 for the path through $X$ and 7.3 for the path through $Z$. If the agents bid truthfully, the auctioneer will allocate $a_1$ the path $s_{1} \rightarrow $Y$ \rightarrow g_1$ and will allocate $a_2$ the path $s_{2} \rightarrow $X$ \rightarrow g_2$, as this allocation maximizes the total value for the agents ($8+7.5=15.5$). The payment for the agents is calculated according to the harm they caused to the other agents. In this case, $a_1$ will pay $0$, as it did not cause any harm to $a_2$ ($a_2$ got its highest valued path); $a_2$ will pay $0.5$ as it prevented $a_1$ from getting a path that was valued higher by 0.5 from its allocated path (valuation of 7.5 compared to a valuation of 8). The utilities for the agents $a_1$ and $a_2$ are thus $u_1=10-0=10$ and $u_2=10-0.5=9.5$ correspondingly.