Share with your friends










Submit

Analytics Magazine

Combinatorial Auctions: No Such Thing As a Free Lunch?

Fall 2009

CLICK HERE TO GO TO THE DIGITAL VERSION OF THIS ARTICLE

Think again. Combinatorial auctions help feed two million public school children from low-income families in Chile.

By Jaime Catalán, Rafael Epstein, Mario Guajardo, Daniel Yung, Lysette Henriquez, Cristain Martinez and Gabriel Weintraub

JUNAEB provides meals for 2 million children in primary and secondary public schools.

JUNAEB provides meals for 2 million children in primary and secondary public schools.

Economists love to say that there is no such thing as a free lunch. But the Chilean government agency responsible for school grants, Junta Nacional de Auxilio Escolar y Becas (JUNAEB), is an exception to the rule. During the school year, JUNAEB provides breakfast and lunch for 2 million children in primary and secondary public schools. In a developing country where about 14 percent of children under the age of 18 live below the poverty line, many students depend on these free meals as a key source of nutrition.

In 1980, JUNAEB began assigning catering contracts to companies through competitive auctions. At first, only three companies submitted bids, but this number rose to 30 during the 1990s and remains close to that level today.

Given the volume of meals it procures, JUNAEB has always had significant bargaining power over vendors. However, until the late 1990s, JUNAEB awarded contracts based on subjective, and quite rudimentary, criteria, making it easier for bidders to exert inappropriate pressures on JUNAEB officials. Vendors lacked incentives to reduce costs and inefficiencies, and JUNAEB wound up paying a high price for low-quality products.

In 1997, JUNAEB’s board asked a team of academics from the University of Chile’s Department of Industrial Engineering to design and implement a new mechanism for auctioning its school meals service. The new model was implemented for the first time that year and has been used ever since. (We have updated and enhanced the model during this period.) In this article, we present the development and application of this new mechanism, which assigns bids in a single-round, sealed-bid combinatorial auction and is based on an integer linear programming model.

The use of an optimization model in the bidding process to award school meal contracts in Chile has yielded significant social benefits.

The use of an optimization model in the bidding process to award school meal contracts in Chile has yielded significant social benefits.

The New Auction Process

FOR THE PURPOSES OF the auction, Chile is divided into approximately 120 school districts or territorial units (TUs). JUNAEB holds auctions for school catering services in one-third of these districts every year, awarding three-year contracts. The auction process begins when JUNAEB contacts and registers potential vendors. The agency then evaluates the companies from a managerial, technical and financial point of view, and eliminates those that don’t meet minimum reliability standards. Qualifying vendors are classified according to two characteristics: their financial and operating capacity, and their technical and managerial competence.

After the companies are classified, JUNAEB publishes a call to tender with the rules for bidding. Potential vendors submit their bids through an online system. Each bid includes a technical project for meal service and its price. The technical project must meet regulations established by JUNAEB, such as nutritional and hygiene requirements. In this way, meal plans are standardized.

Vendors that satisfy these conditions remain in the bidding process and compete on price, through their respective bids. A bid can cover anywhere from one to 12 TUs, depending on the vendor’s classification. Vendors can submit as many bids as they want; each bid is accepted or rejected in its entirety. When JUNAEB accepts a company’s bid, the company must provide all meal services in the corresponding TUs.

Because JUNAEB allows companies to submit bids that cover multiple TUs, vendors can take advantage of economies of scale. The shared use of infrastructure in neighboring regions, volume discounts and efficiencies in transportation and staffing all contribute to the economies of scale. Firms generally submit many bids, ranging from bids that cover just one TU to those that cover a package of TUs. The ability to submit bids on various groupings of TUs defines the combinatorial character of this auction — and makes identifying the optimal solution much more difficult.

Each bid includes prices for the various catering services that JUNAEB provides in the corresponding TUs. Furthermore, JUNAEB asks companies to quote alternatives to these services, such as improvements to the nutritional quality of the meals. Vendors also quote prices for different levels of demand, thereby reducing the risk the vendors would face if they provide fewer meals because of unforeseen events, such as teacher strikes. Firms can also offer discounts if the

real demand turns out to be higher than anticipated.

In recent years, combinatorial auctions have received a lot of attention from both the academic and industrial worlds. Combinatorial auctions have clear advantages when the auctioned items have a higher value as a set than as separate parts. Other successful applications of these auction applications have been documented [1, 2, 3, 4].

The new model saved the government $40 million a year, or the cost of feeding 300,000 children.

The new model saved the government $40 million a year, or the cost of feeding 300,000 children.

The Assignment Model and Its Solution

