Friday, November 14, 2014,
New York City
The Graduate Center, CUNY
Room 4102 (Science Center) and room 4421
On the Complexity of Nash Equilibria in Anonymous Games
Anonymous games are a large and well-studied class of succinct multiplayer games, in which the payoff of each player depends only on her own strategy and number of other players playing each strategy. In a sequence of papers, Daskalakis and Papadimitriou studied the problem of finding an approximate Nash equilibrium in an anonymous game, and obtained polynomial-time approximation schemes when the number of strategies is bounded. In this talk we briefly review their results and show that the problem is complete in PPAD when the number of strategies is at least seven and the approximation parameter is exponentially small, confirming a conjecture of Daskalakis and Papadimitriou.
Joint work with David Durfee (Georgia Institute of Technology) and Anthi Orfanou (Columbia University).
Control in the Presence of Manipulators: Cooperative and Competitive Cases
Control and manipulation are two of the most studied types of attacks
on elections. We study the complexity of control
attacks on elections in which there are manipulators. We study both
the case where the "chair" who is seeking to control the election is
allied with the manipulators, and the case where the manipulators seek
to thwart the chair. In the latter case, we see that the order of play
substantially influences the complexity. We prove upper bounds,
holding over every election system with a polynomial-time winner
problem, for all standard control cases, and some of these bounds are
at the second or third level of the polynomial hierarchy, and we
provide matching lower bounds to prove these tight. Nonetheless, for
important natural systems the complexity can be much lower. We prove
that for approval and plurality elections, the complexity of even
competitive clashes between a controller and manipulators falls far
below those high bounds, even as low as polynomial time. Yet for a
Borda-voting case we show that such clashes raise the complexity
unless NP=coNP. This is joint work with Zack Fitzsimmons
and Edith Hemaspaandra.
Disjoint NP-pairs and Propositional Proof Systems
This talk surveys results on disjoint NP-pairs, propositional proof systems,
function classes, and promise classes---including results that demonstrate close
connections that bind these topics together. We illustrate important links between
the questions of whether these classes have complete objects and whether optimal proof
systems may exist.
Spin models: connections between complexity, phase transition,
belief propagation, and induced matrix norms
What are the typical configurations of a spin model (for example,
Ising model, or Potts model) on a random regular graph ? We show that the
answer to this question is characterized by tree recursions (belief propagation)
and p->q operator matrix norms.
Understanding the typical configurations allows us to show hardness of
approximating the partition function for certain multispin models (for example,
Potts model) on d-regular graphs in the non-uniqueness regime (that is, when the
Gibbs measure on infinite d-regular tree is not unique). Joint work with
Andreas Galainis, and Eric Vigoda.
A Probably Approximately Correct Lower Bound for
Non-Adaptive Boolean Function Monotonicity Testing
Boolean function monotonicity testing is a problem that has received a lot of attention in the property testing community. In a recent work (FOCS 2014) Chen, Servedio and Tan gave an $\tilde{\Omega}(n^{1/5})$ lower bound on the query complexity of any non-adaptive two-sided error algorithm for testing whether an unknown $n$-variable Boolean function is monotone versus constant-far from monotone. This gives an exponential improvement on the previous lower bound of $\Omega(\log n)$ for this model due to Fischer et al from 2002.
More recently, Chen, De, Servedio and Tan extended this lower bound to $\Omega(n^{1/2-\tau})$ for any $\tau>0$. If one believes (as is commonly conjectured) that the true nonadaptive query complexity of monotonicity testing is $\Theta(\sqrt{n})$, this new lower bound is probably approximately correct (or more precisely, probably approximately tight).
In this talk I will present the main ideas behind these recent results and talk about directions for future work on the monotonicity testing problem.
Surveillance Adversary Protocols: past and future
Mechanism Design in presence of Verification and Applications
The basic mechanism design model assumes that each agent can follow any of its strategies,
independently of its type. Thus the mechanism cannot use any ”real-world” information
about the agents. This is the norm in mechanism design and it models well the negotiation
stage in which agents do nothing but communicate. A simple type of modification to the
model suggests itself: a problem definition may limit the set of strategies available to each
agent as a function of its type. In this work we investigate the way mechanism design
changes under the assumption of verification.
The first deference in the mechanism design with verification is the existence of non-
truthful implementations of social choice functions. We present the reason why this way
of implementation is not really helpful in the solution concept of dominant strategy equi-
librium and we present a way it could be useful using the concept of Nash equilibrium.
In this work, we also investigate the reasons that make symmetric partial verification
essentially useless in virtually all domains. Departing from previous work, we consider
any possible (finite or infinite) domain and general symmetric verification. We identify
a natural property, namely that the correspondence graph of a symmetric verification M
is strongly connected by finite paths along which the preferences are consistent with the
preferences at the endpoints, and prove that this property is sufficient for the equivalence
of truthfulness and M -truthfulness. Since the simplest symmetric verification is the local
verification, specific cases of our result are closely related, in the case without money, to
the research about the equivalence of local truthfulness and global truthfulness.