We study dynamic mechanisms for optimizing revenue in repeated auctions, that are robust to heterogeneous forward-looking and learning behavior of the buyers. Typically it is assumed that the buyers are either all myopic or are all infinite lookahead, and that buyers understand and trust the mechanism. These assumptions raise the following question: is it possible to design approximately revenue optimal mechanisms when the buyer pool is heterogeneous? Facing a heterogeneous population of buyers with an unknown mixture of @math -lookahead buyers, myopic buyers, no-regret-learners and no-policy-regret learners, we design a simple state-based mechanism that achieves a constant fraction of the optimal achievable revenue.
The study of @math -lookahead search can be viewed in the context of bounded rationality , as pioneered by Herb Simon @cite_14 . He argued that, instead of optimizing, agents may apply a class of heuristics, termed satisfying heuristics in decision making. A natural choice of such heuristics is restricting the search space of best-response moves. Lookahead search in decision-making has been motivated and examined in great extent by the artificial intelligence community @cite_7 @cite_31 @cite_35 . Lookahead search is also related to the sequential thinking framework in game theory @cite_21 . More recently, @cite_3 study the quality of equilibrium outcomes for look-ahead search strategies for various classes of games. They observe that the quality of resulting equilibria increases in generalized second-price auctions, and duopoly games, but not in other classes of games. No prior work studies dynamic mechanisms that are robust against various lookahead search strategies.
@cite_35 @cite_14 @cite_7 @cite_21 @cite_3 @cite_31
2148962857 2126701363 2046289784 2529439 1549049553
Introduction, 99. — I. Some general features of rational choice, 100.— II. The essential simplifications, 103. — III. Existence and uniqueness of solutions, 111. — IV. Further comments on dynamics, 113. — V. Conclusion, 114. — Appendix, 115. One important application of tree searching is looking ahead on a decision tree or game tree to try to predict the results of a decision. To guarantee correct results, substantial portions of the tree must be completely searched, which is physically impossible for very large trees. The author has developed a mathematical theory modeling the effects of search depth on the probability of making a correct decision. In this theory, the errors made by the evaluation function are modeled as independent, identically distributed random errors superimposed on the true values of the nodes evaluated. This research has produced the surprising result that there is an infinite class of game trees for which searching deeper does not increase the probability of making a correct decision, but instead causes the decision to become more and more random. The paper contains a mathematical proof of this statement, experimental verification of it, and a discussion of its significance. 31 references. Abstract We pose a hierarchial model of strategic thinking and conduct an experiment to test this theory as well as other solution concepts for symmetric (3 × 3) games. A level-0 type plays unpredictably, a level-1 type acts as if everyone else were level-0 types, and a level-2 type acts as if all other players were level-0 and level-1 types. In a model with level-0,…, level-2, and Nash types, we estimated that an insignificant portion of the participants were level-0 types, 24 were level-1 types, 49 were level-2 types, and the remaining 27 were Nash types. Lookahead search is perhaps the most natural and widely used game playing strategy. Given the practical importance of the method, the aim of this paper is to provide a theoretical performance examination of lookahead search in a wide variety of applications. To determine a strategy play using lookahead search, each agent predicts multiple levels of possible re-actions to her move (via the use of a search tree), and then chooses the play that optimizes her future payoff accounting for these re-actions. There are several choices of optimization function the agents can choose, where the most appropriate choice of function will depend on the specifics of the actual game - we illustrate this in our examples. Furthermore, the type of search tree chosen by computationally-constrained agent can vary. We focus on the case where agents can evaluate only a bounded number, k, of moves into the future. That is, we use depth k search trees and call this approach k-lookahead search. We apply our method in five well-known settings: industrial organization (Cournot's model); AdWord auctions; congestion games; valid-utility games and basic-utility games; cost-sharing network design games. We consider two questions. First, what is the expected social quality of outcome when agents apply lookahead search? Second, what interactive behaviours can be exhibited when players use lookahead search? We demonstrate how the answer depends on the game played.