SEQUENCE OF ALGORITHMS TO COMPUTE EQUILIBRIUM PRICES IN NETWORKS

• US 20080103793A1
• Filed: 05/29/2007
• Published: 05/01/2008
• 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
• Granted Patent: US 8,244,562 B2
• Time in Patent Office: Days
• US Class Current: 705/1
• 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:

an analysis component 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 that employs a combinatorial algorithm to determine an equilibrium solution for the set of edges.

2. The system of claim 1, the combinatorial algorithm is a strongly polynomial combinatorial algorithm.

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

4. The system of claim 1, the equilibrium solution is an optimal solution to a convex program.

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

6. 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.

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

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

9. The system of claim 6, the budget component modifies the price by a predetermined amount.

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

11. The system of claim 10, the budget component modifies the price for the plurality of edges simultaneously.

12. 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.

13. The system of claim 12, the supply is bandwidth supply for the edge and the demand is demand utilization for the edge.

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

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

16. 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 a strongly polynomial combinatorial algorithm for determining an equilibrium solution for the set of edges.

17. The method of claim 16, 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.

18. The method of claim 16, 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.

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

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

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

computer-implemented means for employing a strongly polynomial combinatorial algorithm for determining an equilibrium solution for the set of edges.