Bidders with hard valuation problems

ABSTRACT

Auctions provide efficient and distributed ways of allocating goods and tasks among agents. In this paper we study optimal strategies for computationally limited agents, where agents must use their limited computing resources to determine valuations for (bundles of) the items being auctioned. Agents are free to compute on any valuation problems including their opponents'. The deliberation actions are incorporated into the agents' strategies and different auction settings (both single--item and combinatorial) are analyzed in order to determine equilibrium strategies. We show that in some auction mechanisms, but not others, in equilibrium the bidders compute on others' problems as well. We show that the model of bounded rationality (limited or costly computing) impacts the agents' equilibrium strategies and so must be considered when designing mechanisms for computationally limited agents.

REFERENCES

• 1: Mark Boddy , Thomas L. Dean, Deliberation scheduling for problem solving in time-constrained environments, Artificial Intelligence, v.67 n.2, p.245-285, June 1994 [doi>10.1016/0004-3702(94)90054-X]
• 2: Kate Larson , Tuomas Sandholm, Bargaining with limited computation: deliberation equilibrium, Artificial Intelligence, v.132 n.2, p.183-217, November 2001 [doi>10.1016/S0004-3702(01)00132-1]
• 3: Kate Larson , Tuomas Sandholm, Costly valuation computation in auctions, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
• 4: P. Milgrom. Auctions and bidding: A primer. Journal of Economic Perspectives, 3(3):3--22, 1989.
• 5: D. C. Parkes. Optimal auction design for agents with hard valuation problems. In Agent-Mediated Electronic Commerce Workshop at IJCAI99, Stockholm, Sweden, 1999.
• 6: Stuart Russell, Principles of metareasoning, Artificial Intelligence, v.49 n.1-3, p.361-395, May 1991 [doi>10.1016/0004-3702(91)90015-C]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Theory