Resource allocation games with changing resource capacities

In this paper we study a class of resource allocation games which are inspired by the El Farol Bar problem. We consider a system of competitive agents that have to choose between several resources characterized by their time dependent capacities. The agents using a particular resource are rewarded if their number does not exceed the resource capacity, and punished otherwise. Agents use a set of strategies to decide what resource to choose, and use a simple reinforcement learning scheme to update the accuracy of strategies. A strategy in our model is simply a lookup table that suggests to an agent what resource to choose based on the actions of its neighbors at the previous time step. In other words, the agents form a social network whose connectivity controls the average number of neighbors with whom each agent interacts. This statement of the adaptive resource allocation problem allows us to fully parameterize it by a small set of numbers. We study the behavior of the system via numeric simulations of 100 to 5000 agents using one to ten resources. Our results indicate that for a certain range of parameters the system as a whole adapts effectively to the changing capacity levels and results in very little under- or over-utilization of the resources.

• Publication year

  2003

• Venue

  Adaptive Agents and Multi-Agent Systems

• Publication date

  2003-07-14

• Fields of study

  Mathematics, Computer Science, Economics

• Identifiers
  DOI 10.1145/860575.860599
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An improved search technique for optimal winner determination in combinatorial auctions

  2004cited by this paper
• Multi Agent Reinforcement Learning Independent vs Cooperative Agents

  2003cited by this paper
• Adaptive Boolean networks and minority games with time-dependent capacities.

  2002cited by this paper
• Reinforcement learning of coordination in cooperative multi-agent systems

  2002cited by this paper
• Market Clearability

  2001cited by this paper
• Sequential Auctions for the Allocation of Resources with Complementarities

  1999cited by this paper
• Minority game with arbitrary cutoffs

  1999cited by this paper
• Decentralized Markets versus Central Control: A Comparative Study

  1999cited by this paper
• Adaptive Competition, Market Efficiency, and Phase Transitions

  1999influential reference
• Phase transition and symmetry breaking in the minority game.

  1999cited by this paper
• Phase Transitions in Random Networks with Multiple States

  1999cited by this paper
• A market protocol for decentralized task allocation

  1998cited by this paper
• The Dynamics of Reinforcement Learning in Cooperative Multiagent Systems

  1998cited by this paper
• The Theory of Learning in Games

  1998cited by this paper
• Irrelevance of memory in the minority game

  1998cited by this paper
• On the minority game: Analytical and numerical studies

  1998cited by this paper
• The moving target function problem in multi-agent learning

  1998cited by this paper
• Challenger: a multi-agent system for distributed resource allocation

  1997cited by this paper
• Adaptive Competition, Market Efficiency, Phase Transitions and Spin-Glasses

  1997cited by this paper
• Emergence of cooperation and organization in an evolutionary game

  1997influential reference
• Market-Based Negotiation for Digital Library Services

  1996cited by this paper
• Limitations of the Vickrey Auction in Computational Multiagent Systems

  1996cited by this paper
• Market-oriented programming: some early lessons

  1996cited by this paper
• Market-based control: a paradigm for distributed resource allocation

  1996cited by this paper
• Inductive Reasoning and Bounded Rationality

  1994cited by this paper
• Learning to Coordinate without Sharing Information

  1994cited by this paper
• Adaptive Load Balancing: A Study in Multi-Agent Learning

  1994cited by this paper
• Learning from delayed rewards

  1989influential reference
• A Microeconomic Approach to Optimal Resource Allocation in Distributed Computer Systems

  1989cited by this paper
• The evolution of cooperation

  1981cited by this paper
• The contract net protocol

  1980influential reference
• A class of games possessing pure-strategy Nash equilibria

  1973cited by this paper
• Theory of games and economic behavior

  1945cited by this paper

• Methodologies in Game Theory for Optimizing Collaboration in Microservices

  2025influential citation
• The El Farol Bar Problem: A Comparative Analysis of Expectation Models Used in Decision Making

  2023cites this paper
• Distributed Medium Access Control Method through Inductive Reasoning

  2021cites this paper
• Memory effects on binary choices with impulsive agents: Bistability and a new BCB structure.

  2019cites this paper
• Random-Access Control Method for MTC in an LTE System Inspired by the Minority Game

  2018cites this paper
• Weighted Multi-resource Minority Games

  2016cites this paper
• Reinforcement Learning Techniques for Decentralized Self-adaptive Service Assembly

  2016cites this paper
• A Game Theory Model for Self-adapting Traffic Flows with Autonomous Navigation

  2016cites this paper
• A Game Theoretic Method for Resource Allocation in Scientific Cloud

  2016cites this paper
• A game theoretical model for profit maximization resource allocation in cloud environment with budget and deadline constraints

  2016cites this paper
