Welcome to the Game Theory and Decision Theory Reading Group website. To join the mailing list, email majordomo, with “subscribe gt-dt” in the message body.
For Term 1 2014, we’ll be meeting on Mondays from 12–2 in ICCS X530.
October 06 - Geoffrey Hinton (video) - “Tutorial on Deep Learning”. [NIPS 2009]
Complex probabilistic models of unlabeled data can be created by combining simpler models. Mixture models are obtained by averaging the densities of simpler models and “products of experts” are obtained by multiplying the densities together and renormalizing. A far more powerful type of combination is to form a “composition of experts” by treating the values of the latent variables of one model as the data for learning the next model. The first half of the tutorial will show how deep belief nets – directed generative models with many layers of hidden variables – can be learned one layer at a time by composing simple, undirected, product of expert models that only have one hidden layer. It will also explain why composing directed models does not work. Deep belief nets are trained as generative models on large, unlabeled datasets, but once multiple layers of features have been created by unsupervised learning, they can be fine-tuned to give excellent discrimination on small, labeled datasets. The second half of the tutorial will describe applications of deep belief nets to several tasks including object recognition, non-linear dimensionality reduction, document retrieval, and the interpretation of medical images. It will also show how the learning procedure for deep belief nets can be extended to high-dimensional time series and hierarchies of Conditional Random Fields.
September 29 - Alice Gao - “Trick or Treat: Putting Peer Prediction to the Test” by Xi Alice Gao, Andrew Mao, Yiling Chen, and Ryan P. Adams. (EC 2014), forthcoming
Collecting truthful subjective information from multiple individuals is an important problem in many social and online systems. While peer prediction mechanisms promise to elicit truthful information by rewarding participants with carefully constructed payments, they also admit uninformative equilibria where coordinating participants provide no useful information. To understand how participants behave towards such mechanisms in practice, we conduct the first controlled online experiment of a peer prediction mechanism, engaging the participants in a multiplayer, real-time and repeated game. Using a hidden Markov model to capture players’ strategies from their actions, our results show that participants successfully coordinate on uninformative equilibria and the truthful equilibrium is not focal, even when some uninformative equilibria do not exist or are undesirable. In contrast, most players are consistently truthful in the absence of peer prediction, suggesting that these mechanisms may be harmful when truthful reporting has similar cost to strategic behavior.
September 22 - Alexandre Fréchette - “Deferred-Acceptance Auctions and Radio Spectrum Reallocation” by Milgrom, P and Segal, I [forthcoming]
Deferred-acceptance auctions choose allocations by an iterative process of rejecting the least attractive bid. These auctions have distinctive computational and incentive properties that make them suitable for application in some challenging environments, such as the planned US auction to repurchase television broadcast rights. For any set of values, any deferred acceptance auction with "threshold pricing” is weakly group strategy-proof, can be implemented using a clock auction, and leads to the same outcome as the complete-information Nash equilibrium of the corresponding paid-as-bid auction. A paid-as-bid auction with a non-bossy bid-selection rule is dominance solvable if and only if it is a deferred acceptance auction.
September 15 - James Wright - “An Experimental Evaluation of Bidders’ Behavior in Ad Auctions” by G, Noti, N. Nisan, and I. Yaniv. WWW 2014.
We performed controlled experiments of human participants in a continuous sequence of ad auctions, similar to those used by Internet companies. The goal of the research was to understand users’ strategies in making bids. We studied the behavior under two auction types: (1) the Generalized Second-Price (GSP) auction and (2) the Vickrey–Clarke–Groves (VCG) payment rule, and manipulated also the participants’ knowledge conditions: (1) explicitly given valuations and (2) payoff information from which valuations could be deduced. We found several interesting behaviors, among them are:
No convergence to equilibrium was detected; moreover the frequency with which participants modified their bids increased with time.
We can detect explicit “better-response” behavior rather than just mixed bidding.
While bidders in GSP auctions do strategically shade their bids, they tend to bid higher than theoretically predicted by the standard VCG-like equilibrium of GSP.
Bidders who are not explicitly given their valuations but can only deduce them from their gains behave a lit- tle less “precisely” than those with such explicit knowl- edge, but mostly during an initial learning phase.
VCG and GSP yield approximately the same (high) social welfare, but GSP tends to give higher revenue.