Game Theory Discussion Group - Spring 2005

We present the first general-purpose techniques for automatically designing multistage mechanisms. These can reduce elicitation burden by only querying agents for information that is relevant given their answers to previous queries. We first show how to turn a given (e.g., automatically designed) single-stage mechanism into the most efficient corresponding multistage mechanism given a specified elicitation tree. We then present greedy and dynamic programming algorithms that will determine the elicitation tree (optimal in the DP case). Next, we show how the query savings inherent in the multistage model can be used to design the underlying single-stage mechanism to maximally take advantage of this approach. Finally, we present negative results on the design of multistage mechanisms that do not correspond to dominant-strategy single-stage mechanisms: an optimal multistage mechanism in general has to randomize over queries to hide information from the agents.

This talk will be in two parts. And both parts will be informal. In the first part I will describe the General Game Playing Competition which is being held for the first time at AAAI this year. In the second part I will describe our work on the Multi-Agent Meeting Scheduling Problem. I will talk about the difficulties we encountered in trying to use a Mechanism Design approach and some of our current work on intelligent negotiation.

We present a technique for reducing a normal-form game, $O$, to a smaller normal-form game, $R$, for the purpose of computing a Nash equilibrium. This is done by computing a Nash equilibrium for a subgame, $G$, of $O$ for which a certain condition holds. We also show that such a subgame $G$ on which to apply the technique can be found in polynomial time (if it exists). We show that the technique does not extend to computing Pareto-optimal or welfare-maximizing equilibria. Finally, we present a class of games, which we call ALAGIU (Any Lower Action Gives Identical Utility) games, for which recursive application of (special cases of) the technique is sufficient for finding a Nash equilibrium in linear time.

In an attribute auction, a seller (auctioneer) is marketing some good of unlimited supply to n bidders, each of whom has a set of public attributes. The goal of the seller is to achieve a revenue competitive with the best pricing function in some given class of functions over the attributes. This setting was introduced in [Blum, Hartline 2005], where the special case of 1-dimensional real-valued attributes was considered, and results were given for the comparison class of piecewise-constant functions with k pieces.

In this work, we consider attribute auctions more generally, and show a natural strategy by which an auctioneer can perform nearly as well as the best pricing scheme in any given class, so long as the number of bidders is large enough as a function of an appropriate measure of the complexity of the class. We do this by making a natural connection to the notion of sample-complexity in machine learning, though from a learning perspective the auction setting presents certain unique challenges: in particular, the loss function is discontinuous and asymmetric, and the range of bid values may be large. We also consider a partial-information setting in which the auctioneer only gets information by making offers that are either accepted or rejected, and provide bounds for that case as well.

Joint work with Avrim Blum, Jason Hartline, and Yishay Mansour.

Consider a repeated game in which players are only partially informed about the actual stage game. The theory of repeated games of incomplete information characterizes the optimal strategies each player should play. In this overview talk, I will present the basic theory for two-player zero-sum games of incomplete information, with lack of information on one side.

I will conclude with a few thoughts about the computational problem of computing optimal strategies.

Practice talk for thesis proposal.