Sequence of algorithms to compute equilibrium prices in networks

• US 8,244,562 B2
• Filed: 05/29/2007
• Issued: 08/14/2012
• Est. Priority Date: 10/27/2006
• Status: Active Grant

• Current Assignee: Spansion LLC (Infineon Technologies AG), Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jain, Kamal, Vazirani, Vijay
• Primary Examiner(s): Nguyen, Nga B.
• Application Number:
  US11/754,877
• Publication Number:
  US 20080103793A1
• Time in Patent Office: 1,904 Days
• Field of Search: 705/7, 705/10, 705/37
• US Class Current: 705/7
• CPC Class Codes: G06Q 30/0206 Price or cost determination based on market factors
• CPC Class Codes: H03L 3/00 Starting of generators
• CPC Class Codes: H03L 7/0995 the oscillator comprising a ring oscillator

Abstract

The claimed subject matter provides an architecture for facilitating equilibrium solutions for resource allocation markets. One particular example of such markets can be a computer network environment. The architecture can model buyers as nodes and suppliers as edges, incorporating notions of an ascending price auction in order to provide optimal equilibrium solution to Eisenberg-Gale type convex programs in strongly polynomial time.

Claims

1. A computer-implemented system that facilitates equilibrium for a natural resource allocation market, comprising:

a memory;

one or more processors operatively coupled to the memory and disposed within one or more devices;

an analysis component disposed within one of the one or more devices that ascertains at least one of a supply or a demand for a set of edges in a natural resource allocation market; and

a solutions component disposed within one of the one or more devices that employs a strongly polynomial combinatorial algorithm to determine an equilibrium solution to a convex program for the set of edges based in part on relaxing complementary slackness conditions.

2. The system of claim 1, the combinatorial algorithm converges to the equilibrium solution in strongly polynomial time.

3. The system of claim 1, the convex program is substantially similar to an Eisenberg-Gale program.

4. The system of claim 1, further comprising a budget component that modifies a price associated with utilization of an edge from the set of edges.

5. The system of claim 4, the budget component raises the price when the demand is greater than the supply for the edge.

6. The system of claim 4, the budget component lowers the price when the demand is less than the supply.

7. The system of claim 4, the budget component modifies the price by a predetermined amount.

8. The system of claim 4, the budget component modifies the price for a plurality of edges by a uniform amount.

9. The system of claim 8, the budget component modifies the price for the plurality of edges simultaneously.

10. The system of claim 1, the natural resource allocation market is a computer network environment and an edge from the set of edges is a network path between a first and a second network participant or agent.

11. The system of claim 10, the supply is bandwidth supply for the edge and the demand is demand utilization for the edge.

12. The system of claim 10, the solutions component determines the equilibrium solution for a point-to-point topology.

13. The system of claim 10, the solutions component determines the equilibrium solution for a broadcast topology.

14. A computer-implemented method for facilitating equilibrium for a natural resource allocation market, comprising:

monitoring at least one of a supply or a demand for a set of edges in a natural resource allocation market; and

employing, by a processor, a strongly polynomial combinatorial algorithm for determining an equilibrium solution to a convex program for the set of edges based in part on relaxing complementary slackness conditions.

15. The method of claim 14, further comprising at least one of the following acts:

adjusting a cost for utilization of an edge from the set of edges;

increasing the cost when the supply is less than the demand;

decreasing the cost when the supply is greater than the demand;

adjusting the cost of utilization for a plurality of edges from the set of edges simultaneously;

or

adjusting the cost of utilization for a plurality of edges from the set of edges uniformly.

16. The method of claim 14, further comprising at least one of the following acts:

modeling as a node at least one of a natural resource allocation market agent or participant;

modeling as an edge a supplier of a resource;

or

approaching the equilibrium solution as an ascending price auction.

17. The method of claim 14, the natural resource allocation market is a computer network environment.

18. One or more computer-readable storage devices encoded with instructions, that when executed by at least one processor, implement acts comprising:

examining at least one of a supply or demand for a set of edges in a natural resource allocation market; and

employing a strongly polynomial combinatorial algorithm for determining an equilibrium solution to a convex program for the set of edges based in part on relaxing complementary slackness conditions.