HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program

Material from Talks

G. Anandalingam (Systems Engineering and The Wharton School University of Pennsylvania Philadelphia PA) and Neil J. Keon (Edwin L. Cox School of Business Southern Methodist University)

Pricing of Multiple Services in Telecommunications Networks With Quality of Service Guarantees

We consider pricing of multiple services offered over a single telecommunications network. Each service has quality of service (QoS) requirements that are guaranteed to users. Service classes may be defined by the type of service, such as voice, video or data, as well as the origin and destination of the connection provided to the user. We formulate the optimal pricing problem as a mathematical program. We solve for both prices and resource allocations necessary to provide connections with guaranteed QoS, to serve the demand resulting from the prices. We derive optimality conditions and a solution method for this class of problems.

John R. Birge (Dean, McCormick School of Engineering and Applied Science, Northwestern University)   jrbirge@northwestern.edu

Equilibria in Electric Power Exchange Auction Markets

Deregulated electric power markets have been increasingly transformed into auction clearing houses. We will describe the structure of these markets and the forms of equilibria that can exist. We will give characterizations of equilibria in simple stylized markets and illustrate conditions that produce apparent paradoxes such as declining prices during periods of high demand. We will also discuss some experience with the market in Colombia and the difficulties in using pure optimization procedures in predicting auction behavior or devising bidding strategies.

Brenda Dietrich (IBM T.J. Watson Research Center) and John Forrest

Column Generation Methods for Combinatorial Auctions

This paper discusses model formulations for solving combinatorial auctions using column generation techniques. We include the details of a solver developed for the FCC spectrum auction, formulations of other combinatorial auctions, and preliminary computational experience based on sample data for the FCC auction.

Brenda Dietrich (IBM T.J. Watson Research Center) and Jayant Kalagnanam

Examples of Complex Marketplaces: Customers, Models and Solution Methods

We discuss three classes of complex marketplaces: direct procurement, indivisible supply/demand, and combinatorial bids with type constraints. For each, we describe the commerce environment, the mathematical models and the solution methods.

In weekly direct procurement, suppliers submit bundled bids for multiple commodities. The goal is to select a minimum ocst set of bids that meet all requirements while satisfying additional constraints such as a minimum number of suppliers for each commodity and maximum number os suppliers.

Certain commodities such as steel and paper need to be sourced from a single supplier; a bid for a 2 feet wide galvanized coil cannot be satisfied by two 1 foot wide coils. The introduction of such indivisability constraints makes the problem of finding the set of winning bids and asks NP-hard and can be modeled as a generalized assignment problem.

Based on a liability limiting constraint proposed by the FCC for its license auction, we formulate a more general type-based bidding system for combinatorial auctions, and discuss a column generation approach for solving such auctions.

Suzhou Huang (Ford Motor Company)

Pricebot Dynamics

We study a class of dynamic pricing duopoly games that model the type of environment in which e-commerce will be carried out in not so distant future. Under Markov settings these games can be solved via backward induction. The equilibrium structure is found to display very complex patterns when parameters of the model are varied, due to bifurcation phenomena in the discrete map induced by backward induction. However, it is possible to define an effective but simpler dynamics that retains the optimality of the original game in the long run. We further show that this effective dynamics can be sustained by steady self-confirming equilibria. Our results (1) set limits on what learning algorithms based on Markov assumptions can obtain and (2) imply that learning in this kind of games should not be focused on the exact reaction functions, but rather on achieving optimal net present values with the realized time series of prices.

Jeffrey O. Kephart (Institute for Advanced Commerce IBM Thomas J. Watson Research Center)   kephart@us.ibm.com

Dynamic Pricing by Software Agents

We envision a future in which the world economy and the Internet will merge and evolve into an information economy bustling with billions of economically motivated software agents that exchange information goods and services with humans and other agents. These software agents will constitute a new economic species that differs in some significant ways from humans. What impact might collective interactions among agents have on market behavior, and on the global economy as a whole?

In this talk, I will focus on collective interactions among software agents that dynamically price information goods or services. I will discuss two types of dynamic pricing. First, I will cover a few examples of dynamic posted pricing, in which automated pricing agents ("pricebots") continually adjust the price of a commodity (or the price and attributes of a more complex product) in an effort to maximize profits. The price dynamics that result from interactions among pricebots are often quite complex, sometimes to the detriment of buyers as well as sellers. I will describe the connection of these and other nonlinear dynamical effects to optimization and learning. Second, I will discuss some very recent work on bidding algorithms for agents. We have found that relatively simple algorithms for a multi-unit continuous double auction consistently outperform humans in controlled experiments involving students and IBM Researchers.

