The program on "Societal Concerns in Algorithms and Data Analysis" (SCADA 2018), we will hold weekly meetings at the Weizmann Institute. Each week, the agenda will include:

• 10:30-11:15: student presentation on a related topic
• 11:30-12:30: full talk
• 12:45-2:00: lunch, including an informal presentation and discussion

Location. The main talk will be in the lecture hall of the Wolfson Building, Weizmann Institute of Science (see map).

Parking: At any available spot on campus (please specify to guards at the gate that you are coming to an event of the computer science department).

Schedule

(See also the Google calendar, available once you join the Google group.)

October 18th

• Main Talk: Deploying Differential Privacy, Aleksandra Korolova, USC
• Lunch Talk: A New Approach to Fair Distribution of Welfare, Uri Feige, Weizmann Institute

Note: we will have an organizational meeting for students at 11AM (in the Wolfson lecture hall)

October 25th

• Main Talk: IBM Project Debator, Noam Slonim and Ranit Aharonov, IBM Research AI
• Lunch Talk: Fair Allocation through Competitive Equilibrium from Generic Incomes, Inbal Talgam-Cohen, Technion
• Student presentation: On The Turing Test, Lee Cohen, Tel Aviv University

November 1st

• Main Talk: Machine Learning in Security: Applications and Implications, Adi Shamir, Weizmann Institute
• Student presentation: Adversarial Leaning, Gal Yona, Weizmann Institute

There will be no lunch talk (but there will be lunch).

November 8th

• Main Talk: Formalizing the “Duty of Care” for self-driving cars, Shai Shalev-Shwartz, HUJI
• Lunch Talk: Questions about the structure of local differential privacy, Uri Stemmer, Ben Gurion University
• Student presentation: The Moral Machine, Moshe Shechner and Hanan Zaichyk, BGU

November 15th - NO MEETING

November 22nd

• Main Talk: c-single crossing Interdependent valuations, Amos Fiat, Tel Aviv University
• Lunch Talk: Hiring Under Diversity Constraints, Haim Kaplan, TAU
• Student presentation: Truthful Mechanisms for One-Parameter Agents, Gal Arnon, Weizmann

November 29th

• Main Talk: The Communication Complexity of Cake Cutting, Noam Nisan, HUJI
• Lunch Talk: Combinatorial Walrasian Equilibrium, Michal Feldman, TAU
• Student presentation: The Communication Complexity of Approximate Set Packing and Covering, Aaron Koolyk, HUJI

December 6th

• Main Talk: Ex Ante Fair Division of a random object, Herve Moulin, University of Glasgow
• Student presentation: On Fair Division, Itay Safran, Weizmann

There will be no lunch talk (but there will be lunch).

December 13th

• Main Talk: Fairness in Algorithmic Decision Making, Sampth Kannan, University of Pennsylvania
• Lunch Talk: Calibration for the (Computationally-Identifiable) Masses – empirical implementation in healthcare, Noa Dagan, Clalit Research Institute
• Student presentation: Fairness in Learning: Classic and Contextual Bandits, Roee Zamir, Weizmann

Organizers. Moni Naor and Guy Rothblum

Abstracts

October 18th: Deploying Differential Privacy

Aleksandra Korolova, USC

I'll start by role-playing the challenges of convincing industry practitioners to adopt differential privacy. I'll then describe RAPPOR, the first commercial deployment of differential privacy, and analyze the features that made it attractive for practical adoption (hint: change the trust model!). A tour of other deployments with recipes and open questions will follow:

- What were the flaws of Apple's implementation: bit.ly/APPLEDP

- What to do if your user base is smaller than Apple's and Google's: bit.ly/BLENDERDP

- How to deploy client-centric machine learning in a way that scales to modern cloud infrastructures: bit.ly/DDMLbySNAP

October 25th: IBM Project Debator

Noam Slonim and Ranit Aharonov, IBM Research AI

