GTDT -- Department of Computer Science

Game Theory and Decision Theory Reading Group Paper List

This is the place for links to papers.

Symmetries and the Complexity of Pure Nash Equilibrium - Felix Brandt et al

Learning in One-Shot Strategic Form Games - Moshe Tennenholtz

  • We propose a machine learning approach to action prediction in one-shot games. In contrast to the huge literature on learning in games where an agent's model is deduced from its previous actions in a multi-stage game, we propose the idea of inferring correlations between agents' actions in different one-shot games in order to predict an agent's action in a game which she did not play yet. We define the approach and show, using real data obtained in experiments with human subjects, the feasibility of this approach. Furthermore, we demonstrate that this method can be used to increase payoffs of an adequately informed agent. This is, to the best of our knowledge, the first proposed and tested approach for learning in one-shot games, which is the most basic form of multi-agent interaction.

Regret-based Incremental Partial Revelation Mechanisms - Hyafil and Boutilier

  • Classic direct mechanisms suffer from the drawback of requiring full type (or utility function) revelation from participating agents. In complex settings with multi-attribute utility, assessing utility functions can be very difficult, a problem addressed by recent work on preference elicitation. In this work we propose a framework for incremental, partial revelation mechanisms and study the use of minimax regret as an optimization criterion for allocation determination with type uncertainty. We examine the incentive properties of incremental mechanisms when minimax regret is used to determine allocations with no additional elicitation of payment information, and when additional payment information is obtained. We argue that elicitation effort can be focused simultaneously on reducing allocation and payment uncertainty.

Spiteful Bidding in Sealed-Bid Auctions - Felix Brandt, Tuomas Sandholm and Yoav Shoham

  • We study the bidding behavior of spiteful agents who, contrary to the common assumption of self-interest, maximize the weighted difference of their own profit and their competitors' profit. This assumption is motivated by inherent spitefulness, or, for example, by competitive scenarios such as in closed markets where the loss of a competitor will likely result in future gains for oneself. We derive symmetric Bayes Nash equilibria for spiteful agents in \first-price and \second-price sealed-bid auctions. In \first-price auctions, bidders become ``more truthful'' the more spiteful they are. Surprisingly, the equilibrium strategy in \second-price auctions does not depend on the number of bidders. Based on these equilibria, we compare revenue in both auction types. It turns out that expected revenue in \second-price auctions is higher than expected revenue in \first-price auctions whenever agents have the slightest interest in reducing others' profit as long as they still care for their own profit. In other words, revenue equivalence only holds for auctions in which all agents are either self-interested or completely malicious. We furthermore investigate the impact of common knowledge on spiteful bidding. Making bidders' valuations publicly available results in less revenue in \second-price auctions whereas it increases revenue in \first-price auctions.
Last Update: August 2006