this is for holding javascript data
guni edited Theorem_maximum_soci.tex
over 9 years ago
Commit id: c0c4c038442136142efa6b6b4a7516624c8b6cb0
deletions | additions
diff --git a/Theorem_maximum_soci.tex b/Theorem_maximum_soci.tex
index 314fee8..1661901 100644
--- a/Theorem_maximum_soci.tex
+++ b/Theorem_maximum_soci.tex
...
\subsection{Optimal MAPF}
A line of previous work was devoted to the optimal variant of MAPF. In the optimal variant a solution which minimizes the summation of single agent paths is required.
In CA optimizing the summed utility over all agents is known as maximum social welfare. Many CA solvers
guarntee guarantee maximum social welfare as long as agents use the myopic best response bidding strategy (Parkes 1999). According to this strategy, agents
allways always bid on the best bundle (according to
thier their evaluation) given the current prices.
A myopic best response MAPF agent will aspire to minimize its own path cost.
The utility of
agiven a given path $p$, for a given agent is $-c$ where $c=cost(p)$.
Since the maximal price an agent is willing to pay on a bundle (path)
can not cannot be negative, we suggest setting $price(p)=max_{p' \in P}[cost(p')]-cost(p)$ where $P$ is the set of all
possibale possible paths in the optimal solution and $p' \in P$ is the path with the maximal cost.
Though finding $max_{p' \in P}[cost(p')]$ is a
hared 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
multipling multiplying the time steps bound by the maximal cost of a single time step.}
-setting Setting the
cost above price function and a myopic best response strategy for
each bundle all agents is not sufficient to guarantee an optimal MAPF solution using a CA solver. Figure xxx presents a MAPF problem
Theorem: maximum social welfare = optimal MAPF.