Many interesting issues raised by this question --- which essentially asks about creating a social optimum from individual behavior. Assume the individuals operate without regard to overall social constraints. I could imagine that each could find a (local i.e. for themselves) optimum. How do we "add" these together to get the social outcome? When we do, we may have aggregate constraints on the solution that were not apparent at the individual scale. Also, I think there are some deep interesting theory from Arrow which talks about the impossibility of aggregate social welfare optimization from the sum of individual parts, but that may or may not be relevant here. If you could tell me how to add up the individuals, I could optimize that aggregate objective. I think we would all be surprised if the aggregate optimum corresponded to the individually optimal outcome.

Interesting question!

As far as I have understood your problem correctly, it can be only in case of objective function f(D) = f1(D1) + f2(D2) + ... + fn(Dn), where D = D1 U D2 U ... Dn, Di and Dj are disjoint subsets, fi and fj are mutually independent functions, 1

I would agree with Gennady above: only if those local optima searching agents are independent then we could sum them up together to get the global optimal, but if this is the case, then I believe it will be a trivial problem to solve!

Dear Stephen,

Thank you for this interesting question.

It seems to me that any useful strategy would need to try to take full advantage of the characteristics of the problem at hand. For instance, in the case of the vehicle problem, the precise strategy will highly depend on whether or not each vehicle is assigned its own start/goal position and whether ot not all vehicles begin their motion at the same time. Incidentally, a related but different problem is the one in which the objective is not to minimize the sum of the travel times but rather the time required for the last agent to finish the job.

As a side note, I would like to add the following remarks 

1) the word "local" and "global" that appear in the question title could be a bit confusing because they do not refer to the same function landscape. Since the objective here is to minimize a sum, then terms such as local/global optimum are understood to be referring solely to this stated objective and not to the score obtained by a given agent. Of course, the score of a given agent could (but not necessarily) coincide with a local/global optimum in the function landscape of this particular agent but, in that case, it should be referred to as an individual local/global optimum which would have nothing to do with the landscape of the function sum.

2) The way the original question is stated seems to imply that whenever the algorithm converges to a local/global optimum of the sum, then all individual scores will also coincide with individual local/global optimum in their respective landscape. In general, this is simply not true. In fact, the global optimum for the sum may very well be obtained when individual scores are neither local nor global optima, particularly so if the problem includes severe interaction constraints between agents  (This last remarks has already been mentioned above by @Morton)

Hope this helps.

Just one more thought re-reading the context of your question. You may be aware (?) of the "user equilibrium" vs "system optimal" distinction in traffic assignment. These are two different approaches with different objective functions that arise in the field of traffic assignment. They recognize that user equilibrium involves finding a route pattern (for everyone) that cannot be swapped for a lower cost for the individual. This is done even as we recognize that individuals contribute to congestion and potentially slow things down for others. The system optimal approach has a more global objective. I think your questions points us in a critical direction -- i.e. the relevance of these ideas for a (partially) autonomous fleet.

Indeed, if the system optimum objective function is a convex one, you may set a "toll" equivalent to the derivative of the system cost (evaluated at a system optimum solution), and derive a system optimum as a user equilibrium (with the link tolls added to the original user costs). Piece of cake, you may say, but rarely is the system cost a convex one.

In the way you set your problem up, there is no way for agents to "give up" their individual optimal policy/strategy for the "better good", because there is no incentive for them.

On the other hand, in other contexts, there are beautiful solutions to the problem of "channel coordination" where the global optimum cannot be obtained when the involved agents pursue their individual optimum solutions, but it is possible for one agent to provide incentive to the other ones (essentially change the problem) so that the overall solution is improved. There are such solutions have found their way in the real-world. Consider contract negotiations in a supplier/retailer setting, where the supplier profits as the retailer purchases more items from the supplier, but the retailer's optimal purchase quantity (the one that maximizes their expected profits under a given demand distribution) is far from the quantity that maximizes the sum of profits of the channel (supplier + retailer). The easy solution is for the supplier to "share" part of the retailer's risk, by proposing one of many possible options:

1. buy-back contracts (supplier agrees to buy back at a certain price any unsold items of the retailer)

2. revenue sharing (supplier sells items to the retailer at much less cost and then shares the profits of the items the retailer sells)

3. and many other possibilities

Now, the retailer has incentive to buy more items from the supplier, and the overall expected profit for each player (and obviously for the channel as a whole) is improved!.

The morale of the above example is that one or a group of the agents (the ones that would benefit the most by the change of behavior of (some) other agents) need to "forfeit" some advantage they have, so as to convince the other agents to also change their behavior. Only then (in a proposed win-win situation), it may be possible under the right circumstances for all involved independent parties to change their behavior in a way that leads to better individual solutions, that also has the benefit of an overall better solution.

Under independent agents assumption, unless there is a win-win situation for all, it is impossible to convince the "loosing" agents to act "selflessly" for the better good (unless of course you can model the problem differently, and maybe have the individual agents care for the "better good").

Hi Everyone,

Thanks for a great discussion.

H.E. - I agree that I meant "individual" optima.  However, it's much easier to talk about local optima and a global optimum as opposed to individual optima (which does not immediately imply that they are not globally optimal).

Morton, Michael, and Ioannis - I have been thinking about price incentives for each agent.  If we know the global optimum, we could of course create individual objective functions for each agent such that their individual/local optima match their roles in this global optimum.  Then, the alternate optimization problem might be how we minimize the total incentives offered.

Any suggestions?

Thanks, 

Stephen

Dear Stephen,

You wrote a phrase "If we know the global optimum, we could of course create individual objective functions for each agent such that their individual/local optima match their roles in this global optimum". Can you build a Lower Bound LB(D) of unknown global optimum OPT(D) ? , where LB(D)

Hi Everyone,

Thinking about this further, what does this do to the "efficient market" hypothesis in economic theory?  

I'm not sure I have this 100% accurate, but I recall that market efficiency is based on every actor responding to their own stimuli.  As we've discussed above, this cannot possibly lead to the global optimum.  So, are markets inherently inefficient?

Thanks,

Stephen