Approximating mixed Nash equilibria using smooth fictitious play in simultaneous auctions

ABSTRACT

We investigate equilibrium strategies for bidding agents that participate in multiple, simultaneous second-price auctions with perfect substitutes. For this setting, previous research has shown that it is a best response for a bidder to participate in as many such auctions as there are available, provided that other bidders only participate in a single auction. In contrast, in this paper we consider equilibrium behaviour where all bidders participate in multiple auctions. For this new setting we consider mixed-strategy Nash equilibria where bidders can bid high in one auction and low in all others. By discretising the bid space, we are able to use smooth fictitious play to compute approximate solutions. Specifically, we find that the results do indeed converge to ε-Nash mixed equilibria and, therefore, we are able to locate equilibrium strategies in such complex games where no known solutions previously existed.

REFERENCES

• 1: G. W. Brown. Iterative solutions of games by fictitious play. In T. C. Koopmans, editor, Activity Analysis of Production and Allocation, pages 374--376. Wiley, 1951.
• 2: R. Engelbrecht-Wiggans and R. Weber. An example of a multiobject auction game. Management Science, 25:1272--1277, 1979.
• 3: D. Fudenberg and D. K. Levine. Consistency and cautious fictitious play. Journal of Economic Dynamics and Control, 19:1065--1089, 1995.
• 4: D. Fudenberg and D. K. Levine. The Theory of Learning in Games. MIT Press, 1999.
• 5: Enrico H. Gerding , Rajdeep K. Dash , David C. K. Yuen , Nicholas R. Jennings, Bidding optimally in concurrent second-price auctions of perfectly substitutable goods, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329188]
• 6: V. Krishna and R. Rosenthal. Simultaneous auctions with synergies. Games and Economic Behaviour, 17:1--31, 1996.
• 7: D. Monderer and L. S. Shapley. Fictitious play property for games with identical interests. Journal of Economic Theory, 68(1):258--265, 1996.
• 8: R. Rosenthal and R. Wang. Simultaneous auctions with synergies and common values. Games and Economic Behaviour, 17:32--55, 1996.
• 9: B. Szentes and R. Rosenthal. Three-object two-bidder simultaneous auctions: Chopsticks and tetrahedra. Games and Economic Behaviour, 44:114--133, 2003.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation

General Terms:
Algorithms, Design, Management, Theory