Speaker: Vasilis Zikas, ETH Zurich
Abstract. As complex security challenges emerge, cryptography is called to provide secure solutions for a wide range of applications. Bridging the gap between theory and applications is perhaps the biggest challenge of contemporary cryptography. In this talk I discuss how the use of cross- disciplinary technologies can help us achieve this goal. I demonstrate this in two major problems in cyber-security, namely secure distributed computation and malware protection. For the former, I show how combining ideas from game theory and cryptography provides grounds for the design of highly efficient, more resilient, and simpler provably secure protocols. For the latter, I present a novel approach to provably secure detection of malware injection and the idea of a prototype system.
Speaker: Reshef Meir, Harvard University
Abstract: In multi-agent interactions, each agent often faces uncertainty over the incentives and the behavior of the other agents. The traditional approach assumes that agents each maximize their expected utility w.r.t. some common prior distribution. However in most real-world scenarios agents have no way to accurately or even approximately know this distribution. Moreover, numerous psychological experiments have demonstrated that human decision makers fail even at fairly simple tasks involving probabilistic reasoning, and are prone to cognitive biases such as risk-aversion and loss-aversion. I will describe an alternative, non-probabilistic, model for representing players’ uncertainty in games, inspired by artificial intelligence and bounded rationality approaches. While the model is quite general, I will demonstrate how it applies for preference aggregation mechanisms (voting), overcoming many shortcomings of previous theories. My main result is that the behavior of bounded-rational agents boils down to a simple and natural dynamics, which is guaranteed to converge to equilibrium. Extensive simulations show that the resulting equilibria replicate known phenomena from real-world voting. Finally, I will show how key components of this approach can be extracted and applied to very different settings, including online scheduling on Doodle and routing in networks with uncertain congestion. The talk is based on published and unpublished work with Omer Lev, David Parkes, Jeffrey S. Rosenschein, and James Zou.
Speaker: Moshe Vardi, Rice University
Abstract. Mathematical logic was developed in an effort to provide formal foundations for mathematics. In this quest, which ultimately failed, logic begat computer science, yielding both computers and theoretical computer science. But then logic turned out to be a disappointment as foundations for computer science, as almost all decision problems in logic are either unsolvable or intractable. Starting from the mid 1970s, however, there has been a quiet revolution in logic in computer science, and problems that are theoretically undecidable or intractable were shown to be quite feasible in practice. This talk describes the rise, fall, and rise of logic in computer science, describing several modern applications of logic to computing, include databases, hardware design, and software engineering.
Speaker: John Postl
Abstract: We study profit sharing games in which players select projects to participate in and share the reward resulting from that project equally. Unlike most existing work, in which it is assumed that the player utility is monotone in the number of participants working on their project, we consider non-monotone player utilities. Such utilities could result, for example, from “threshold” or “phase transition” effects, when the total benefit from a project improves slowly until the number of participants reaches some critical mass, then improves rapidly, and then slows again due to diminishing returns. Non-monotone player utilities result in a lot of instability: strong Nash equilibrium may no longer exist, and the quality of Nash equilibria may be far away from the centralized optimum. We show, however, that by adding additional requirements such as players needing permission to leave a project from the players currently on this project, or instead players needing permission to a join a project from players on that project, we ensure that strong Nash equilibrium always exists. Moreover, just the addition of permission to leave already guarantees the existence of strong Nash equilibrium within a factor of 2 of the social optimum. In this paper, we provide results on the existence and quality of several different coalitional solution concepts, focusing especially on permission to leave and join projects, and show that such requirements result in the existence of good stable solutions even for the case when player utilities are non-monotone.
Speaker: Nicole Immorlica, Microsoft Research New England
Abstract. Theoretical computer scientists often view the world through a lens of paranoia, focusing on bounding the worst-case performance of the systems they study. Economists instead prefer to assume the inputs are drawn from a well-behaved and commonly known distribution and study the resulting average-case performance of the system. In this talk, we survey efforts aimed at a middle ground. We identify small realistic perturbations to economic settings that result in a good properties often even for worst-case inputs. We begin with a classic example of this phenomenon: in a canonical single-item market, if buyers’ values are drawn from a nice (but unknown) distribution, then simple auctions have good revenue. We then discuss more complex multi-item markets, and identify noisy supply and demand conditions that guarantee good welfare. Finally, we mention extensions of these results to non-market games, including network routing, two-sided matching, and information aggregation in social networks. In all cases, we identify conditions under which games perform much better than the corresponding worst-case instances, and often improve significantly as the market grows. Many of our results are based on a new analytical framework for bounding inefficiency of a sequence of games. Based on joint works with Michal Feldman, Brendan Lucier, Mohammad Mahdian, Tim Roughgarden, Vasilis Syrkganis, and Matt Weinberg.
Speaker: Lirong Xia
Abstract: In this paper, we take a statistical decision-theoretic viewpoint on social choice, putting a focus on the decision to be made on behalf of a system of agents. In our framework, we are given a statistical ranking model, a decision space, and a loss function defined on (parameter, decision) pairs, and formulate social choice mechanisms as decision rules that minimize expected loss. This suggests a general framework for the design and analysis of new social choice mechanisms. We compare Bayesian estimators, which minimize Bayesian expected loss, for the Mallows model and the Condorcet model respectively, and the Kemeny rule. We consider various normative properties, in addition to computational complexity and asymptotic behavior. In particular, we show that the Bayesian estimator for the Condorcet model satisfies some desired properties such as anonymity, neutrality, and monotonicity, can be computed in polynomial time, and is asymptotically different from the other two rules when the data are generated from the Condorcet model for some ground truth parameter.
Speaker: David Woodruff, IBM Watson
Abstract. I'll highlight recent advances in algorithms for numerical linear algebra that have come from the technique of linear sketching, whereby given an n x d matrix A, one first compresses A to an m x d matrix S*A, where S is a certain m x n random matrix with m much less than n. Much of the expensive computation is then performed on S*A, thereby accelerating the solution for the original problem involving A. I'll discuss recent advances in least squares as well as robust regression, including least absolute deviation and M-estimators. I'll also discuss low rank approximation, and a number of variants of these problems such as kernel and communication-efficient solutions. Finally, I'll mention limitations of the method.