Trajectories of goods in distributed allocation

ABSTRACT

Distributed allocation mechanisms rely on the agents' autonomous (and supposedly rational) behaviour: states evolve as a result of agents contracting deals and exchanging resources. It is no surprise that restrictions on potential deals also restrict the reachability of some desirable states, for instance states where goods are efficiently allocated. In particular topological restrictions make any attempt to guarantee asymptotic convergence to an optimal allocation impossible in most cases. In this paper, we concentrate on the dynamics of such systems; more precisely we study the trajectories of goods in such iterative reallocative processes. Our first contribution is to propose an upper bound on the length of the trajectories of goods, when agent utility functions are modular. The second innovative aspect of the paper is then to discuss how this affects, on average, the quality of the states that are reached. Finally, a preliminary study of the non-modular case is proposed, examining how synergetic effects between items can affect their trajectories.

REFERENCES

• 1: D. Aldous and P. Diaconis. Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Amer. Math. Soc., 36:413--432, 1999.
• 2: Y. Chevaleyre, P. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Padget, S. Phelps, J. Rodríguez-Aguilar, and P. Sousa. Issues in multiagent resource allocation. Informatica, 30, 2006.
• 3: Y. Chevaleyre, U. Endriss, and N. Maudet. Allocating goods on a graph to eliminate envy. In Proc. 22nd AAAI Conference on Artificial Intelligence (AAAI-2007). AAAI Press, 2007.
• 4: Scott H. Clearwater, Market-based control: a paradigm for distributed resource allocation, World Scientific Publishing Co., Inc., River Edge, NJ, 1996
• 5: Rajdeep K. Dash , Nicholas R. Jennings , David C. Parkes, Computational-Mechanism Design: A Call to Arms, IEEE Intelligent Systems, v.18 n.6, p.40-47, November 2003 [doi>10.1109/MIS.2003.1249168]
• 6: D. Dolgov and E. Durfee. Resource allocation among agents with MDP-induced preferences. Journal of Artificial Intelligence Research, 27:505--549, 2006.
• 7: P. E. Dunne. Extremal behaviour in multiagent contract negotiation. Journal of Artif. Intell. Research, 23:41--78, 2005.
• 8: Paul E. Dunne , Michael Wooldridge , Michael Laurence, The complexity of contract negotiation, Artificial Intelligence, v.164 n.1-2, p.23-46, May 2005 [doi>10.1016/j.artint.2005.01.006]
• 9: Ulle Endriss , Nicolas Maudet, On the Communication Complexity of Multilateral Trading, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.622-629, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.202]
• 10: U. Endriss, N. Maudet, F. Sadri, and F. Toni. Negotiating socially optimal allocations of resources. Journal of Artif. Intell. Research, 25:315--348, 2006.
• 11: R. A. Fisher and L. H. Tippett. On the estimation of the frequency distributions of the largest or smallest member of a sample. Proc. Cambridge Phil. Soc., 24:180--190, 1928.
• 12: Michel Grabisch, k-order additive discrete fuzzy measures and their representation, Fuzzy Sets and Systems, v.92 n.2, p.167-189, Dec. 1, 1997 [doi>10.1016/S0165-0114(97)00168-1]
• 13: J. Jensen. Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta Math., 30:175--193, 1906.
• 14: Sarit Kraus, Strategic negotiation in multiagent environments, MIT Press, Cambridge, MA, 2001
• 15: H. Moulin. Axioms of Cooperative Decision Making. Cambridge University Press, 1988.
• 16: H. Van Dyke Parunak , Sven Brueckner, Entropy and self-organization in multi-agent systems, Proceedings of the fifth international conference on Autonomous agents, p.124-130, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376024]
• 17: J. S. Rosenschein and G. Zlotkin. Rules of Encounter. MIT Press, 1994.
• 18: T. Sandholm. Contract types for satisficing task allocation: I Theoretical results. In Proc. AAAI Spring Symposium: Satisficing Models, 1998.
• 19: R. G. Smith, The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver, IEEE Transactions on Computers, v.29 n.12, p.1104-1113, December 1980 [doi>10.1109/TC.1980.1675516]
• 20: Michael P. Wellman , Amy Greenwald , Peter Stone, Autonomous Bidding Agents: Strategies and Lessons from the Trading Agent Competition (Intelligent Robotics and Autonomous Agents), The MIT Press, 2007
• 21: Michael Woolridge , Michael J. Wooldridge, Introduction to Multiagent Systems, John Wiley & Sons, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Economics

Keywords:
dynamics of complex systems, resource allocation