IBM Project Debater is the first -- and so far the only -- AI system that can debate humans on complex topics in a meaningful manner. In this talk we will describe this system, the challenges involved in developing it, and its impact on the rapidly emerging field of Computational Argumentation.

October 25th: Fair Allocation through Competitive Equilibrium from Generic Incomes

Inbal Talgam-Cohen, Technion

Two food banks catering to populations of different sizes with different needs must divide among themselves a donation of food items. What constitutes a “fair” allocation of the items among them? Competitive equilibrium from equal incomes (CEEI) is a classic solution to the problem of fair and efficient allocation of goods among agents. However, a CEEI is not guaranteed to exist when the items are indivisible, and does not accommodate agents who are a priori non-equal (like different-sized foodbanks). I will present some results from joint work with Moshe Babaioff and Noam Nisan, to appear in FAT*’19, on the existence and fairness properties of a relaxation called competitive equilibrium from generic incomes (CEGI).

November 1st: Machine Learning in Security: Applications and Implications

Adi Shamir, Weizmann Institute

In this talk I will survey the way machine learning research is affecting the field of security, and the way security research Is affecting the field of machine learning. After giving several examples of each type, I will discuss some of the latest developments In adversarial machine learning research, which are used by hackers to defeat security mechanisms based on regular machine learning techniques.

November 8th: Formalizing the “Duty of Care” for self-driving cars.

Shai Shalev-Shwartz, HUJI

The "Duty of Care” is a legal obligation requiring one to adhere to a standard of reasonable care while performing acts that could harm others. We propose a formal, mathematical interpretation of the duty of care in the context of "being cautious while driving”. The framework enables tackling moral questions in a formal way and is an example of a new research field which we call regulatory science.

Joint work with Shaked Shammah and Amnon Shashua.

November 22nd: c-single crossing Interdependent valuations

Amos Fiat, Tel Aviv University

We consider the goal of social welfare maximization where a single item is to be assigned to one of to n potential agents with interdependent values.

That is, each agent has her own private signal, and the valuation of each agent is a known function of all n private signals. This captures settings such as valuations for artwork, oil drilling rights, broadcast rights, and many more. In the interdependent value setting, all previous work has assumed a so-called single-crossing condition. Single-crossing means that the impact of agent i’s private signal, s_i, on her own valuation is greater than the impact of s_ii on the valuation of any other agent. It is known that without the single-crossing condition an efficient outcome cannot be obtained. We study welfare maximization for interdependent valuations through the lens of approximation.

We show that, in general, without the single-crossing condition, one cannot hope to approximate the optimal social welfare any better than the approximation given by assigning the item to a random bidder. Consequently, we introduce a relaxed version of single-crossing, c-single-crossing, parameterized by c ≥ 1, which means that the impact of s_i on the valuation of agent i is at least 1/c times the impact of s_i on the valuation of any other agent (c = 1 is single-crossing). Using this parameterized notion, we obtain a host of positive results. We also consider interdependent settings when valuations are concave and give improved results.

Joint work with Alon Eden, Michal Feldman, and Kira Goldner.

November 22nd: c-single crossing Interdependent valuations

Haim Kaplan, Tel Aviv University

We study the problem of hiring under diversity constraints: consider a company that plans a recruitment of k new employees under diversity constraints, where each constraint is of the form of a lower bound on the fraction of new employees that need to belong to some protected population (e.g., at least 20% of the new employees must be above the age of 50).

We assume a stochastic setting, where each candidate is sampled independently from a fixed unknown distribution D. During preprocessing, the algorithm has an access to a set of candidates sampled from D, which is used for training. After the preprocessing phase, the algorithm is given the input real-time set of candidates (which is sampled from the same distribution D), and its goal is to maximize the accumulated value of the k recruited employees, while satisfying the diversity constraints.

We consider algorithms that work in 2 stages, in the first stage we filter a small set of candidates that contains the optimal (or close to optimal) solution, which is them found in the second stage. We want to retain a small set of candidates following the first stage.

