Automated Bidding Strategies and the Power of Threats
| Michael Littman (Rutgers University)
Peter Stone (University of Texas at Austin),
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
- 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
Back to the Main Page
Last modified: Mon Apr 28 16:55:23 EDT 2003