Method and system for the dynamic allocation of resources based on fairness, throughput, and user behavior measurement

• US 8,909,567 B2
• Filed: 02/20/2012
• Issued: 12/09/2014
• Est. Priority Date: 02/20/2012
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Kang, Dhanwant Singh, Liu, Hua, Sun, Tong
• Primary Examiner(s): Gaffin, Jeffrey A.
• Assistant Examiner(s): Bharadwaj, Kalpana
• Application Number:
  US13/400,323
• Publication Number:
  US 20130218814A1
• Time in Patent Office: 1,023 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06Q 10/00 Administration; Management
• CPC Class Codes: G06Q 50/00 Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism healthcare informatics G16H

Abstract

A system and method for the dynamic allocation of resources based on fairness, throughput, and user behavior measurement. A resource allocation decision can be made based on an index value computed by a selection index function. A fairness coefficient and a throughput coefficient, which represent the significance of fairness and throughput can be computed utilizing a reinforcement learning algorithm. The degree of fairness and throughput coefficient can be varied while allocating resources. A user behavior coefficient with respect to a user can be computed to determine the degree of cooperativeness of the user with other users and the value of user behavior coefficient can be updated each time it interacts with the system.

Claims

1. A method for dynamically allocating resources in a process, said method comprising:

estimating a fairness coefficient and a throughput coefficient that respectively represent a significance of a fairness and a throughput utilizing a reinforcement learning algorithm in order to thereafter vary a degree of said fairness coefficient and said throughput coefficient while allocating a resource;

computing a user behavior coefficient with respect to a user to determine a degree of cooperativeness of said user with a plurality of other users and updating said user behavior coefficient thereof in order to dynamically allocate said resource in a process with a high user satisfaction and a retention rate;

implementing an exploration and exploitation as a function of a temperature parameter by said reinforcement learning algorithm; and

determining an optimal value of said fairness coefficient and said throughput coefficient for successive iterations utilizing a probability function based on a selection index and said temperature parameter.

2. The method of claim 1 further comprising rendering a resource allocation decision based on an index value computed by a selection index function.

3. The method of claim 1 further comprising applying said fairness measurement based on a heterogeneous user demand.

4. The method of claim 1 further comprising adjusting said temperature parameter in accordance with an environment setting wherein a low temperature leads to a higher exploitation and a lower exploration, and a high temperature leads to a lower exploitation and a higher exploration.

5. The method of claim 1 further comprising:

randomly rendering a selection decision when said temperature parameter value is high so that a solution space is explored at said higher temperature parameter value; and

rendering a selection decision utilizing a greedy approach when said temperature parameter value is low.

6. The method of claim 1 further comprising considering said user behavior coefficient as a parameter for said resource allocation by iteratively interacting with said user in order to motivate said user to be more cooperative.

7. The method of claim 6 further comprising:

initiating a negotiation process by designating a value of a reduction factor in order to thereafter select a maximum number of users with a highest selection index value and a demand less than a total availability; and

considering a user with a low value of said user behavior coefficient as a greedy user that tends to be less flexible in said negotiation process and a user with a high value as a cooperative user that is more flexible in said negotiation process.

8. The method of claim 6 further comprising assigning said user behavior coefficient value to each user depending on said behavior in order to motivate said user to be more cooperative for efficiently allocating said resource.

9. The method of claim 1 wherein said cooperative user possesses a higher probability of selection in a future interaction as compared to said greedy user.

10. The method of claim 1 further comprising specifying a weight age for said fairness and said throughput based on a business requirement in order to thereafter determine an optimal value for said fairness weight age and said throughput weight age utilizing said reinforcement learning algorithm.

11. A system for dynamically allocating resources in a process, said system comprising:

a processor;

a data bus coupled to said processor; and

a computer-usable medium embodying computer code, said computer-usable medium being coupled to said data bus, said computer program code comprising instructions executable by said processor and configured for;

estimating a fairness coefficient and a throughput coefficient that respectively represent a significance of a fairness and a throughput utilizing a reinforcement learning algorithm in order to thereafter vary a degree of said fairness coefficient and said throughput coefficient while allocating a resource;

computing a user behavior coefficient with respect to a user to determine a degree of cooperativeness of said user with a plurality of other users and updating said user behavior coefficient thereof in order to dynamically allocate said resource in a process with a high user satisfaction and a retention rate;

implementing an exploration and exploitation as a function of a temperature parameter by said reinforcement learning algorithm; and

determining an optimal value of said fairness coefficient and said throughput coefficient for successive iterations utilizing a probability function based on a selection index and said temperature parameter.

12. The system of claim 11 wherein said instructions are further configured for rendering a resource allocation decision based on an index value computed by a selection index function.

13. The system of claim 11 wherein said instructions are further configured for applying said fairness measurement based on a heterogeneous user demand.

14. The system of claim 11 wherein said instructions are further configured for adjusting said temperature parameter in accordance with an environment setting wherein a low temperature leads to a higher exploitation and a lower exploration, and a high temperature leads to a lower exploitation and a higher exploration.

15. The system of claim 11 wherein said instructions are further configured for:

randomly rendering a selection decision when said temperature parameter value is high so that a solution space is explored at said higher temperature parameter value; and

rendering a selection decision utilizing a greedy approach when said temperature parameter value is low.

16. A non-transitory processor-readable medium storing code representing instructions to cause a process to perform a process to dynamically allocate resources in a process, said code comprising code to:

estimate a fairness coefficient and a throughput coefficient that respectively represent a significance of a fairness and a throughput utilizing a reinforcement learning algorithm in order to thereafter vary a degree of said fairness coefficient and said throughput coefficient while allocating a resource;

compute a user behavior coefficient with respect to a user to determine a degree of cooperativeness of said user with a plurality of other users and updating said user behavior coefficient thereof in order to dynamically allocate said resource in a process with a high user satisfaction and a retention rate;

implement an exploration and exploitation as a function of a temperature parameter by said reinforcement learning algorithm; and

determine an optimal value of said fairness coefficient and said throughput coefficient for successive iterations utilizing a probability function based on a selection index and said temperature parameter.

17. The non-transitory processor-readable medium of claim 16 wherein said code comprises code to render a resource allocation decision based on an index value computed by a selection index function.