Automated Bidding Strategies and the Power of Threats

Michael Littman (Rutgers University) and Peter Stone (University of Texas at Austin),

Abstract

This talk presents a sequence of five Littman and Stone collaborations over the past few years with the common theme and motivation of enabling autonomous agents to bid in competitive settings, a form of multiagent interaction: The entry point is our winning entry in the inaugural trading agent competition (TAC) in which simulated travel agents bid to obtain travel packages for a set of clients with individual preferences. Some of the successful methodology was then successfully applied to a real-world high-stakes auction scenario, namely the spectrum bandwidth auctions run by the Federal Communications Commission (FCC). Motivated by some of the theoretical issues that arose in this scenario, we developed a polynomial-time algorithm for finding a Nash equilibrium in an average-payoff repeated bimatrix game. Making use of this algorithm, we then introduce an efficient, general "leader" strategy that induces cooperative behaviors from opponent "followers" via stubbornness and threats in general-sum repeated bimatrix games. These tactics are forms of implicit negotiation in that they aim to achieve a mutually beneficial outcome without using explicit communication outside of the game. We then put aspects of this approach into practice in the FCC spectrum auction domain described previously. The resulting strategy - randomized strategic demand reduction (RSDR) - has the potential to save bidders a billion dollars in that scenario! In the remaining time we will apologize for taking longer than we expected.

Back to the Main Page