Time polynomial arrow-debreu market equilibrium

• US 20060111951A1
• Filed: 04/29/2005
• Published: 05/25/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,668,728 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 method for deriving a combinatorial characterization of an equilibrium in an exchange arena in order to establish a price at which a good can be sold, wherein first and second participants in the exchange arena each have an initial amount of money and goods to exchange, each participant has a utility function representing consumption of goods, the money and goods are exchanged, and an assignment of the price to the good at the equilibrium maximizes a mathematical product of the utility functions, the method comprising:

selecting a first test point in a convex set, wherein each point in the convex set describes a price assignment and the first test point has an associated Eisenberg-Gale objective function;

selecting a second test point in the convex set, wherein the second test point represents a price assignment associated with a transfer of all of the first participant'"'"'s goods to the second participant;

on a line between the first test point and the second test point, calculating a derivative of the Eisenberg-Gale objective function from the first test point in the direction of the second test point, wherein the derivative is positive at the first test point;

if the derivative remains positive along the line from the first test point to the second test point, then selecting the assignment of price represented by the second test point; and

if the derivative equals zero somewhere on the line thereby representing an equilibrium, then selecting the assignment of price represented by the point on the line where the derivative equals zero.

2. The method as recited in claim 1, wherein the Eisenberg-Gale objective function is represented as:

3. The method as recited in claim 1, wherein the exchange arena comprises a goods market and the equilibria are represented by a Fisher model.

4. The method as recited in claim 1, wherein the exchange arena represents a data network for transferring digital data of varying sizes via a transmission system that possesses finite resources, and the equilibria correspond to an equilibrium allocation of the resources across a spectrum of users originating the digital data.

5. An apparatus for allocating a gamut of resources across a spectrum of users in an exchange arena, wherein the users each have an initial amount of money and goods to exchange, each user has a utility function representing consumption of goods, and the money and goods are exchanged, comprising:

at least one processor;

a memory coupled to the processor, wherein the memory stores data representing the resources and multiple needs of the spectrum of users and the memory further includes computer-readable instructions capable of causing the processor to perform;

estimating current requests from the spectrum of users for the resources;

comparing the current requests to the data; and

allocating the resources with respect to the requests according to a combinatorial characterization of equilibria in the exchange arena, wherein the characterization determines when an assignment of the resources between the users provides, in response to allocating the resources, an increase in a product of utility functions associated respectively with the users, wherein the allocating includes;

selecting a first test point in a convex set describing assignments, wherein the first test point has an associated Eisenberg-Gale objective function;

locating a second point in the convex set, wherein the second point represents the exchange of all the money and goods between the users;

testing a derivative of the objective function at the first test point to determine when the derivative is positive along a line between the first test point and the second point;

if the derivative remains positive along the line from the first test point to the second point, then selecting the assignment represented by the second test point; and

if the derivative is not positive for at least one point along a length of the line, then finding a zero point along the line at which the derivative has a value of zero representing an equilibrium and selecting the assignment represented by the zero point.

6. The apparatus of claim 5, wherein the users provide requests to transfer digital data of different data sizes via a data transfer network and the resources comprise data transfer capabilities.

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

8. The apparatus of claim 5, wherein the users provide requests to transmit information of different sizes via an information system, and the resources comprise information system descriptors.

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

bandwidth;

capacity, load, or throughput.

10. A method for deriving a non-convex combinatorial characterization of an equilibrium in an exchange arena of n participants in order to establish a price at which a good can be sold, wherein a first participant i and second participant j in the exchange arena each have an initial amount of money and goods x to exchange, each participant has a utility function u representing consumption of goods x, the money and goods x are exchanged, and an assignment of the price to the good at the equilibrium maximizes a mathematical product of the utility functions, the method comprising:

constructing a directed graph with n participants as a set of vertices, including vertices for the first participant i and the second participant j;

extending one or more edges from i to j when the goods x provide positive utility u;

assigning two types of weight w(ij) to each edge, wherein the first weight is denoted by

$w<br><br>\left(\mathrm{ij}\right)=\frac{\underset{k}{\sum <br><br>}<br><br>u_{\mathrm{ik}}=x_{\mathrm{ik}}}{u_{\mathrm{ij}}}$

and the second weight is denoted by LOGw(ij)=log(w(ij)), wherein the product that forms w_ij is at least one over any cycle of the directed graph and wherein the directed graph has no negative cycle with respect to the weight function LOGw(ij); and

selecting an assignment of the price based on at least one of the weights.

11. The method as recited in claim 10, wherein each utility function u comprises a concave utility function.

12. A method for deriving a combinatorial characterization of an equilibrium in an exchange arena of n participants in order to establish a price at which a good can be sold, wherein a first participant i and second participant j in the exchange arena each have an initial amount of money and goods x to exchange, each participant has a utility function u representing consumption of goods x, the money and goods x are exchanged, and an assignment of the price to the good at the equilibrium maximizes a mathematical product of the utility functions, the method comprising:

finding a solution to a convex program;

$\forall <br><br>j<br><br>\text{;<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{i}{\sum <br><br>}<br><br>x_{\mathrm{ij}}=1$$\forall <br><br>i,j<br><br>\text{;<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_{\mathrm{ij}}\ge <br><br>0$$\mathrm{and}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{every}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{cycle},C,\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>G<br><br>\text{;<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{\mathrm{ij}\in <br><br>C}{\prod <br><br>}<br><br>w<br><br>\left(\mathrm{ij}\right)\ge <br><br>1$

including;

constructing a directed graph G with n participants as a set of vertices, including vertices for the first participant i and the second participant j;

extending one or more edges from i to j when the goods x provide positive utility u;

assigning a weight w(ij) to each edge, wherein the weight is denoted by

$w<br><br>\left(\mathrm{ij}\right)=\frac{\underset{k}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>u_{\mathrm{ik}}<br><br>x_{\mathrm{ik}}}{u_{\mathrm{ij}}}$

wherein the product that forms w_ij is at least one over any cycle of the directed graph and wherein the directed graph has no negative cycle with respect to the weight function w(ij).

13. The method as recited in claim 12, wherein the convex program is solved using a separation oracle.

14. The method as recited in claim 12, wherein the convex program is represented by: