SYSTEM AND METHOD FOR DECISION MAKING IN STRATEGIC ENVIRONMENTS

• US 20150018060A1
• Filed: 02/04/2014
• Published: 01/15/2015
• Est. Priority Date: 07/11/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Naveh, Yehuda, Ronen, Amir
• Granted Patent: US 10,537,801 B2
• Time in Patent Office: Days
• US Class Current: 463/9
• CPC Class Codes: A63F 13/46 Computing the game score
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06Q 10/0637 Strategic management or analysis, e.g. setting a goal or target of an organisation; Planning actions based on goals; Analysis or evaluation of effectiveness of goals

Abstract

In one embodiment, payoffs to an actor during the strategic game according to a solution concept is simulated a predetermined number of times. A machine learning tool is used to predict a payoff based on the predetermined number of payoffs according to the solution concept, wherein the machine learning tool is trained with plurality of pairs, each pair comprising a set of simulated payoffs and an actual payoff, wherein the simulated payoffs are predetermined number of payoffs determined in accordance with the solution concept. In another embodiment, a process tree representative of a strategic game involving actors is obtained. The process tree may comprise computational nodes, and leaf nodes which define payoff based on computations of the computational nodes.

The process tree is reduced to a game tree representing the strategic game by simulating routes in the process tree.

Claims

1. A computerized apparatus having a processor, the processor being adapted to perform the steps of:

obtaining a description of a strategic game, wherein an actor makes a strategic decision in the strategic game;

simulating a predetermined number of payoffs to the actor during the strategic game, wherein said simulating is performed based on a solution concept; and

utilizing a machine learning prediction tool to predict a payoff to the actor based on the predetermined number of payoffs, wherein the machine learning predicting tool is trained with plurality of pairs, each pair comprising a set of simulated payoffs and an actual payoff, wherein the simulated payoffs are predetermined number of payoffs determined in accordance with the solution concept.

2. The computerized apparatus of claim 1, wherein said simulating comprises:

simulating a first portion of the predetermined number of payoffs using a first solution concept and simulating a second portion of the predetermined number of payoffs using a second solution concept.

3. The computerized apparatus of claim 1, wherein the solution concept is selected from the group consisting of:

quantal response equilibrium, Nash equilibrium, and quantal level k equilibrium.

4. The computerized apparatus of claim 1, wherein said simulating comprises simulating more than the predetermined number of payoffs, and extracting percentiles from the more than predetermined number of payoffs to extract the predetermined number of payoffs.

5. The computerized apparatus of claim 1, wherein the processor is further adapted to:

receive from a user a payoff outcome to the actor in the strategic game; and

train the machine learning prediction tool based on a set of the predetermined number of payoffs and the payoff outcome.

6. The computerized apparatus of claim 1, wherein the processor is further adapted to normalize the predetermined number of payoffs, and wherein the set of simulated payoffs are normalized.

7. The computerized apparatus of claim 1, wherein said obtaining the description of the strategic game comprises:

obtaining a process tree, wherein the process tree comprises computational nodes and leaf nodes, wherein the computational nodes define a computation value for a variable, wherein the leaf nodes define payoffs for the actors, wherein at least for one leaf node the payoff is defined based on the computational value of the variable; and

constructing the strategic game based on one or more simulations of the process tree.

8. A computerized apparatus having a processor, the processor being adapted to perform the steps of:

obtaining a process tree representative of a strategic game involving actors, wherein the process tree comprises computational nodes, strategic decision nodes and leaf nodes, wherein the strategic decision nodes are associated with a strategic decision of actors, wherein the computational nodes define a computation value for a variable, wherein the leaf nodes define payoffs for the actors, wherein at least for one leaf node the payoff is defined based on the computational value of the variable;

simulating routes defined in the process tree to reduce the process tree into a game tree representing the strategic game.

9. The computerized apparatus of claim 8, wherein said processor is further adapted to perform the steps of:

extracting a feature from the game tree, wherein the feature is based on predictions of payoffs in the strategic game in accordance with a solution concept, wherein the feature comprises a predetermined number of predictions which is not defined by or based on the strategic game;

utilizing a machine learning prediction tool to predict a payoff based on the feature, wherein the machine learning predicting tool is trained with plurality of pairs, each pair comprising a training feature and an actual payoff, wherein the training feature is based on predictions of payoffs in strategic games in accordance with the solution concept, wherein the training features comprise the predetermined number of predictions, wherein the actual payoffs are actual payoffs that were received in the strategic games.

10. The computerized apparatus of claim 8, wherein the strategic game is non-deterministic, and wherein said simulating comprises:

simulating each route a predetermined number of times and aggregating simulated payoffs to determine for each route an expected payoff.

11. The computerized apparatus of claim 8, wherein said processor is further adapted to perform the steps of:

obtaining a query regarding expected utility from the strategic game;

utilizing a machine learning prediction tool to predict the expected utility; and

outputting a query result based on the prediction of the machine learning prediction tool.

12. The computerized apparatus of claim 11, wherein the query assumes a predetermined actor makes a predetermined action, wherein said simulating simulates that the predetermined actor makes the predetermined action thereby determining the game tree to represent the strategic game under the assumption that the predetermined actor makes the predetermined action.

13. A computer program product comprising a non-transitory computer readable medium retaining program instructions, which instructions when read by a processor, cause the processor to perform a method comprising:

obtaining a description of a strategic game, wherein an actor makes a strategic decision in the strategic game;

simulating a predetermined number of payoffs to the actor during the strategic game, wherein said simulating is performed based on a solution concept; and

utilizing a machine learning prediction tool to predict a payoff to the actor based on the predetermined number of payoffs, wherein the machine learning predicting tool is trained with plurality of pairs, each pair comprising a set of simulated payoffs and an actual payoff, wherein the simulated payoffs are predetermined number of payoffs determined in accordance with the solution concept.

14. The computer program product of claim 13, wherein said obtaining the description of the strategic game comprises:

obtaining a process tree, wherein the process tree comprises computational nodes and leaf nodes, wherein the computational nodes define a computation value for a variable, wherein the leaf nodes define payoffs for the actors, wherein at least for one leaf node the payoff is defined based on the computational value of the variable; and

constructing the strategic game based on one or more simulations of the process tree.