skip to main content
10.5555/1402298.1402375acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

Trajectories of goods in distributed allocation

Published: 12 May 2008 Publication History

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]
S. Clearwater. Market-based control: A paradigm for Distributed Resource Allocation. World Scientific Publishing Co., 1996.
[5]
R. Dash, N. Jennings, and D. C. Parkes. Computational mechanism design: A call to arms. IEEE Intelligent Systems, pages 40--47, 2003.
[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]
P. E. Dunne, M. Wooldridge, and M. Laurence. The complexity of contract negotiation. Artificial Intelligence, 164(1--2):23--46, 2005.
[9]
U. Endriss and N. Maudet. On the communication complexity of multilateral trading. In Proc. AAMAS-2004. ACM Press, 2004.
[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]
M. Grabisch. k-order additive discrete fuzzy measures and their representation. Fuzzy Sets and Systems, 92:167--189, 1997.
[13]
J. Jensen. Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta Math., 30:175--193, 1906.
[14]
S. Kraus. Strategic Negotiation in Multiagent Environments. MIT Press, 2001.
[15]
H. Moulin. Axioms of Cooperative Decision Making. Cambridge University Press, 1988.
[16]
H. V. D. Parunak and S. Brueckner. Entropy and self-organization in multi-agent systems. In Proc. AGENTS-2001. ACM Press, 2001.
[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 Trans. Comput., C-29(12):1104--1113, 1980.
[20]
M. P. Wellman, A. Greenwald, and P. Stone. Autonomous Bidding Agents: Strategies and Lessons from the Trading Agent Competition. MIT Press, 2007.
[21]
M. Wooldridge. An Introduction to MultiAgent Systems. John Wiley and Sons, 2002.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2
May 2008
673 pages
ISBN:9780981738116

Sponsors

In-Cooperation

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 12 May 2008

Check for updates

Author Tags

  1. dynamics of complex systems
  2. resource allocation

Qualifiers

  • Research-article

Conference

AAMAS08
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 118
    Total Downloads
  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media