home
GTDT

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
gtdt" 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:
September
18: "Approximation Algorithms and Online Mechanisms for Item Pricing" MariaFlorina 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 singleminded 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 4approximation, 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 incentivecompatible
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 Pointbased 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. Pointbased 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 pointbased 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 pointbased 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.
October
2: Regretbased 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 multiattribute 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
November
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
December
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
