Jin Akiyama
(Tokyo University of Science), Reversible Figures and Solids
An example of reversible (or hinge insideout transformable) figures
is Dudeney's Haberdasher's puzzle in which an equilateral triangle is
dissected into four pieces, hinged like a chain, and then is
transformed into a square by rotating the hinged pieces. Furthermore,
the entire boundary of each figure goes into the inside of the other
figure and becomes the dissection lines of the figure. Many intriguing
results on reversibilities of figures have been found in the preceding
research, but most of them are results on polygons. We generalize
those results to general connected figures. It is shown that two nets
obtained by cutting the surface of an arbitrary convex polyhedron
along noninteresting dissection trees are reversible. Moreover, we
generalize reversibility for 2Dfigures to one for 3Dsolids.
Joint work with Jin Akiyama (Tokyo University of Science).
Allan Borodin
(University of Toronto), Simplicity Is in Vogue (again)
Throughout history there has been an appreciation of the importance of
simplicity in the arts and sciences. In the context of algorithm
design, and in particular in apprxoximation algorithms and algorithmic
game theory, the importance of simplicity is currently very much in
vogue. I will present some examples of the current interest in the
design of “simple algorithms”. And what is a simple
algorithm? Is it just “you'll know it when you see it”, or
can we benefit from some precise models in various contexts?
José Correa
(Universidad de Chile), Subgame Perfect Equilibrium: Computation and Efficiency
The concept of Subgame Perfect Equilibrium (SPE) naturally arises in
games which are played sequentially. In a simultaneous game the
natural solution concept is that of a Nash equilibrium in which no
players has an incentive to unilaterally deviate from her current
strategy. However, if the game is played sequentially, i.e., there is
a prescribed order in which the players make their moves, an SPE is a
situation in which all players anticipate the full strategy of all
other players contingent on the decisions of previous
players. Although most research in algorithmic game theory has been
devoted to understand properties of Nash equilibria including its
computation and the socalled price of anarchy in recent years there
has been an interest in understanding the computational properties of
SPE and its corresponding efficiency measure, the sequential price of
anarchy.
In this talk we will review some of these recent results putting
particular emphasis on a very basic game, namely that of atomic
selfish routing in a network. In particular we will discuss some
hardness results such as the PSPACEcompleteness of computing an SPE
and its NPhardness even when the number of players fixed to two. We
will also see that for interesting classes of games SPE avoid worst
case Nash equilibria, resulting in substantial improvements for the
price of anarchy. However, for the atomic network routing games with
linear latencies, where the price of anarchy has long been known to be
equal to \(5/2\), we prove that the sequential price of arachy is not
bounded by any constant and can be as large as
\(\Omega(\sqrt{n})\), with \(n\) being the number of players.
Alan Frieze
(Carnegie Mellon University), Buying Stuff Online
Suppose there is a collection \(x_1, x_2, \ldots,
x_N\) of independent uniform \([0, 1]\) random
variables, and a hypergraph \(F\) of target structures on the
vertex set \(\{1, \ldots, N\}\). We would like to buy a target structure
at small cost, but we do not know all the costs \(x_i\)
ahead of time. Instead, we inspect the random variables
\(x_i\) one at a time, and after each inspection, choose
to either keep the vertex \(i\) at cost \(x_i\),
or reject vertex \(i\) forever.
In the present paper, we consider the case where \(\{1, \ldots, N\}\) is the
edgeset of some graph, and the target structures are the spanning
trees of a graph; the spanning arborescences of a digraph; the
Hamilton cycles of a graph; the prefect matchings of a graph; the
paths between a fixed pair of vertices; or the cliques of some fixed
size.
Joint work with Wesley Pegden (CMU).
Héctor GarcíaMolina
(Stanford University), Data Crowdsourcing: Is It for Real?
Crowdsourcing refers to performing a task using human workers that
solve subproblems that arise in the task. In this talk I will give an
overview of crowdsourcing, focusing on how crowdsourcing can help
traditional data processing and analysis tasks. I will also give a
brief overview of some of the crowdsourcing research we have done at
the Stanford University InfoLab.
