Optimal policies for load balancing for distributed and strategic agents (more technically, optimal coordination mechanisms for machine scheduling)

A computer storage media having computer-executable instructions recorded thereon, the computer-executable instructions, upon execution to configure a computer for load balancing a plurality of tasks on a plurality of distributed machines, by performing operations comprising:

• receiving a plurality of tasks at a first networked device assigned by two or more independent strategic agents;
• ranking a task for completion based on an inefficiency parameter that is a function of the task and of resources available to the first device and at least one additional networked device;
• and
• calculating the inefficiency parameter that divides the time required to process the task on the first device by the minimum time required to process the task on any suitable device networked with the first device.

A system that load balances tasks assigned by self-interested agents to a plurality of machines on a network, comprising:

• a processor;
• a memory operatively coupled to the processor for executing components;
• a distribution component that receives a plurality of tasks at a machine, assigned to the machine by at least one self-interested agent, on a network of a plurality of machines;
• an ordering component that schedules each of the plurality of tasks for processing on the machine in a non-decreasing order of task inefficiency;
• and
• a partition component that subdivides the machine into a plurality of virtual machines that can simultaneously process the plurality of tasks assigned to the machine, the number of virtual machines, b, is equal to ┌log m┐, where m is the number of the plurality of machines.

A system that load balances tasks assigned by self-interested agents to a plurality of machines on a network, comprising:

• a processor;
• a memory operatively coupled to the processor for executing components;
• a distribution component that receives a plurality of tasks at a machine, assigned to the machine by at least one self-interested agent, on a network of a plurality of machines;
• an ordering component that schedules each of the plurality of tasks for processing on the machine in a non-decreasing order of task inefficiency;
• and
• a partition component that subdivides the machine into a plurality of virtual machines that can simultaneously process the plurality of tasks assigned to the machine, the distribution component assigns an individual task to a virtual machine of the machine if the task inefficiency for the individual task on the machine is less than the number of the plurality of machines.

A method for load balancing tasks, comprising:

• receiving, a plurality of tasks at a machine, assigned to the machine by at least one self-interested agent, on a network of a plurality of machines;
• scheduling each of the plurality of tasks for processing on the machine in a non- decreasing order of task inefficiency;
• and
• subdividing the machine into a plurality of virtual machines that can simultaneously process the plurality of tasks assigned to the machine, an individual task of the plurality of tasks being scheduled on the plurality of virtual machines in random order of inefficiency.

A computer storage media having computer-executable components recorded thereon, the computer-executable components, upon execution to configure a computer for load balancing a plurality of tasks on a plurality of distributed machines, the computer-executable components comprising:

• a distribution component that receives a plurality of tasks at a machine, assigned to the machine by at least one self-interested agent, on a network of a plurality of machines;
• an ordering component that schedules each of the plurality of tasks for processing on the machine in a non-decreasing order of task inefficiency;
• and
• a partition component that subdivides the machine into a plurality of virtual machines that can simultaneously process the plurality of tasks assigned to the machine, an individual task of the plurality of tasks being scheduled on the plurality of virtual machines in increasing order of inefficiency.

A computer storage media having computer-executable instructions recorded thereon, the computer-executable instructions, upon execution to configure a computer for load balancing a plurality of tasks on a plurality of distributed machines, by performing operations comprising:

• receiving a plurality of tasks at a first networked device assigned by two or more independent strategic agents;
• ranking a task for completion based on an inefficiency parameter that is a function of the task and of resources available to the first device and at least one additional networked device;
• and
• coordinating a shortest time first algorithm or a random time algorithm with the inefficiency parameter so that a local machine policy minimizing global completion time of a plurality of tasks scheduled to a plurality of machines by a plurality of independent strategic agents converges to pure Nash equilibria.