Time polynomial arrow-debreu market equilibrium

• US 20060116917A1
• Filed: 11/19/2004
• Published: 06/01/2006
• Est. Priority Date: 11/19/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jain, Kamal
• Granted Patent: US 7,584,111 B2
• Time in Patent Office: Days
• US Class Current: 705/7
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: G06Q 30/0204 Market segmentation
• CPC Class Codes: G06Q 30/0206 Price or cost determination based on market factors

Abstract

A concept for providing a process and apparatus for allocating a gamut of assets/resources across a spectrum of consumers is described. The concept includes an apparatus for allocating resources across a spectrum of users. The apparatus includes one or more processors and a memory coupled to the one or more processors. The memory is configured to store data representative of characteristics and capabilities of the resources and describing needs of the spectrum. The memory further includes computer readable code configured to cause the one or more processors to perform acts of: estimating current requests from the spectrum for the resources; comparing the current requests to the capabilities and characteristics; and allocating the resources with respect to the requests in conformance with a convex program implementation of Arrow-Debrue theory.

Claims

1. A process for promoting market liquidity, comprising:

determining a spectrum of participants in a market, the spectrum comprising consumers of goods of a particular type;

defining a gamut of goods of the particular type;

including ranges of value units over which respective products related to the gamut command; and

invoking a convex program to determine a particular number of value units for a specific product related to the gamut, at which a market in which the spectrum participates will clear.

2. The process of claim 1, wherein the convex program instantiates Arrow-Debrue theory.

3. The process of claim 1, wherein the convex program treats linear utility functions.

4. The process of claim 1, wherein the convex program treats non-linear utility functions.

5. The process of claim 1, wherein the convex program is represented by:

Λ

j;

Σ

_ix_ij=1
Λ

i,j;

x_ij≧

0;


Λ

i,j such that u_ij>

0;

${\mathrm{LOGp}}_i-{\mathrm{LOGp}}_j\le <br><br>\log \left(\frac{\underset{k}{\sum <br><br>}<br><br>u_{\mathrm{ik}}<br><br>x_{\mathrm{ik}}}{u_{\mathrm{ij}}}\right).$

6. The process of claim 1, wherein the convex program is represented by:

Λ

j;

Σ

_ix_ij=1
Λ

i,j;

m_iu_ij≦

p_jΣ

_ku_ikx_ik
Σ

_jp_j≦

Σ

_im_i
Λ

i,j;

x_ij≧

0
Λ

j;

p_j≧

0

7. An apparatus for allocating a gamut of resources across a spectrum of users, comprising:

one or more processors;

a memory coupled to the processor, the memory being configured to store data representative of the resources and needs of the spectrum, the memory further comprising computer-readable code configured to cause the one or more processors to perform acts of;

estimating current requests from the spectrum for the resources;

comparing the current requests to the data; and

allocating the resources with respect to the requests in conformance with a convex program implementation of Arrow-Debrue theory.

8. The apparatus of claim 7, wherein the convex program treats linear utility functions.

9. The apparatus of claim 7, wherein the convex program treats non-linear utility functions.

10. The apparatus of claim 7, wherein the convex program is represented by:

Λ

j;

Σ

_ix_ij=1
Λ

i,j;

x_ij≧

0
Λ

i,j such that u_ij>

0;

${\mathrm{LOGp}}_i-{\mathrm{LOGp}}_j\le <br><br>\log \left(\frac{\underset{k}{\sum <br><br>}<br><br>u_{\mathrm{ik}}<br><br>x_{\mathrm{ik}}}{u_{\mathrm{ij}}}\right).$

11. The apparatus of claim 7, wherein the convex program is represented by:

Λ

j;

Σ

_ix_ij=1
Λ

i,j;

m_iu_ij≦

p_jΣ

_ku_ikx_ik
Σ

_jp_j≦

Σ

_im_i
Λ

i,j;

x_ij≧

0
Λ

j;

p_j≧

0

