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
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:
September
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.
October
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
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
|