Non-zero-sum game system framework with tractable Nash equilibrium solution

1 . A computer-implemented device for processing a multi-agent system input to form an at least partially optimized output indicative of an action policy, the device comprising one or more processors configured to perform the following:

receiving the multi-agent system input, the multi-agent system input comprising a definition of a multi-agent system and defining behavior patterns of a plurality of agents based on system states, wherein the plurality of agents are driverless cars controlled by the device;

receiving an indication of an input system state from one or more sensors of the driverless cars;

performing an iterative machine learning process to estimate a single aggregate function representing the behavior patterns of the plurality of agents over a set of system states, wherein a representation of the multi-agent system is converted from a nonzero-sum stochastic game (SG) representation into a stochastic potential game (SPG) representation; and

iteratively processing the single aggregate function for the input system state to estimate an at least partially optimized set of actions for each of the plurality of agents in the input system state,

wherein the multi-agent system is transformed into an equivalent Markov decision process (MDP), including receiving, after interaction with an environment, a set of observations of rewards and state transitions based on which the MDP is decided using an application of supervised learning methods; and

wherein the MDP is for estimating the at least partially optimized set of actions for each of the plurality of agents in the input system state; and

sending controlling signals indicating the at least partially optimized set of actions to the one or more sensors of the driverless cars, so that the driverless cars carry out respective actions of the at least partially optimized set of actions.

2 . The device according to claim 1 , wherein the performing the iterative machine learning process comprises repeatedly performing the following until a predetermined level of convergence is reached:

generating a set of random system states;

estimating, based on the multi-agent system input, the behavior patterns of the plurality of agents in the system states;

estimating an error between the estimated behavior patterns and the behavior patterns predicted by a predetermined candidate aggregate function, the error representing a level of convergence; and

adapting the predetermined candidate aggregate function based on the estimated behavior patterns.

3 . The device according to claim 2 , wherein the set of random system states are generated based on a predetermined probability distribution.

4 . The device according to claim 2 , wherein the error is estimated as between derivatives of the estimated behavior pattern and the behavior patterns.

5 . The device according to claim 2 , wherein the error is estimated as a sum of squares of differences between estimated behavior patterns and respective behavior patterns predicted by the candidate aggregate function.

6 . The device according to claim 1 , wherein the single aggregate function is formed so that maxima of the aggregate function yield a behavior pattern that corresponds to a solution of the SPG.

7 . The device according to claim 1 , wherein the at least partially optimized output comprises a collectively optimal action policy for the plurality of agents in the input system state.

8 . The device according to claim 1 , wherein the at least partially optimized output represents Nash equilibrium behavior pattern of the agents in the input system state.

9 . The device according to claim 1 , wherein the agents are autonomous vehicles and the system states are vehicular system states.

10 . The device according to claim 1 , wherein the agents are communications routing devices and the system states are data flows.

11 . The device according to claim 1 , wherein the agents are data processing devices and the system states are computation tasks.

12 . The device according to claim 1 , wherein the aggregate function includes jointly maximizing rewards of the agents over a set of system states.

13 . A method for processing a multi-agent system input to form an at least partially optimized output indicative of an action policy, the method which is performed by a computer-implemented device comprising:

receiving the multi-agent system input, the multi-agent system input comprising a definition of a multi-agent system and defining behavior patterns of a plurality of agents based on system states, wherein the plurality of agents are driverless cars controlled by the device;

receiving an indication of an input system state from one or more sensors of the driverless cars;

performing an iterative machine learning process to estimate a single aggregate function representing the behavior patterns of the plurality of agents over a set of system states, wherein a representation of the multi-agent system is converted from a nonzero-sum stochastic game (SG) representation into a stochastic potential game (SPG) representation; and

iteratively processing the single aggregate function for the input system state to estimate an at least partially optimized set of actions for each of the plurality of agents in the input system state,

wherein the multi-agent system is transformed into an equivalent Markov decision process (MDP), including receiving, after interaction with an environment, a set of observations of rewards and state transitions based on which the MDP is decided using an application of supervised learning methods; and

wherein the MDP is for estimating the at least partially optimized set of actions for each of the plurality of agents in the input system state; and

sending controlling signals indicating the at least partially optimized set of actions to the one or more sensors of the driverless cars, so that the driverless cars carry out respective actions of the at least partially optimized set of actions.

14 . The method according to claim 13 , further comprising: causing each of the agents to implement a respective action of the at least partially optimized set of actions.

15 . A non-transitory computer readable medium storing in non-transient form a set of instructions for causing one or more processors of a computer-implemented device to perform a method for processing a multi-agent system input to form an at least partially optimized output indicative of an action policy, the method comprising:

receiving the multi-agent system input, the multi-agent system input comprising a definition of a multi-agent system and defining behavior patterns of a plurality of agents based on system states, wherein the plurality of agents are driverless cars controlled by the device;

receiving an indication of an input system state from one or more sensors of the driverless cars;

performing an iterative machine learning process to estimate a single aggregate function representing the behavior patterns of the plurality of agents over a set of system states, wherein a representation of the multi-agent system is converted from a nonzero-sum stochastic game (SG) representation into a stochastic potential game (SPG) representation; and

iteratively processing the single aggregate function for the input system state to estimate an at least partially optimized set of actions for each of the plurality of agents in the input system state,

wherein the multi-agent system is transformed into an equivalent Markov decision process (MDP), including receiving, after interaction with an environment, a set of observations of rewards and state transitions based on which the MDP is decided using an application of supervised learning methods; and

wherein the MDP is for estimating the at least partially optimized set of actions for each of the plurality of agents in the input system state; and

sending controlling signals indicating the at least partially optimized set of actions to the one or more sensors of the driverless cars, so that the driverless cars carry out respective actions of the at least partially optimized set of actions.

16 . The non-transitory computer readable medium according to claim 15 , wherein the method further comprises: causing each of the agents to implement a respective action of the at least partially optimized set of actions.

17 . The non-transitory computer readable medium according to claim 15 , wherein the performing the iterative machine learning process comprises repeatedly performing the following until a predetermined level of convergence is reached:

generating a set of random system states;

estimating, based on the multi-agent system input, the behavior patterns of the plurality of agents in the system states;

estimating an error between the estimated behavior patterns and the behavior patterns predicted by a predetermined candidate aggregate function, the error representing a level of convergence; and

adapting the predetermined candidate aggregate function based on the estimated behavior patterns.

18 . The non-transitory computer readable medium according to claim 17 , wherein the set of random system states are generated based on a predetermined probability distribution.

19 . The non-transitory computer readable medium according to claim 17 , wherein the error is estimated as between derivatives of the estimated behavior pattern and the behavior patterns.

20 . The non-transitory computer readable medium according to claim 17 , wherein the error is estimated as a sum of squares of differences between estimated behavior patterns and respective behavior patterns predicted by the candidate aggregate function.