The new model’s objective is to select a combination of bids that supply all of the TUs at a minimum cost. The performance of vendors based on JUNAEB’s evaluations, or their quality index, is also a factor in awarding contracts. Other constraints include:

  • Limits on the number of vendors supplying a region. Having too few vendors increases the risk of supply interruptions, while having too many can make management more difficult.
  • A maximum award per vendor, calculated as a function of other contracts held by the vendor, its quality index and its financial and operating capacity.
  • Minimum prices. A phenomenon known as “winner’s curse” occurs when the firm that bid the lowest price is found to have underestimated its costs, raising the possibility of losses or even financial ruin [5]. To avoid this, unrealistically low bids are eliminated.

Furthermore, we consider various scenarios such as different food structures and demand levels. By combining all of the possible variations, we generated more than 700 scenarios for analysis. In practice, the decision-maker will be interested in evaluating no more than 200 of them.

To find the optimal assignment for each scenario, we formulated the problem as an integer linear programming model. We defined a binary decision variable for each bid, where the decision is either to accept the bid or reject it. We also defined auxiliary binary variables that correspond to the restrictions limiting the number of firms in each region and the number of firms in the winning assignment.

Not surprisingly, the difficulty of solving combinatorial bidding models is one of the main impediments to their broader use. Solving our model can be a challenging task, indeed, since it contains three classical combinatorial structures, each NP-hard: a set-covering problem, a multiknapsack problem and uncapacitated facility location problem. A real instance of the problem contains about 90,000 binary variables. In addition, considering the high number of scenarios to be evaluated, we had to design an efficient solving strategy. (Additional technical details can be found in [6, 7].)

We found optimal solutions by solving the different scenarios of the model, and the JUNAEB Contract Award Commission was able to evaluate these scenarios along with the quality and robustness of their solutions. For example, the model allows JUNAEB to analyze the performance of the optimal solution when the demand level is at 100 percent, and compare this to the performance when demand is at 80 percent.

It is important to note that the commission selects the scenario to be considered for the award, but the optimization model provides the specific solution. The entire process ¬ including data processing, administrative tasks, legal procedures and analysis of scenarios ¬ is usually completed in no more than 10 days.

In developing countries, state-run social programs like school meals often account for the bulk of the national budget.

In developing countries, state-run social programs like school meals often account for the bulk of the national budget.

Results and Conclusions

The use of an optimization model in the bidding process to award school meal contracts in Chile, along with other managerial advances at JUNAEB, has yielded significant social benefits. For example, we compared the 1999 auction (which used the new model) and the 1995 auction (carried out under the old process) and found substantial improvements in the nutritional quality of the meals, the infrastructure of the meals service and the labor conditions of the food handlers. Although these improvements increased total costs by 24 percent (in real terms), the average price of a meal rose by only 0.76 percent. In all, the new model saved the government about $40 million a year, or the cost of feeding 300,000 children.

Using mathematical modeling to assign contracts allowed JUNAEB to reap significant savings for the following reasons:

  1. The new process is objective and transparent, providing few opportunities for vendors to pressure on decision makers.
  2. The process is impartial and reliable. It forces companies to compete and to increase productivity. Participating vendors have improved their management, enhanced the quality of their service and cut their prices, and they still manage to make profits. In fact, a survey by JUNAEB compared the companies’ average profit on sales before and after the model was introduced. The results showed profits increased from 3.2 percent to 4.9 percent. Average return on equity also rose, climbing from 28 percent to 38 percent, reflecting the vendors’ higher rate of investment.
  3. By allowing companies to make bids that cover multiple TUs, vendors can take advantage of economies of scale.
  4. In every scenario, JUNAEB is able to get the lowest-cost bid combination that meets all of its restrictions. This would be nearly impossible to accomplish manually. Would the agency attempt to do so, and make an assignment that is just 2 percent more costly than the optimal solution, it would overspend by $10 million, — the equivalent of providing food to 40,000 children.

The clearest evidence of the model’s success is its continued use. JUNAEB introduced the model in 1997 and has applied it ever since. To date, the Chilean government has awarded more than $2 billion of contracts using the combinatorial auction methodology. Over the years, we have enhanced the model’s outputs and improved the comparison among different scenarios. In 2002, this work received the IFORS Prize for Operational Research in Development, awarded by the International Federation of Operational Research Societies to the best application of O.R. in developing countries.

Recently, we developed new procedures to solve the multiple auction scenarios, reducing solution times significantly [7]. We are currently studying the empirical behavior of bidders, so that we can better understand their cost structures and economies of scale, and thereby improve the auction design. Overall, the project has generated a stimulating and challenging research agenda on both algorithmical issues and auction design.

