Research Overview

This page contains current and past research activity. I currently work within the confines of the Artificial Intelligence Laboratory at the University of Michigan and has been funded by the STIET fellowship which is awarded to doctoral students interested in furthering research related to electronic transactions.

My thesis research is primarily divided into two major foci: developing tools and techniques for practical strategic reasoning (empirical game theory) and applying the developed methodology to market games.

Empirical Game Theory

In cases where exact analytical models of a game cannot be constructed, empirical game-theoretic models often provide a viable alternative. I address three basic problems of interest within empirical game theory. First, how should strategies be evaluated in an empirical game model? Second, how should modelers optimally select strategy profiles to simulate? Finally, what game model best predicts payoffs resulting from agent play? I describe my approach to these problems in my thesis proposal.

Ad Auctions

Internet advertising provides a substantial source of revenue for online publishers, amounting to billions of dollars annually. Sponsored search is a popular form of targeted advertising, in which query-specific advertisements are placed alongside organic search-engine results. The placement (position) of an ad for a given query, along with the cost (to the advertiser) per click (CPC), is determined through an auction process. Under cost-per-click pricing, both the publisher and advertiser bear some of the risk associated with uncertain user behavior. The use of automated auctions addresses the combinatorial problem of quoting an appropriate price (CPC) for each display slot for each distinct query. Advertisers bid for the family of keywords of interest, and competition among them determines the going CPC for each of the available slots on a query-by-query basis.

Over the history of sponsored search, a variety of ad auction mechanisms, differing on pricing and ranking rules, have been employed. For example, the CPC for a slot can be set at the price bid by the winner of that slot (called the generalized first price rule), or by the price bid by the winner of the next-best position (generalized second-price). Similarly, mechanisms may rank by the CPC bid, or adjust these bids by a quality score taking into account such factors as the likelihood the ad will be clicked. For any such mechanism, advertisers face the problem of how to generate bids over time, considering their value for exposure, the competitive environment, and many other factors. Complicating matters, the value an advertiser assigns to an ad may change dynamically, forcing advertisers to balance their current knowledge of the ad markets with a need to explore the bid, keyword, and ad design space.

Given the salience of ad auction mechanisms, a growing number of researchers have started to investigate the mechanism design problem faced by search publishers, as well as the strategic problems faced by advertisers. As part of my thesis, members of the Strategic Reasoning Group and I introduce a new ad auctions game in an attempt to facilitate such research by presenting a concrete scenario in the sponsored-search domain.

The Ad Auctions game is developed as part of the Trading Agent Competition. Agents play the role of search engine advertisers, who compete with each other on ad placement for search results. The final round of the TAC/AA tournament will be held in Pasadena in July in conjunction with IJCAI 2009. The scenario employs a standard ad auction mechanism, and a simple yet structured model of a population of search users within a simulated retail market. Developing advertiser strategies for bidding and ad selection in this domain is a challenging problem, beyond the reach of known analytical solutions. Our hope is that by tackling this problem competitively, researchers and practitioners participating in TAC/AA will produce new ideas about bidding strategy for advertising (and in general), as well as insights about sponsored-search mechanisms and ways to improve the model.

In addition to the design of the TAC/AA game, I have also been involved in another competition focusing on sponsored search. I designed and implemented an autonomous agent, BlueReason, for the 2006 Bidding Agent Competition. BlueReason placed third out of twelve teams from various universities and organizations around the world. The competition departed from the typical simulation-based frameworks found in TAC scenarios in that teams managed a campaign in a real-world market.

Supply Chain Management

The management of supply chains poses a complex strategic problem faced by many of today's businesses. In response to the growing complexity, many firms engaged in various information technology services such as EDI systems and ERP services. The business processes involved in and surrounding these services are becoming increasingly automated. Analyzing the efficacy of the mixed initiative and autonomous systems regulating supply chains is becoming an increasingly important research question. The Trading Agent Competition Supply Chain Management scenario addresses many interesting aspects of such a challenging problem in a repeatable simulation environment.

The University of Michigan's Deep Maize agent which has been a perennial tournament finalist since the tournament's inception (2003) and I have participated as one of the lead developers over the course of its history. This culminated in the 2008 TAC/SCM tournament, in which Deep Maize was the champion. In addition to the main SCM scenario, two challenges have been proposed. Deep Maize has participated in the Prediction Challenged in which our team recorded a first place finish in 2007 and a second place finish in 2008.

Computational Market Mechanisms for Electronic Exchanges

As part of the STIET Summer Research Opportunity Program, I mentored students participating in the second annual TAC/CAT competition tournament. Undergraduates Kemal Eren, Flavio Kuperman, and Bongseog Choi extended the MANX (Michigan Agent for Negotiated eXchange) from the 2007 competition. The much improved agent placed second in the 2008 competition.