Omer Tamuz

AAAI Conference 2018 Conference Paper

Non-Exploitable Protocols for Repeated Cake Cutting

• Omer Tamuz
• Shai Vardi
• Juba Ziani

We introduce the notion of exploitability in cut-and-choose protocols for repeated cake cutting. If a cut-and-choose protocol is repeated, the cutter can possibly gain information about the chooser from her previous actions, and exploit this information for her own gain, at the expense of the chooser. We de- fine a generalization of cut-and-choose protocols—forced-cut protocols—in which some cuts are made exogenously while others are made by the cutter, and show that there exist nonexploitable forced-cut protocols that use a small number of cuts per day: When the cake has at least as many dimensions as days, we show a protocol that uses a single cut per day. When the cake is 1-dimensional, we show an adaptive non-exploitable protocol that uses 3 cuts per day, and a nonadaptive protocol that uses n cuts per day (where n is the number of days). In contrast, we show that no non-adaptive non-exploitable forced-cut protocol can use a constant number of cuts per day. Finally, we show that if the cake is at least 2-dimensional, there is a non-adaptive non-exploitable protocol that uses 3 cuts per day.

SODA Conference 2018 Conference Paper

Quasi-regular sequences and optimal schedules for security games

• David Kempe 0001
• Leonard J. Schulman
• Omer Tamuz

We study security games in which a defender commits to a mixed strategy for protecting a finite set of targets of different values. An attacker, knowing the defender's strategy, chooses which target to attack and for how long. If the attacker spends time t at a target i of value α i, and if he leaves before the defender visits the target, his utility is t · a i; if the defender visits before he leaves, his utility is 0. The defender's goal is to minimize the attacker's utility. The defender's strategy consists of a schedule for visiting the targets; it takes her unit time to switch between targets. Such games are a simplified model of a number of real-world scenarios such as protecting computer networks from intruders, crops from thieves, etc. We show that optimal defender play for such security games, although played in continuous time, reduces to the solution of a combinatorial question regarding the existence of infinite sequences over a finite alphabet, with the following properties for each symbol i: (1) i constitutes a prescribed limiting fraction p i of the sequence. (2) The occurrences of i are spread apart close to evenly, in that the ratio of the longest to shortest interval between consecutive occurrences is bounded by a parameter K. We call such sequences K -quasi-regular; a 1-quasi-regular sequence is one in which the occurrences of each symbol form an arithmetic sequence. As we show, a 1-quasi-regular sequence ensures an optimal defender strategy for these security games: the intuition for this fact lies in the famous “inspection paradox. ” However, as we demonstrate, for K < 2 and general p i, K -quasi-regular sequences may not exist. Fortunately, this does not turn out to be an obstruction: we show that, surprisingly, 2-quasi-regular sequences also suffice for optimal defender play. What is more, even randomized 2-quasi-regular sequences suffice for optimality. We show that such sequences always exist, and can be calculated efficiently. Thus, we can ensure optimal defender play for these security games. The question of the least K for which deterministic K -quasi-regular sequences exist is fascinating. Using an ergodic theoretical approach, we proceed to show that deterministic 3-quasi-regular sequences always exist (and can be calculated efficiently). We also show that these deterministic 3-regular sequences give rise to a ≈ 1. 006-approximation algorithm for the defender's optimal strategy. For 2 ≤ K < 3 we do not know whether deterministic K -quasi-regular sequences always exist; however, when the pi are all small, improved bounds are possible, and in fact, (1 + ∊ )-quasi-regular deterministic sequences exist for any ∊ > 0 for sufficiently small p i.

ICML Conference 2013 Conference Paper

A Machine Learning Framework for Programming by Example

• Aditya Krishna Menon
• Omer Tamuz
• Sumit Gulwani
• Butler W. Lampson
• Adam Tauman Kalai

Learning programs is a timely and interesting challenge. In Programming by Example (PBE), a system attempts to infer a program from input and output examples alone, by searching for a composition of some set of base functions. We show how machine learning can be used to speed up this seemingly hopeless search problem, by learning weights that relate textual features describing the provided input-output examples to plausible sub-components of a program. This generic learning framework lets us address problems beyond the scope of earlier PBE systems. Experiments on a prototype implementation show that learning improves search and ranking on a variety of text processing tasks found on help forums.

JAAMAS Journal 2013 Journal Article

Majority dynamics and aggregation of information in social networks

• Elchanan Mossel
• Joe Neeman
• Omer Tamuz

Abstract Consider \(n\) individuals who, by popular vote, choose among \(q \ge 2\) alternatives, one of which is “better” than the others. Assume that each individual votes independently at random, and that the probability of voting for the better alternative is larger than the probability of voting for any other. It follows from the law of large numbers that a plurality vote among the \(n\) individuals would result in the correct outcome, with probability approaching one exponentially quickly as \(n \rightarrow \infty \). Our interest in this article is in a variant of the process above where, after forming their initial opinions, the voters update their decisions based on some interaction with their neighbors in a social network. Our main example is “majority dynamics”, in which each voter adopts the most popular opinion among its friends. The interaction repeats for some number of rounds and is then followed by a population-wide plurality vote. The question we tackle is that of “efficient aggregation of information”: in which cases is the better alternative chosen with probability approaching one as \(n \rightarrow \infty \)? Conversely, for which sequences of growing graphs does aggregation fail, so that the wrong alternative gets chosen with probability bounded away from zero? We construct a family of examples in which interaction prevents efficient aggregation of information, and give a condition on the social network which ensures that aggregation occurs. For the case of majority dynamics we also investigate the question of unanimity in the limit. In particular, if the voters’ social network is an expander graph, we show that if the initial population is sufficiently biased towards a particular alternative then that alternative will eventually become the unanimous preference of the entire population.

ICML Conference 2011 Conference Paper

Adaptively Learning the Crowd Kernel

• Omer Tamuz
• Ce Liu 0001
• Serge J. Belongie
• Ohad Shamir
• Adam Tauman Kalai