12. The apparatus of claim 7, wherein the users provide requests to handle bodies of digital information of different sizes via a data-handling network, and the resources comprise data handling capabilities.

13. The apparatus of claim 7, wherein the users provide requests to store bodies of data of different sizes in a memory system, and the resources comprise memory resources.

14. The apparatus of claim 7, wherein the users provide requests to transmit bodies of information of different sizes via a data transmission system, and the resources comprise data transmission system descriptors.

15. The apparatus of claim 7, wherein the users provide requests to transmit bodies of information of different sizes via a data transmission system, each of the bodies represents one or more or digital representations of text, video, pictorial and audio data and the resources comprise data transmission system descriptors, including one or more of:

bandwidth;

capacity, loading and throughput.

16. A resource allocation engine, including in combination:

means for estimating current requests from a spectrum of participants for resources;

means for characterizing a gamut of resources that can be made available to the participants; and

means for allocating portions of the gamut across the spectrum using a convex program implementation of Arrow-Debrue theory.

17. The resource allocation engine of claim 16, wherein the convex program implementation employs linear utility functions.

18. The resource allocation engine of claim 16, wherein the convex program implementation employs non-linear utility functions.

19. The resource allocation engine of claim 16, wherein the convex program implementation is represented by:

Λ

j;

Σ

_ix_ij=1
Λ

i,j;

x_ij≦

0
Λ

i,j such that u_ij>

0;

${\mathrm{LOGp}}_i-{\mathrm{LOGp}}_j\le <br><br>\log \left(\frac{\underset{k}{\sum <br><br>}<br><br>u_{\mathrm{ik}}<br><br>x_{\mathrm{ik}}}{u_{\mathrm{ij}}}\right)$

20. The resource allocation engine of claim 16, wherein the convex program implementation is represented by:

Λ

j;

Σ

_ix_ij=1
Λ

i,j;

m_iu_ij≦

p_jΣ

_ku_ikx_ik
Σ

_jp_j≦

Σ

_im_i
Λ

i,j;

x_ij≦

0
Λ

j;

p_j≦

0

21. The resource allocation engine of claim 16, further comprising:

one or more processors;

a memory coupled to the one or more processors; and

computer-readable code accessible to the one or more processors, wherein the computer-readable code embodies one or more code modules, which, when executed by the one or more processors, cause the one or more processors to perform acts providing at least portions of functionalities of the means for estimating, the means for characterizing or the means for allocating.

22. An article of manufacture comprising computer-readable media having computer-readable code embodied therein, wherein the computer-readable code is configured to cause one or more processors to perform acts of:

determining a spectrum of participants in a market, the spectrum comprising consumers of goods of a particular type;

defining a gamut of goods of the particular type;

including ranges of value units over which respective products related to the gamut exchange command; and

invoking a convex program to determine a particular number of value units for a specific product related to the gamut, at which a market in which the spectrum participates will clear.

23. The article of manufacture of claim 22, wherein the convex program instantiates Arrow-Debrue theory.

24. The article of manufacture of claim 22, wherein the convex program treats linear utility functions.

25. The article of manufacture of claim 22, wherein the convex program treats non-linear utility functions.

26. The article of manufacture of claim 22, wherein the convex program is represented by:

Λ

j;

Σ

_ix_ij=1
Λ

i,j;

x_ij≦

0
Λ

i,j such that u_ij>

0;

${\mathrm{LOGp}}_i-{\mathrm{LOGp}}_j\le <br><br>\log \left(\frac{\underset{k}{\sum <br><br>}<br><br>u_{\mathrm{ik}}<br><br>x_{\mathrm{ik}}}{u_{\mathrm{ij}}}\right).$

27. The article of manufacture of claim 22, wherein the convex program is represented by:

Λ

j;

Σ

_ix_ij=1
Λ

i,j;

m_iu_ij≦

p_jΣ

_ku_ikx_ik
Σ

_jp_j≦

Σ

_im_i
Λ

i,j;

x_ij≧

0
Λ

j;

p_j≧

0