AI Boosting Smarts of Online Auctions

Computerworld - When electronic marketplaces evolved out of the dot-com boom of the late 1990s, conventional wisdom held that these digital exchanges would operate more efficiently than physical marketplaces by removing the middleman and streamlining the procurement process.
And while some of these exchanges have generated significant operational efficiencies for their participants, Tuomas Sandholm has identified other improvements that can be realized. Sandholm, who runs the Agent-Mediated Electronic Commerce Laboratory at Carnegie Mellon University in Pittsburgh and is an associate professor in the school's computer science department, has patented a method for determining the best rules to apply to decision-making processes.
The approach, which draws upon artificial intelligence and operations research techniques, can be applied not only to business-to-business auctions but also in setting rules for divorce settlements and evaluating public works projects.
Computerworld's Thomas Hoffman recently caught up with Sandholm, a 34-year-old former world-class windsurfer, to discuss the work he has been doing in AI and e-commerce.
Describe the research you're doing. At a high level, what we do is design and build electronic marketplaces that lead to more efficient outcomes. Think of a traditional procurement auction. The seller has to "pre-lot" the items to be bought. But that doesn't always meet the bidders' needs and optimize the marketplace. What we've created are auctions where people can bid expressively by building their own self-selected lots [of merchandise].
For example, a bidder can say, "I'm willing to pay $100 for Items 6, 7 and 8." But the problem of determining who wins what items is a most difficult problem, and we've built algorithms to help address this.

What's an example of this? Consider an auction where the bidders have submitted bids on different, overlapping packages of items. For example, one bidder can bid $100 for A, B and C. Another bidder bids $50 for C. A third bids $70 for B. Now, in this small example, it is relatively easy to see that the auctioneer should accept the latter two bids because he will collect $120, which is the highest possible revenue.

Tuomas Sandholm of Carnegie Mellon University

On the other hand, if there are tens of bids, this becomes difficult to determine by hand. Our algorithms solve this problem optimally with even hundreds of thousands of bids. The techniques used are AI searches.

How else can AI be applied to e-commerce? What are the current hurdles, and can they be overcome? There are lots of different things that can be applied here. Another stream of research we're doing is automated mechanism design. Mechanism design is a subfield of game