Method for computing payment discounts to achieve budget-balance in exchanges

1. A method for computing payment discounts awarded to a plurality of winning agents in an exchange, said method comprising:

computing, by a processor, a Vickrey discount to said plurality of winning agents in a cleared exchange as the difference between available surplus with all agents present minus available surplus without said plurality of winning agents, wherein the available surplus is a difference between an asked for payment from sellers and a bid payment from buyers, and wherein the winning agents are sellers and buyers matched to one another; and

computing, by the processor, said payment discounts by adjusting said Vickrey discounts so as to constrain said exchange to budget-balance, wherein said Vickrey discounts are equal to or less than the available surplus, and wherein said adjusting step further comprises:

minimizing a distance function under said budget-balance constraint and one or more bounding constraints, said distance function comprising a metric of the distance between said payment discounts and said Vickrey discounts;

deriving a parameterized payment rule for said distance function;

determining an allowable range of parameters so as to maintain budget-balance; and

selecting values for said parameters within said allowable range, wherein said values for said parameters are selected within said allowable range so as to reduce agent manipulation across said plurality of winning agents upon determining each agent's bidding strategy as a function of said parameters.

2. The method of claim 1 wherein said bounding constraints comprises a constraint that said payment discounts be non-negative.

3. The method of claim 1 wherein said bounding constraints comprises a constraint that said payment discounts not exceed said Vickrey discounts.

4. The method of claim 1 wherein said distance function is one of:

L 2 (Δ,Δ V )=(Σ l (Δ l V −Δ l ) 2 ) 1/2 ,

L ∞ (Δ,Δ V )=max l |Δ l V −Δ l |,

L RE (Δ,Δ V )=Σ l (Δ l V −Δ l )/Δ l V ,

L π (Δ,Δ V )=Π l Δ l V /Δ l ,

L RE2 (Δ,Δ V )=Σ l (Δ l V −Δ l ) 2 /Δ l V , and

L RE (Δ,Δ V )=Σ l Δ l V (Δ l V −Δ l ),

wherein Δ l V is said Vickrey discount for an agent l and Δ l is a new payment discount for the agent l.

5. The method of claim 4 , wherein said parameterized payment rule comprises:

a Threshold Rule max(0,Δ l V −C), C≧0 if said distance function is L 2 (Δ,Δ V ) or L ∞ (Δ,Δ V );

a Small Rule Δ l V if Δ l V ≦C, C≧0 if said distance function is L RE (Δ,Δ V );

a Reverse Rule min(Δ l V ,C), C≧0 if said distance function is L π (Δ,Δ V );

a Fractional Rule μΔ l V , 0≦μ≦1 if said distance function is L RE2 (Δ,Δ V ); and

a Large Rule Δ l V if Δ l V ≧C, C≧0 if said distance function is L RE (Δ,Δ V ),

wherein C is a given parameter.

6. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for computing payment discounts awarded to a plurality of winning agents in an exchange, said method steps comprising:

computing a Vickrey discount to said plurality of winning agents in a cleared exchange as the difference between available surplus with all agents present minus available surplus without said plurality of winning agents, wherein the available surplus is a difference between an asked for payment from sellers and a bid payment from buyers, and wherein the winning agents are sellers and buyers matched to one another; and

computing said payment discounts by adjusting said Vickrey discounts so as to constrain said exchange to budget-balance, wherein said Vickrey discounts are equal to or less than the available surplus, and wherein said adjusting step further comprises:

minimizing a distance function under said budget-balance constraint and one or more bounding constraints, said distance function comprising a metric of the distance between said payment discounts and said Vickrey discounts;

deriving a parameterized payment rule for said distance function;

determining an allowable range of parameters so as to maintain budget-balance; and

selecting values for said parameters within said allowable range, wherein said values for said parameters are selected within said allowable range so as to reduce agent manipulation across said plurality of winning agents upon determining each agent's bidding strategy as a function of said parameters.

7. The program storage device of claim 6 wherein said bounding constraints comprises a constraint that said payment discounts be non-negative.

8. The program storage device of claim 6 wherein said bounding constraints comprises a constraint that said payment discounts not exceed said Vickrey discounts.

9. The program storage device of claim 6 wherein said distance function is one of:

L 2 (Δ,Δ V )=(Σ l (Δ l V −Δ l ) 2 ) 1/2 ,

L ∞ (Δ,Δ V )=max l |Δ l V −Δ l |,

L RE (Δ,Δ V )=Σ l (Δ l V −Δ l )/Δ l V ,

L π (Δ,Δ V )=Π l Δ l V /Δ l ,

L RE2 (Δ,Δ V )=Σ l (Δ l V −Δ l ) 2 /Δ l V , and

L RE (Δ,Δ V )=Σ l Δ l V (Δ l V −Δ l ),

wherein Δ l V is said Vickrey discount for an agent l and Δ l is a new payment discount for the agent l.

10. The program storage device of claim 9 , wherein said parameterized payment rule comprises:

a Threshold Rule max(0,Δ l V −C), C≧0 if said distance function is L 2 (Δ,Δ V ) or L ∞ (Δ,Δ V );

a Small Rule Δ l V if Δ l V ≦C, C≧0 if said distance function is L RE (Δ,Δ V );

a Reverse Rule min(Δ l V ,C), C≧0 if said distance function is L π (Δ,Δ V );

a Fractional Rule μΔ l V , 0≦μ≧1 if said distance function is L RE2 (Δ,Δ V ); and

a Large Rule Δ l V if Δ l V ≧C, C≧0 if said distance function is L RE (Δ,Δ V ),

wherein C is a given parameter.

11. The method of claim 1 , wherein the computation of the Vickrey discount to said plurality of winning agents is performed after the exchange is cleared.

12. The program storage device of claim 6 , wherein the computation of the Vickrey discount to said plurality of winning agents is performed after the exchange is cleared.