joint with Alon Cohen, Avinatan Hassidim, Yishay Mansour, and Shay Moran

November 29th: The Communication Complexity of Cake Cutting

Noam Nisan, HUJI

This talk concerns the well-studied model of "cake-cutting" for studying questions regarding notions of fair division of resources. We focus on discrete versions rather than using infinite-precision real values, specifically, focusing on the communication complexity. Using general discrete simulations of classical infinite-precision protocols (Robertson-Webb and moving-knife), we roughly partition the various fair-allocation problems into 3 classes: "easy" (constant number of rounds of logarithmic many bits), "medium" (poly-log total communication), and "hard".

Our main technical result concerns two of the "medium" problems (perfect allocation for 2 players and equitable allocation for any number of players) which we prove are not in the "easy" class. Our main open problem is to separate the "hard" from the "medium" classes.

Joint work with Simina Brânzei

December 6th: Ex Ante Fair Division of a random object

Herve Moulin, University of Glasgow

Ex Ante Fair Division of a random object

A Bogomolnaia, H Moulin, F Sandomirskyi

Objects arrive randomly, and must be allocated on the spot between a fixed set of beneficiaries. We explore the tradeoff between a concern for Fairness and the utilitarian measure of Efficiency:

• ex ante Fair Share guarantees to each agent, for each object, at least 1/n-th of his expected utility for the good (or at most 1/n-th of his expected disutility);
• Efficiency assigns goods to those who value them most (or bads to those who dislike them least).

Even a Bayesian manager (who knows in each period the full probability distribution of utility profiles) faces a steep (and well known) Price of Fairness: in the worst case implementing Fair Share allows her to capture only a 2/sqrt{n} fraction of the efficient surplus.

A Prior-free manager who only knows the expectation of individual utilities in each period (or just the ratios of these expectations), but neither the actual distribution in any period, nor the number of periods, ensures Fair Share by the simple Proportional rule: agents get the object with probabilities proportional to their (normalized) utilities (or disutilities).

We define the equally simple one-dimensional family of Top Heavy rules and show that they capture the optimal tradeoffs between Fair Share and Efficiency: any other prior-free rule meeting Fair Share is less efficient ex post (for every realization of utilities) than one of our rules. In particular the Proportional rule is substantially less efficient than one of our rules.

Moreover the Top Heavy rules pay the same Price of Fairness as the best Bayesian rules, and are often close to as efficient as the optimal Bayesian rule. If individual utilities are probabilistically independent, they capture a positive fraction of the utilitarian surplus, irrespective of the number of agents. Thus the collection of detailed statistical information for ex ante Fair Division is of little practical advantage.

December 13th: Fairness in Algorithmic Decision Making

Sampath Kannan, University of Pennsylvania

In this talk we survey some formulations of fairness requirements for decision making under uncertainty. We then discuss results from 3 recent papers:

1) Treating individuals fairly is not in conflict with long-term scientific learning goals if the population is sufficiently diverse.

2) When there is a pipeline of decisions, end-to-end fairness is impossible to achieve even in a very simple model.

3) Exploiting the knowledge acquired by others can unfairly advantage the free rider.

These papers are joint work with a number of co-authors:

Christopher Jung, Neil Lutz, Jamie Morgenstern, Aaron Roth, Bo Waggoner, Steven Wu, and Juba Ziani

December 13th: Calibration for the (Computationally-Identifiable) Masses –empirical implementation in healthcare

Noa Dagan, Clalit Research Institute

Prediction models are becoming an essential part of clinical practice. However, there are concerns regarding potential unfairness of the models towards groups which are underrepresented in the training dataset and thus might receive uncalibrated scores. The results of an empirical evaluation of the "calibration for the computationally-identifiable masses" algorithm will be presented. The algorithm was implemented on widely used risk models in healthcare, including the ACC/AHA 2013 model for cardiovascular events and the FRAX model for osteoporotic fractures.

Based on a joint work with Noam Barda, Gal Yona, Guy Rothblum and Eitan Bachmat.