• On characterizing and modelling collective behaviour in non-coordinated wireless networks

  2016cites this paper
• Capacity, information and minority games in public transport

  2016cites this paper
• Paradox Phenomena in Autonomously Self-Adapting Navigation

  2015cites this paper
• Self-managed resources in network virtualisation environments

  2015cites this paper
• Efficient Nash Equilibrium Resource Allocation Based on Game Theory Mechanism in Cloud Computing by Using Auction

  2015cites this paper
• Resource-provision scheduling in cloud datacenter

  2015cites this paper
• Online Routing Games and the Benefit of Online Data

  2014cites this paper
• On Intention-Propagation-Based Prediction in Autonomously Self-Adapting Navigation

  2014cites this paper
• Robustness of Optimality of Exploration Ratio against Agent Population in Multiagent Learning for Nonstationary Environments

  2014cites this paper
• The value of less connected agents in Boolean networks

  2013cites this paper
• Advances in Applied Self-Organizing Systems

  2013cites this paper
• Evolving Mechanisms in Boolean Games

  2013cites this paper
• Statistical Mechanics of Competitive Resource Allocation

  2013cites this paper
• Break with agents who listen to too many others (at least when making Boolean decisions!)

  2012influential citation
• MCSP: a new algorithm for scheduling in Wireless Sensor Networks

  2012cites this paper
• Heterogeneous Populations of Learning Agents in the Minority Game

  2011cites this paper
• Ressource allocation and schelduling models for cloud computing

  2011cites this paper
• Minority-Game-based resource allocation for run-time reconfigurable multi-core processors

  2011influential citation
• Heterogeneous Populations of Learning Agents in Minority Games

  2011cites this paper
• Evolutionary minority game based on genetic algorithm

  2011cites this paper
• Adaptive resource management for simultaneous multitasking in mixed-grained reconfigurable multi-core processors

  2011cites this paper
• Decision-Making Using Random Boolean Networks In The El Farol Bar Problem

  2011cites this paper
• Robust interference management to satisfy allowable outage probability using minority game

  2010cites this paper
• Advanced Scheduling Schemes in 4G Systems

  2010cites this paper
• Decentralised agent-based resource allocation in open and dynamic environments

  2010cites this paper
• Competing Schedulers

  2010cites this paper
• Hai-xiang Zhao Sujet : Artificial Intelligence Models for Building Energy Consumption Analysis

  2010cites this paper
• A New Game Theoretical Resource Allocation Algorithm for Cloud Computing

  2010cites this paper
• Grid resource selection based on reinforcement learning

  2010cites this paper
• An Adaptive Strategy for Resource Allocation with Changing Capacities

  2009influential citation
• An Adaptive Bidding Strategy for Combinatorial Auction-Based Resource Allocation in Dynamic Markets

  2009cites this paper
• Learning in Minority Games with Multiple Resources

  2009influential citation
• Learning in the time-dependent minority game

  2009cites this paper
• Individual agent's wealth in minority games

  2009cites this paper
• Game Theoretic Scheduling of Grid Computations

  2009cites this paper
• Cloud Computing

  2009cites this paper
• Minority game for cognitive radios: Cooperating without cooperation

  2008cites this paper
• Improving Self-organized Resource Allocation with Effective Communication

  2008cites this paper
• Maximising Personal Utility Using Intelligent Strategy in Minority Game

  2008cites this paper
• An Adaptive Strategy for Allocation of Resources with Gradually or Abruptly Changing Capacities

  2008influential citation
• A Self-organizing Sensing System for Structural Health Monitoring of Aerospace Vehicles

  2008cites this paper
• A group selection pattern for multiagent systems and its application to grid computing

  2008cites this paper
• Self-organizing Nomadic Services in Grids

  2008cites this paper
• The Potluck Problem

  2008cites this paper
• Towards self-organising agent-based resource allocation in a multi-server environment

  2007cites this paper
• An Adaptive Strategy for Resource Allocation Modeled as Minority Game

  2007influential citation
• An adaptive strategy for minority games

  2007cites this paper
• An Agent-Based Framework for Emergent Process Management

  2006cites this paper
• Analysis of Complexity and Time Restriction in Resources Allocation Problems

  2006cites this paper
• A multiagent system manages collaboration in emergent processes

  2005cites this paper
• An Information-Based Agent

  2005cites this paper
• Mathematical Modeling of Large Multi-Agent Systems

  2005cites this paper
• Managing Collaboration in a Multiagent System

  2005cites this paper
• Resource Allocation in the Grid with Learning Agents

  2005cites this paper
• Control of Learning Types for Efficient Resource Allocation

  2004cites this paper
• A Review of Probabilistic Macroscopic Models for Swarm Robotic Systems

  2004cites this paper
• Resource allocation in the grid using reinforcement learning

  2004cites this paper