GTDT -- Department of Computer Science

Game Theory and Decision Theory Reading Group

Welcome to the Game Theory and Decision Theory Reading Group website. This is the place for announcements and links to papers.

To join the mailing list, email majordomo, with "subscribe gt-dt" in the message body.
There will also be more information on upcoming presentations.

In fall 2006 we are meeting on Monday 13h30 - 15h00 in ICICS 146 (LCI meeting room).

List of possible papers to present

Schedule of topics and presenter:

18: "Approximation Algorithms and Online Mechanisms for Item Pricing" Maria-Florina Balcon and Avrim Blum -- Baharak Rastegari

  • Abstract: We present approximation and online algorithms for a number of problems of pricing items for sale so as to maximize sellers revenue in an unlimited supply setting. Our first result is an O(k)-approximation algorithm for pricing items to single-minded bidders who each want at most k items. This improves over recent independent work of Briest and Krysta [5] who achieve an O(k^2) bound. For the case k = 2, where we obtain a 4-approximation, this can be viewed as the following graph vertex pricing problem: given a (multi) graph G with valuations we on the edges, find prices pi>= 0 for the vertices to maximize Sum_{ e=(i,j): w_e>=pi+pj} (pi + pj) We also improve the approximation of Guruswami et al. [11] from O(logm + log n) to O(log n), where m is the number of bidders and n is the number of items, for the highway problem in which all desired subsets are intervals on a line. Our approximation algorithms can be fed into the generic reduction of Balcan et al. [2] to yield an incentive-compatible auction with nearly the same performance guarantees so long as the number of bidders is sufficiently large. In addition, we show how our algorithms can be combined with results of Blum and Hartline [3], Blum et al. [4], and Kalai and Vempala [13] to achieve good performance in the online setting, where customers arrive one at a time and each must be presented a set of item prices based only on knowledge of the customers seen so far.

25: Perseus: Randomized Point-based Value Iteration for POMDPS -- Matthijs T. J. Spaan & Nikos Vlassis -- Jennifer Tillett
  • Partially observable Markov decision processes (POMDPs) form an attractive and principled framework for agent planning under uncertainty. Point-based approximate techniques for POMDPs compute a policy based on a finite set of points collected in advance from the agentís belief space. We present a randomized point-based value iteration algorithm called Perseus. The algorithm performs approximate value backup stages, ensuring that in each backup stage the value of each point in the belief set is improved; the key observation is that a single backup may improve the value of many belief points. Contrary to other point-based methods, Perseus backs up only a (randomly selected) subset of points in the belief set, sufficient for improving the value of each belief point in the set. We show how the same idea can be extended to dealing with continuous action spaces. Experimental results show the potential of Perseus in large scale POMDP problems.

2: Regret-based Incremental Partial Revelation Mechanisms by Hyafil and Boutilier -- AAAI, 2006 -- Mark Crowley

  • 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.

9: THANKSGIVING -- No talk scheduled.
16: "On the optimality of privacy in sequential contracting" by Giacomo Calzolari and Alessandro Pavan -- Baharak Rastegari
  • This paper studies the exchange of information between two principals who contract sequentially with the same agent, as in the case of a buyer who purchases from multiple sellers. We show that when (a) the upstream principal is not personally interested in the downstream level of trade, (b) the agent's valuations are positively correlated, and (c) preferences in the downstream relationship are separable, then it is optimal for the upstream principal to offer the agent full privacy. On the contrary, when any of these conditions is violated, there exist preferences for which disclosure is strictly optimal, even if the downstream principal does not pay for the information. We also examine the effects of disclosure on welfare and show that it does not necessarily reduce the agent's surplus in the two relationships and in some cases may even yield a Pareto improvement.

23: Nando's series on approximation algorithms -- Part 1 -- Whiteboard notes -- Notes from "All of Statistics"
30: Nando's series on approximation algorithms -- Part 2 -- Whiteboard notes -- Textbook pages

6: Economics talk -- Albert Xin Jiang
13: Remembrance Day -- no talks
14: SPECIAL DAY & TIME -- 4 pm -- Mechanism Design and Communication Costs - Raymond Deneckere and Sergei Severinov -- Dave Thompson
20: Nando's series on approximation algorithms -- Part 3
27: Nando's series on approximation algorithms -- Part 4

4: Jan or Erik or Kevin LB
11: Tao Wang, University of Alberta

Possible future topics

  • Computing equilibria
  • Sampling techniques + game theory
  • Compact representations
  • Machine learning and game theory
  • Bounded rationality
  • Game theory and decision theory
  • Preference elicitation
  • Dynamic and repeated games
  • Bayesian games
  • Trading agent competition
  • Auctions (with severely limited communication)
  • Boosting

  • Last Update: August 2006