Time polynomial arrow-debreu market equilibrium

• US 7,668,728 B2
• Filed: 04/29/2005
• Issued: 02/23/2010
• Est. Priority Date: 11/19/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jain, Kamal
• Primary Examiner(s): Hayes; John W
• Assistant Examiner(s): Erb; Nathan
• Application Number:
  US11/119,362
• Publication Number:
  US 20060111951A1
• Time in Patent Office: 1,761 Days
• Field of Search: 705/1
• US Class Current: 705/1.1
• 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-Debreu theory.

Claims

1. A tangible computer-readable storage medium for deriving a combinatorial characterization of an equilibrium in an exchange arena, wherein first and second participants in the exchange, each participant has a utility function representing consumption of goods, the money and goods are exchange, and an allocation of a gamut of resources at the equilibrium maximizes a mathematical product of the utility functions, the tangible computer-readable storage medium storing computer-executable instructions for causing a computer to perform the steps comprising:

selecting a first test point in a convex set, wherein each point in the convex set describes a respective allocation of resources and the first test point has an associated Eisenberg-Gale objective function, and wherein the derivative of the Eisenberg-Gale objective function at the first test point is positive;

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

on a line from the first test point to the second test point, calculating the 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 indicating the allocation of resources represented by the second test point; and

if the derivative equals zero somewhere on the line from the first test point to the second test point, thereby representing the equilibrium, then indicating the allocation of resources represented by the point on the line from the first test point to the second test point where the derivative equals zero;

wherein the Eisenberg-Gale objective function is represented as;

$\underset{i}{\sum <br><br>}<br><br>m_i<br><br>\log \left(\underset{j}{\sum <br><br>}<br><br>u_{\mathrm{ij}}<br><br>\left(x_{\mathrm{ij}}+\mathrm{\varepsilon <br><br>}<br><br><br><br>z_{\mathrm{ij}}\right)\right)$

 

wherein i represents the i^th participant;

j represents the j^th good;

m_j represents the initial amounts of money of the i participants;

u_ij represents the utility functions of the i participants with respect to the j goods; and

z_ij represents (x_ij′

−

x_ij) where x_ij′

represents an assignment in equilibrium of good j with respect to participant i, and x_ij represents an assignment not in equilibrium of good j with respect to participant i;

such that goods are transferred from the first participant to the second participant, at least some goods are transferred from the second participant to the first participant in exchange, and ∈

represents a positive constant.

2. The tangible computer-readable storage medium as recited in claim 1, wherein the exchange arena comprises a goods market, and the equilibrium is represented by a Fisher model.

3. The tangible computer-readable storage medium 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 equilibrium corresponds to an equilibrium allocation of the resources across a spectrum of users originating the digital data.

4. 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; and

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

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

comparing the current requests to the data; and

allocating the resources with respect to the current requests according to a combinatorial characterization of an equilibrium in the exchange arena, wherein the combinatorial 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 a plurality of assignments, wherein the first test point has an associated Eisenberg-Gale objective function, and wherein the derivative of the Eisenberg-Gale objective function at the first test point is positive;

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

testing the derivative of the Eisenberg-Gale objective function at the first test point to determine when the derivative is positive along a line from the first test point to the second point;

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

if the derivative for at least one point along a length of the line from the first test point to the second point is not positive, then finding a third point along the line from the first test point to the second point at which the derivative has a value of zero, representing the equilibrium, and indicating the assignment represented by the third point;

wherein the Eisenberg-Gale objective function is represented as;

$\underset{i}{\sum <br><br>}<br><br>m_i<br><br>\log \left(\underset{j}{\sum <br><br>}<br><br>u_{\mathrm{ij}}<br><br>\left(x_{\mathrm{ij}}+\mathrm{\varepsilon <br><br>}<br><br><br><br>z_{\mathrm{ij}}\right)\right)$

 

wherein i represents the i^th user;

j represents the j^th good;

m_j represents the initial amounts of money of the i users;

u_ij represents the utility functions of the i users with respect to the j goods; and

z_ij represents (x_ij′

−

x_ij) where x_ij′

represents an assignment in equilibrium of good j with respect to user i, and x_ij represents an assignment not in equilibrium of good j with respect to user i;

such that ∈

represents a positive constant.

5. The apparatus of claim 4, 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.

6. The apparatus of claim 4, wherein the users provide requests to store data of different data sizes in some particular memory, and the resources comprise memory resources.

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

8. The apparatus of claim 4, 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.