In developing countries, state-run social programs often account for the bulk of the national budget. The success of this case shows that sophisticated decision-making tools can help. Small changes in these programs can lead to enormous savings, and these savings can lead to tangible improvements in quality of life, such as meals for school children. Perhaps operational research tools can continue to uncover free lunches where they are needed the most.


Rafael Epstein (repstein@dii.uchile.cl) is an associate professor in the Department of Industrial Engineering, University of Chile, where Jaime Catalán (jcatalan@dii.uchile.cl), Mario Guajardo (maguajar@dii.uchile.cl) and Daniel Yung (dyung@dii.uchile.cl) are research assistants. Gabriel Weintraub (gyw2105@columbia.edu) is an assistant professor of decision, risk and operations at Columbia Business School. Lysette Henriquez (lysetteh@dii.uchile.cl) is former Director of JUNAEB. Cristian Martínez (cristian.martinez@mineduc.cl) is Vice-Minister of Education, Chile.

References

1. Hohner G., Rich, J., Ng, E., Reid, G., Davenport, A.J., Kalagnanam, J.R., Lee, H.S., An, C., 2003, “Combinatorial and Quantity-Discount Procurement Auctions Benefit Mars, Incorporated and Its Suppliers,” Interfaces, Vol. 33, Vol. 1, pp. 23-35.

2. Sheffi, Y., 2004, “Combinatorial Auctions in the Procurement of Transportation Services,” Interfaces, Vol. 34, No. 4, pp. 245-252.

3. Metty, T., Harlan, R., Samelson, Q., Moore, T., Morris, T., Sorensen, R., Schneur A., Raskina O., Schneur R., Kanner, J., Potts K., Robbins, J., 2005, “Reinventing the Supplier Negotiation Process at Motorola,” Interfaces, Vol. 35, No. 1, pp. 7-23.

4. Sandholm, T., Levine, D., Concordia, M., Martyn, P., Hughes, R., Jacobs, J., Begg, D., 2006, “Changing the Game in Strategic Sourcing at Procter & Gamble: Expressive Competition Enabled by Optimization,” Interfaces, Vol. 36, No. 1, pp. 55-68.

5. Milgrom, P., 1989, “Auctions and Bidding: A Primer,” The Journal of Economic Perspectives, Vol. 3, No. 3, pp. 3-22.

6. Epstein, R., Henríquez, L., Catalan, J., Weintraub, G., Martínez, C. A., 2002, “Combinatorial Auction Improves School Meals in Chile,” Interfaces, Vol. 32, No. 6, pp. 1-14.

7. Catalan, J., Epstein, R., Guajardo, M., Yung, D., Martínez, C., 2006, “Solving multiple scenarios in a combinatorial auction,” accepted for publication in Computers and Operations Research.

CLICK HERE TO GO TO THE DIGITAL VERSION OF THIS ARTICLE

Analytics Blog

Electoral College put to the math test


With the campaign two months behind us and the inauguration of Donald Trump two days away, isn’t it time to put the 2016 U.S. presidential election to bed and focus on issues that have yet to be decided? Of course not.

Headlines

Stereotypes hold back girls’ interest in STEM subjects

New research from Accenture reveals that young people in the United Kingdom and Ireland are most likely to associate a career in science and technology with “doing research” (52 percent), “working in a laboratory” (47 percent) and “wearing a white coat” (33 percent). The study found that girls are more likely to make these stereotypical associations than boys. Read more →

Gartner: Connected ‘things’ will jump 31 percent in 2017

Gartner, Inc. forecasts that 8.4 billion connected things will be in use worldwide in 2017, up 31 percent from 2016, and will reach 20.4 billion by 2020. Total spending on endpoints and services will reach almost $2 trillion in 2017. Regionally, China, North America and Western Europe are driving the use of connected things, and the three regions together will represent 67 percent of the overall Internet of Things (IoT) installed base in 2017. Read more →

U.S. News: Analytics jobs rank among the best

When it comes to the best business jobs, analytics- and operations research-oriented disciplines dominate the list, according to U.S. News & World Report’s rankings of the “2017 Best Jobs.” In order, the top five “best business jobs” listings include: 1. statistician
, 2. mathematician
, 3. financial advisor, 
4. actuary, and 
5. operations research analyst. Read more →

UPCOMING ANALYTICS EVENTS

INFORMS-SPONSORED EVENTS

CONFERENCES

2017 INFORMS Business Analytics Conference
April 2-4, 2017, Las Vegas

2017 INFORMS Healthcare Conference
July 26-28, 2017, Rotterdam, the Netherlands

CAP® EXAM SCHEDULE

CAP® Exam computer-based testing sites are available in 700 locations worldwide. Take the exam close to home and on your schedule:


 
For more information, go to 
https://www.certifiedanalytics.org.