deletions | additions       diff --git a/Theorem_maximum_soci.tex b/Theorem_maximum_soci.tex  index 741c4dc..84d9809 100644  --- a/Theorem_maximum_soci.tex  +++ b/Theorem_maximum_soci.tex 
...
In CA optimizing the summed utility over all agents is known as maximum social welfare. Many CA solvers guarantee maximum social welfare as long as agents use the myopic best response bidding strategy (Parkes 1999). According to this strategy, agents always bid on the best bundle (according to their evaluation) given the current prices.  A myopic best response MAPF agent will aspire to minimize its own path cost.   The utility of a given path $p$, for a given agent is $-c$ where $c=cost(p)$.  Let $p'$ be the path with the highest cost in the optimal solution.  Let $max_c$ be the cost of $p'$.  Since the maximal price an agent is willing to pay on a bundle (path) cannot be negative, we suggest setting $price(p)=max_{p' \in P}[cost(p')]-cost(p)$ where $P$ is the set of all paths in the optimal solution and $p' \in P$ is the path with the maximal cost. $price(p)=max_c-cost(p)$.  Though finding $max_{p' \in P}[cost(p')]$ $max_c$  is a hard problem, we can bound this value by using the $|V|^3$ upper bound defined above./footnote{The $|V|^3$ bound is defined for the number of time steps and not cost. A cost bound can be calculated by multiplying the time steps bound by the maximal cost of a single time step.} Setting the above price function and a myopic best response strategy for all agents is not sufficient to guarantee an optimal MAPF solution using a CA solver. Figure xxx presents a MAPF problem where each edge costs 1 (left) and a corrisponding corresponding  CA formalization (right). Recall that each item in the CA formalization represent a \{vertex, time step\} coorinant. coordinate.  In the optimal MAPF solution, at the first time step, agent 1 waits at location $A$, and agent 2 moves from $C$ to $B$. At time step 2 both agents move to thier their  goal locations ($B$ and $D$ respectivly). respectively).  consequently, the path costs cost  for both agent 1 and 2 are is  2. When reducing this instance to CA there are three relvent relevant  bundles. The maximal price of each bundle (path) is the maximal single agent path, 2 in this example, $max_c=2$  minus the cost of the bundle (path) in question. For this problem, the maximal revenue of the auctuniar (1) auctioneer (equal to 1)  is obtained when it assigns agent 1 with bundle $b_1$ and no bundle is assigned to agent 2. Consequently CA solver that maintain maximal social welfare will not return the optimal MAPF solution.  Theorem: maximum social welfare = We solve this inconsistency by changing the max-price function as follows, $price(p)=max_c \times |K| - cost(p)$. In this case the minimal price an agent is willing to pay for a path is grater or equal to $max_c \times (|K|-1)$. By not assigning a path to an agent the maximal benefit for all other agents is $max_c$ per agent and $max_c \times (|K|-1)$ in total. The maximal benefit from not assigning an agent is zero, if the auctioneer brake ties in favor of assigning bundles, CA will always return the  optimal MAPF. MAPF solution if one exist.