Method and system for approximating value functions for cooperative games

• US 7,079,985 B2
• Filed: 10/28/2005
• Issued: 07/18/2006
• Est. Priority Date: 04/06/2001
• Status: Expired due to Fees

• Current Assignee: Barry E. Feldman
• Original Assignee: Barry E. Feldman
• Inventors: Feldman, Barry E.
• Primary Examiner(s): Raymond, Edward
• Application Number:
  US11/262,285
• Publication Number:
  US 20060106570A1
• Time in Patent Office: 263 Days
• Field of Search: 702/185, 702/189, 702/181, 702/179, 702/187, 703/1, 703/2, 434/128, 434247-249
• US Class Current: 702/185
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04

Abstract

A method and system for approximating a value functions for cooperative games. The method and system include approximating value functions for large cooperative games. The method and the system may be applicable to other types of value function problems such as those found in engineering, finance and other disciplines.

Claims

1. A method for approximating a value function for players in a cooperative game based on a large number of players representing an allocation problem, comprising:

selecting a measure of precision;

determining a desired precision for approximated player values;

selecting a collection of orderings from a set of possible permutations of player orderings;

computing at least one intermediate value function based on coalitional worths generated for each selected ordering;

computing, periodically, a precision of approximations of values for players to determine if more player orderings should be generated to obtain a more precise estimate of values for players;

computing a final value approximation for determining allocations to players when a desired degree of precision is reached or a selected computational limit is exceeded; and

outputting said final value approximation to a display or a computer module for further processing.

2. The method of claim 1 further comprising a computer readable medium having storing therein instructions for causing a processor to execute the steps of the method.

3. The method of claim 1 wherein:

a collection of player orderings is randomly generated with all players having equal probability of appearing at any position in an ordering;

an intermediate value function generated based on each player ordering is the marginal contribution of each player;

or

at least one player'"'"'s average marginal contribution is determined, or

allocations to players are based on average marginal contributions.

4. The method of claim 1 wherein:

an approximation of a weighted value is computed;

a collection of player orderings is randomly generated with a probability of a player appearing at a particular point in an ordering proportional to a ratio of its weight to a sum of weights of players not already ordered;

an intermediate value function generated based on each player ordering is a marginal contribution of each player;

at least one player'"'"'s average marginal contribution is determined;

or

at least one player'"'"'s value is based on its average marginal contribution.

5. The method of claim 1 wherein:

an approximation of a powerpoint is computed.

6. The method of claim 1 wherein:

a standard error is a selected measure of precision; and

squared values of intermediate value functions used to compute estimated values are also computed and the estimated values squared or their sums are saved, or

sums of squared intermediate value functions and sums of intermediate value functions are used to compute sample standard errors of estimated values for players.

7. A method for approximating the proportional value for players in a cooperative game based on a large number of players comprising:

selecting a collection of orderings from a set of possible permutations of player orderings;

computing weighted marginal contributions for at least one ordering of players and one player in that ordering;

determining allocations to players in the cooperative game; and

outputting said allocations to a display or a computer module for further processing.

8. The method of claim 7 further comprising a computer readable medium having stored therein instructions for causing a processor to execute the steps of the method.

9. The method of claim 7 wherein the computing step includes computing weighted marginal contributions WM_i^r(v) for each player i and ordering r in the cooperative game v with:

${\mathrm{WM}}_i^r<br><br>\left(v\right)=\frac{M_i^r<br><br>\left(v\right)}{\mathrm{OWP}<br><br>\left(r,v\right)},$

wherein the weighted marginal contributions WM_i^r(v) are intermediate value functions used to approximate a proportional value, M_i^r(v) are marginal contributions for each ordering r and OWP(r, v) is an Ordered Worth Product for an ordering r in the cooperative game v.

10. The method of claim 7 wherein the determining step includes:

determining a summation of weighted marginal contributions SWM_i(v) for a player i in a cooperative game v with;

${\mathrm{SWM}}_i<br><br>\left(v\right)=\underset{r<br><br><br><br>\mathrm{\epsilon <br><br>}<br><br><br><br>R^{*}<br><br>\left(N\right)}{\sum <br><br>}<br><br>{\mathrm{WM}}_i^r<br><br>\left(v\right),$

wherein the summation is over all orderings r in a selected collection of orderings R*(N) and WM_i^r(v) are weighted marginal contributions for player i and ordering r.

11. The method of claim 7 wherein the determining step includes:

determining an estimated proportional value EstPV_i of a player i in a cooperative game v including N players with;

${\mathrm{EstPV}}_i<br><br>\left(v\right)=\frac{{\mathrm{SWM}}_i<br><br>\left(v\right)}{\underset{\mathrm{j\epsilon <br><br>}<br><br><br><br>N}{\sum <br><br>}<br><br><br><br>{\mathrm{SWM}}_j<br><br>\left(v\right)}<br><br>v<br><br>\left(N\right),$

wherein EstPV_i is a proportional share of a worth of a grand coalition according to weighted marginal contributions SWM_i(v) and a summation of weighted marginal contributions SWM_j(v) for an ordering j.

12. The method of claim 11 wherein the control game and allocation game have a same set of players and one collection of player orderings is used for both the control game and allocation game.