COMBINATORIAL AND QUANTITY DISCOUNT PROCUREMENT AUCTIONS PROVIDE BENEFITS TO MARS , INCORPORATED AND TO ITS SUPPLIERS

Gail Hohner, John Rich, Ed Nag
Mars, Incorporated, Winnerish Triangle, U.K
.
Grant Reid
Mars, Incorporated , Mclean VA

Andrew J. Daven Port, Jayant R.Kalagnanam, Ho Soo Lee, and Chae An
IBM T.J. Watson Research Center, Yorktown Heights, NY

The Mars-IBM team developed a website called www.Number1Traders.com which is basically a procurement auction web site which supports alternatives to simple auctions that help match its needs as procurer and the capabilities of suppliers by incorporating optimal bid selection subject to constraints based on business rules in a dynamic environment.

Goal: The goal of the project was to enable Mars buyers worldwide to run auctions whose design complimented the overall business strategy. The objective was to support strategic purcheses like
  • small and fairly static supply pools
  • long-term relationships
  • significant-business integration

    The paper then gives an introduction about the volume discount auctions and combinatorial auctions, quotes the business rules(constarints) like the limit on number of winning suppliers, maximum amount to be procured from each supplier.
    The paper says that multi-round auctions provide the following advantage :
  • induces competition among suppliers
  • allows suppliers to correct their bids using information leaned during the process and
  • it elicits bids incrementally so that the suppliers do not have to specify all their preferences
    As part of the project, the team developed the bid evaluation engine as an independent optimization module in C++ and then integrated it into auction platform. The engine uses IBM's optimization subroutine library (OSL) as the LP / IP solver. The implementation of this framework isdone using IBM's ecommerce platform - Websphere commerce Suite 4.1 which provides the infrastructure support for the Number1Traders website
    In a multi-round auction, the non-winnig suppliers are provided feed back on clearing price and thereby the suppliers are given a chance to reformulate their bids .
    Combinatorial Auctions The computational complexity of winner determination problem is a NP-hard optimization problem.
    The rule is framed in a multi-round combinatorial auction that the decrement in bid-price should be atleast delta in each round.
    Winner Determination for Volume Discount Auctions : The winner determination problem in this case has been modeled as a variation to the multiple-choice knapsack problem .

    Desirable Properties for the Auction Design

  • Fairness: Auctions should be fair enough that the bidders should be intrested in participating in it .
  • Optimality : Making an approximate solution using heuristics is unfair in winner determination. So, the optimization module should propse a real soultion. The solver developed by the team provided optimal solution within two minutes response time.

    Time Stamps :
    So as to ensure that the bids which are old are selected when there occurs a price match, time stamps have been put up for each bid. Now, the solver has 2 problems with it. One is to determine the winner bids which an optimization problem and the second is to choose bids in such a way to minimize the time stamps which is another optimization problem which may take more time than the first one .

    Some of the advantages or favours to the suppliers were :
  • Transperency : The suppliers price were compared with other suppliers prices in auction rather than negotiation .
  • Time efficient : The system was good and that the time taken was very less for evaluation.
  • Fairness : Suppliers view these auctions as more equitable than any other mechanisms.