In this paper, we propose a resource assignment scheme in the computational grid based on the notion of market equilibrium. Market equilibrium is a key concept commonly used in the field of game theory, and in this framework, we determine the "price" of resources owned by the service providers so that it fulfills the Nash equilibrium of the given market consisting of clients and service providers. The degree of satisfaction of clients is modeled as a linear utility function of acquired resources, and as a constraint concerned with the clients, we use the notion of budgets. Our proposed scheme a semi-algorithm which finds an assignment of resources to the clients so that it maximizes the utility of the clients provided that: 1) all resources are completely exhausted and 2) the surplus of the clients is at most e using O(nlog(nM/e)) maximum flow computations, where M is the total amount of budgets given to the clients at the initial state and e is a positive real representing the accuracy of approximation.
展开▼