John Ledyard (California Institute of Technology)

Optimal Mechanism Design for Internet Auctions

Paul Milgrom (Stanford University)

Putting Auction Theory to Work: Ascending Auctions with Package Bidding

After reviewing the factors contributing to the present interest in new package bidding designs, a benchmark ascending auction with package bidding is described. If bidders bid straightforwardly at each round for the potentially most profitable package, the allocation converges to an approximately efficient one. Straightforward bidding is consistent with equilibrium when there are only two bidders and it is a best reply to straightforward bidding by other bidders for a bidder that wants to acquire all the items for sale. More generally, if others bid straightforwardly, then non-monotonicity in the prices over time create an incentive for bidders to delay making serious bids, increasing the time requirements and degrading the performance of the auction.

Alvin E. Roth (Harvard University) and Axel Ockenfels

Last Minute Bidding and the Rules for Ending Second Price Auctions: Theory and Evidence from a Natural Experiment on the Internet

An important issue in auction design concerns the rules governing the end of the auction. The internet auctions conducted by eBay and Amazon present a natural experiment because they use different rules for ending an auction. Auctions on eBay have a fixed end time, while auctions on Amazon, which operate under otherwise similar rules, do not have a fixed end time, but continue if necessary past the scheduled end time until ten minutes have passed without a bid. The strategic differences in the auction rules are reflected in the auction data by significantly more late bidding on eBay than on Amazon. Furthermore, more experienced bidders on eBay submit late bids more often than do less experienced bidders, while the effect of experience on Amazon goes in the opposite direction. On eBay, there is also more late bidding for antiques than for computers. We also find scale independence in the distribution over time of bidders' last bids, of a form strikingly similar to the 'deadline effect' noted in bargaining: last bids are distributed according to a power law. Both the theory and the data suggest that multiple causes contribute to late bidding, with strategic issues related to the rules about ending the auction playing an important role.

Michael H. Rothkopf (RUTCOR and Faculty of Management, Rutgers University)  Rothkopf@rutcor.rutgers.edu

Modeling Opportunities in Auctions

This paper argues that the answers to interesting questions about real auctions depend, often critically, on the particular mathematical assumptions that go into a model of an auction situation. It then suggests some understudied areas for fruitful mathematical research on competitive bidding. These include asymmetry, financially constrained bidders, complicated information structures, bidder decisions about auction participation, the effect of repeated auctions involving the same participants, auctioning items with interrelated values, and transaction costs. The paper also discusses two major areas where new, complicated auctions are being designed: combinatorial spectrum auctions and electricity and transmission rights auctions.

Garrett van Ryzin (Columbia University, Graduate School of Business)

Airline Revenue Management and e-Markets

Revenue (or yield) management uses applied mathematical methods to intelligently control the availability of price discounts. While the practice in airlines predates the internet by several decades, it shares some common features with dynamic pricing in e-markets. Moreover, airline tickets are among the highest volume consumer products sold through new e-commerce pricing mechanisms. Thus, a convergence of these two developments appears to be well underway. In this talk, we discuss the traditional revenue management problem and survey the mathematical models and algorithms that have been developed in this area. We then examine the impact of e-market innovations such as Priceline.com?s guaranteed purchase contracts, ticket auctions, etc. on the practice of revenue management. While some have suggested that auctions and similar innovations will completely replace traditional price mechanisms, a melding of new and old looks more likely. We discuss the research challenges that arise from this integration.

Rakesh V. Vohra (Northwestern University)

Combinatorial Auctions: A Survey

(Joint with Sven de Vries).

As the title suggests, its a survey. I will focus on the interplay between Integer Programming and Auction design.

Robert Weber (Northwestern University)

(Public Lecture, Monday night)

The Other Side of the (e-Commerce) Fence

Economic markets occasionally fail to work as intended. Sometimes the problem is less-than-rational behavior on the part of market participants. At other times participants, individually or collectively, are more rational than the market organizers anticipate, and, legally or otherwise, find ways to subvert a market to their own ends. Those seeking to build e-commerce marketplaces must take care to look at their systems through the eyes of those who will be players in the market.

Material from Talks

IMA "HOT TOPICS" Workshop: Mathematics of the Internet: E-Auction and Markets

"Hot Topics" Workshops

2000-2001 Program: Mathematics in Multimedia