9:00 - 9:30 Registration
9:30 - 9:40 Opening
9:40 - 10:40 Keynote 1 – Prof. Joe Halpern (Cornell)
10:40 - 11:00 Rump session 1
11:00 - 11:20 Coffee
11:20 - 12:00 Senior talk 1 – Prof. Boaz Nadler (Weizmann)
12:00 - 12:20 Newcomer talk 1 – Dr. Nimrod Talmon (BGU)
12:20 - 12:40 Newcomer talk 2 – Dr. Ofra Amir (Technion)
12:40 - 13:00 Rump session 2
13:00 - 14:00 Lunch + Posters
14:00 - 15:00 Keynote 2 – Prof. Kevin Leyton-Brown (UBC)
15:00 - 15:20 Industry talk – Gila Kamhi (GM)
15:20 - 15:40 Coffee + Posters
15:40 - 16:20 Senior talk 2 – Dr. Avinatan Hassidim (BIU)
16:20 - 16:40 Newcomer talk 3 – Dr. Erel Segal-Halevi (Ariel)
16:40 - 17:00 Newcomer talk 4 – Dr. Omer Lev (BGU)
17:00 - 17:10 Announcement of winning student paper and farewell
Keynote 1: Prof. Joe Halpern, Cornell University
Decision theory with resource-bounded agents
There have been two major lines of research aimed at capturing resource-bounded players in game theory. The first, initiated by Rubinstein, charges an agent for doing costly computation; the second, initiated by Neyman does not charge for computation, but limits the computation that agents can do, typically by modeling agents as finite automata. We review recent work on applying both approaches in the context of decision theory. For the first approach, we take the objects of choice in a decision problem to be Turing machines, and charge players for the ``complexity'' of the Turing machine chosen (e.g., its running time). This approach can be used to explain well-known phenomena like first-impression-matters biases (i.e., people tend to put more weight on evidence they hear early on) and belief polarization (two people with different prior beliefs, hearing the same evidence, can end up with diametrically opposed conclusions) as the outcomes of quite rational decisions. For the second approach, we model people as finite automata, and provide a simple algorithm that, on a problem that captures a number of settings of interest, provably performs optimally as the number of states in the automaton increases. Perhaps more importantly, it seems to capture a number of features of human behavior, as observed in experiments. This is joint work with Rafael Pass and Lior Seeman. No previous background is assumed.
Keynote 2: Prof. Kevin Leyton-Brown, University of British Columbia
Learning as a Tool for Algorithm Design and Beyond-Worst-Case Analysis
All known algorithms for solving NP-complete problems require exponential time in the worst case; however, these algorithms nevertheless solve many problems of practical importance astoundingly quickly, and are hence relied upon in a broad range of applications. This talk is built around the observation that “Empirical Hardness Models”—statistical models that predict algorithm runtime on novel instances from a given distribution—work surprisingly well. These models can serve as powerful tools for algorithm design, specifically by facilitating automated methods for algorithm design and for constructing algorithm portfolios. They also offer a statistical alternative to beyond-worst-case analysis and a starting point for theoretical investigations.
Senior Talk 1: Prof. Boaz Nadler, Weizmann Institute of Science
Title:Unsupervised Ensemble Learning (or how to make good predictions while knowing almost nothing)
Abstract: In various applications, one is given the advice or predictions of several classifiers of unknown reliability, over multiple questions or queries. This scenario is different from standard supervised learning where classifier accuracy can be assessed from available labeled training or validation data, and raises several questions: given only the predictions of several experts of unknown accuracies, over a large set of unlabeled test data, is it possible to a) reliably rank them, and b) construct a meta-learner more accurate than any individual experts in the ensemble?
In this talk we'll show that under various independence assumptions between classifier errors, this high dimensional data hides simple low dimensional structures. Exploiting these, we will present simple spectral methods to address the above questions, and derive new unsupervised spectral meta-learners. We'll prove these methods are asymptotically consistent when the model assumptions hold, and present their empirical success on a variety of unsupervised learning problems.
Senior Talk 2: Prof. Avinatan Hassidim, Bar-Ilan University
Title: Market Design Patterns
Abstract: Market design has a rich and deep theory which draws from game theory, economics and algorithms. It also has real world applications, most notably in auctions (ad auctions, spectrum auctions etc.) and in labor markets (the Match, school choice systems in various cities). What is missing is design patterns: a way to take a concrete problems, and apply the right tools to it, in a way which would make sense. In this talk we will present the idea of market design patterns, discuss some well known patterns (which were not framed as such), and present new patters which we developed in designing various markets in Israel (the interns' lottery, the psychology match, failures in school choice systems and ongoing work on matching the lawyers' match). Based on joint works with Arnon Afek, Noga Alon, Slava Bronfman, Assaf Romm and Ran Shorer.
Newcommer 1: Dr. Nimrod Talmon, Ben-Gurion University of the Negev
Title: Axioms and Efficient Algorithms for Participatory Budgeting
Abstract: Participatory budgeting is a recent, exciting development in deliberative grassroots democracy in which, e.g., residents of a city specify their preferences on how to construct their city budget, and an algorithm is then applied to aggregate their preferences and decide upon the budget. Even though it is gaining increasing popularity and is used to decide upon many millions of dollars each year, the foundations of participatory budgeting are not yet well understood. I will discuss some recent developments, specifically novel, efficient aggregation algorithms satisfying certain axiomatic properties desired in participatory budgeting scenarios..
Newcommer 2: Dr. Ofra Amir, Technion – Israel Institute of Technology
Title: Summarizing Agent Behavior to People
Abstract: From cleaning robots to self-driving cars, autonomous and semi-autonomous agents are becoming increasingly prevalent. Understanding the capabilities and limitations of agents is important for users, as they might need to choose between different agents, adjust the level of autonomy of an agent, or work alongside an agent. While prior work has developed methods for explaining individual decisions of an agent to a person retrospectively, these approaches do not provide users with a global understanding of an agent’s expected behavior in a range of situations. In this talk, I will discuss the challenge of conveying an agent’s behavior to users. I will present our initial work toward the development of methods for generating summaries of agents’ strategies, and will show empirical results demonstrating that such summaries can help people better assess agents’ capabilities.
Newcommer 3: Dr. Erel Segal-Halevi, Ariel University
Title: Making an Appraiser Work for You
Abstract: You own an item and want to know its value. There is an appraiser who can calculate the value by investing some work. You want to convince the appraiser to invest this work and tell you the value. Unfortunately you have no way to verify that the appraiser's report is correct. Therefore, if you simply pay the appraiser the cost of doing the work in cash, he can take the cash and report some random value instead of doing the work. I will show a mechanism by which you can incentivize the appraiser to actually work and report the true value. Joint work with Shani Alokbi, David Sarne and Tomer Sharbaf.
Newcommer 4: Dr. Omer Lev, Ben-Gurion University of the Negev
Title: Gerrymandering and its Discontents
Abstract: In the past few years, the issue of gerrymandering has become one of the most commonly debated voting manipulations, particularly in the US. This type of manipulations allows electoral districts' geographical boundaries to be set in ways that helps a particular side win a plurality of districts representatives. We will discuss several works aimed at furthering our understanding of this issue: bounds on how much can districting can effect the outcome of an election; complexity analysis of gerrymandering: both theoretical and in practice; and effects of population distribution on gerrymandering power. Some unexpected results appear… Joint work (in different papers) with Yoram Bachrach, Allan Borodin, Yoad Lewenberg, Jeffrey S. Rosenschein, Nisarg Shah, Tyrone Strangway, and Yair Zick.
Industry: Gila Kamhi, General Motors
Title: Intelligent Vehicle Data Analytics to Put Human in the Loop
Position: Research Lab Group Manager, User Experience Technologies at General Motors.