This research involves the development of automated negotiation protocols for autonomous agents in negotiation networks, where each agent can only negotiate with few selected neighbors. That is, we develop agents that can carry out any number of simultaneous negotiations with other selfish agents. For example, they could be routers in the Internet negotiating over which packets to route and which to drop, or purchasing agents in a supply chain deciding what to buy and at what price, or web services deciding who to provide services for and at what price, or sensors in a sensor network deciding which measurements to make and who to forward the results. Our research involves building the negotiation strategies for selfish rational agents that individuals and companies will want to use, along with the negotiation protocols that ensure the agents' interactions result in efficient global resource allocations.
The problem of negotiation networks combines features of characteristic form games and bargaining games from game theory, combinatorial auctions and distributed mechanism design from Economics, network exchange theory from Sociology, and distributed algorithm design from computer science. Our research brings together results from these disparate fields into one framework and provides algorithmic solutions for the dynamic, distributed problem of resource allocation among self-interested parties, in contrast with game theory and Economics' solutions which are typically steady-state axiomatic solutions. Success in this research is potentially transformative as it will provide the foundation for the engineering of protocols and efficient algorithms for distributed resource allocation, which is a pervasive problem in our ever-growing highly-interconnected society.
where each agent can only negotiation with a few select neighbors. Our initial research focused on distributed combinatorial auctions and in the supply chain and seaport terminal and transportation domains. We published negotiation algorithms that agents can use to distributively solve a combinatorial auction where each agent has a preferences over the set of goods he wants to buy. These negotiation algorithms do not always converge to the utilitarian solution, but we showed that under certain circumstances they are very likely to reach a solution that is very close to the utilitarian solution. That is, by negotiating with each other the agents can reach an allocation that has good social welfare characteristics. We furthermore showed how buyer agents can be incentivized to solve parts of the winner determination problem in the combinatorial auctions they participate; their incentives are derived from the higher expected profits they will reap by performing some of the calculations. Taken together these results layout a plan for the development of world-wide distributed combinatorial auction protocols which will enable businesses to find better solutions without the need for a centralized controller and without having to abandon their profit-maximizing strategies. We also explored supply chain and transportation domains with the use of agent-based simulations. We built supply chain simulations following standard models from management theory which describe how agents (suppliers) might establish relationships with other, thus generating a supply chain from the bottom up. We then analyzed these emergent supply chains to determine their resiliency to attacks: either random errors that bring down a node or targeted attacks geared towards the most connected nodes. We found that the negotiation rules that the agents must work under do have an effect on the emergent supply network topology which can then be responsible for big differences in the resiliency of the final network. Our research proposes some simple rules which can increase survivability, such as increasing the social resources of the agents, but further work needs to be done to further refine these. Finally, we applied our agent-based modeling expertise to the development of seaport container dock simulations which try to find optimal strategies for the placement of containers in a dock and the movement of cranes. In these simulations the cranes negotiate with each other and with the incoming trucks to find the optimal solutions that all agents can agree upon. These agent-based simulations are currently being extended to include the wider transportation network where we will study how to best route trucks and containers using the distributed negotiation techniques we have developed.
