Michael Schapira

ICML Conference 2019 Conference Paper

A Deep Reinforcement Learning Perspective on Internet Congestion Control

• Nathan Jay
• Noga H. Rotman
• Philip Brighten Godfrey
• Michael Schapira
• Aviv Tamar

We present and investigate a novel and timely application domain for deep reinforcement learning (RL): Internet congestion control. Congestion control is the core networking task of modulating traffic sources’ data-transmission rates to efficiently utilize network capacity, and is the subject of extensive attention in light of the advent of Internet services such as live video, virtual reality, Internet-of-Things, and more. We show that casting congestion control as RL enables training deep network policies that capture intricate patterns in data traffic and network conditions, and leverage this to outperform the state-of-the-art. We also highlight significant challenges facing real-world adoption of RL-based congestion control, including fairness, safety, and generalization, which are not trivial to address within conventional RL formalism. To facilitate further research and reproducibility of our results, we present a test suite for RL-guided congestion control based on the OpenAI Gym interface.

STOC Conference 2015 Conference Paper

Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension

• Amit Daniely
• Michael Schapira
• Gal Shahaf

UAI Conference 2013 Conference Paper

Pay or Play

• Sigal Oren
• Michael Schapira
• Moshe Tennenholtz

We introduce the class of pay or play games, which captures scenarios in which each decision maker is faced with a choice between two actions: one with a fixed payoff and another with a payoff dependent on others’ selected actions. This is, arguably, the simplest setting that models selection among certain and uncertain outcomes in a multi-agent system. We study the properties of equilibria in such games from both a game-theoretic perspective and a computational perspective. Our main positive result establishes the existence of a semi-strong equilibrium in every such game. We show that although simple, pay or play games contain well-studied environments, e. g. , vaccination games. We discuss the interesting implications of our results for these environments.

TCS Journal 2012 Journal Article

On communication protocols that compute almost privately

• Marco Comi
• Bhaskar DasGupta
• Michael Schapira
• Venkatakumar Srinivasan

We further investigate and generalize the approximate privacy model recently introduced by Feigenbaum et al. (2010) [7]. We explore the privacy properties of a natural class of communication protocols that we refer to as “dissection protocols”. Informally, in a dissection protocol the communicating parties are restricted to answering questions of the form “Is your input between the values α and β (under a pre-defined order over the possible inputs)? ”. We prove that for a large class of functions, called tiling functions, there always exists a dissection protocol that provides a constant average-case privacy approximation ratio for uniform or “almost uniform” probability distributions over inputs. To establish this result we present an interesting connection between the approximate privacy framework and basic concepts in computational geometry. We show that such a good privacy approximation ratio for tiling functions does not, in general, exist in the worst case. We also discuss extensions of the basic setup to more than two parties and to non-tiling functions, and provide calculations of privacy approximation ratios for two functions of interest.

SODA Conference 2010 Conference Paper

Inapproximability for VCG-Based Combinatorial Auctions

• David Buchfuhrer
• Shaddin Dughmi
• Hu Fu 0001
• Robert Kleinberg
• Elchanan Mossel
• Christos H. Papadimitriou
• Michael Schapira
• Yaron Singer

STOC Conference 2008 Conference Paper

Interdomain routing and games

• Hagay Levin
• Michael Schapira
• Aviv Zohar

We present a game-theoretic model that captures many of the intricacies of interdomain routing in today's Internet. In this model, the strategic agents are source nodes located on a network, who aim to send traffic to a unique destination node. The interaction between the agents is dynamic and complex -- asynchronous, sequential, and based on partial information. Best-reply dynamics in this model capture crucial aspects of the interdomain routing protocol de facto, namely the Border Gateway Protocol (BGP).

FOCS Conference 2008 Conference Paper

On the Hardness of Being Truthful

• Christos H. Papadimitriou
• Michael Schapira
• Yaron Singer

The central problem in computational mechanism design is the tension between incentive compatibility and computational efficiency. We establish the first significant approximability gap between algorithms that are both truthful and computationally-efficient, and algorithms that only achieve one of these two desiderata. This is shown in the context of a novel mechanism design problem which we call the combinatorial public project problem (cppp). cpppis an abstraction of many common mechanism design situations, ranging from elections of kibbutz committees to network design. Our result is actually made up of two complementary results -- one in the communication-complexity model and one in the computational-complexity model. Both these hardness results heavily rely on a combinatorial characterization of truthful algorithms for our problem. Our computational-complexity result is one of the first impossibility results connecting mechanism design to complexity theory; its novel proof technique involves an application of the Sauer-Shelah Lemma and may be of wider applicability, both within and without mechanism design.

SODA Conference 2007 Conference Paper

Setting lower bounds on truthfulness: extended abstract

• Ahuva Mu'alem
• Michael Schapira

SODA Conference 2006 Conference Paper

An improved approximation algorithm for combinatorial auctions with submodular bidders

• Shahar Dobzinski
• Michael Schapira

STOC Conference 2006 Conference Paper

Truthful randomized mechanisms for combinatorial auctions

• Shahar Dobzinski
• Noam Nisan
• Michael Schapira

We design two computationally-efficient incentive-compatible mechanisms for combinatorial auctions with general bidder preferences. Both mechanisms are randomized, and are incentive-compatible in the universal sense. This is in contrast to recent previous work that only addresses the weaker notion of incentive compatibility in expectation. The first mechanism obtains an O(√m)-approximation of the optimal social welfare for arbitrary bidder valuations -- this is the best approximation possible in polynomial time. The second one obtains an O(log 2 m)-approximation for a subclass of bidder valuations that includes all submodular bidders. This improves over the best previously obtained incentive-compatible mechanism for this class which only provides an O(√ m)-approximation.

STOC Conference 2005 Conference Paper

Approximation algorithms for combinatorial auctions with complement-free bidders

• Shahar Dobzinski
• Noam Nisan
• Michael Schapira

We exhibit three approximation algorithms for the allocation problem in combinatorial auctions with complement free bidders. The running time of these algorithms is polynomial in the number of items $m$ and in the number of bidders n, even though the "input size" is exponential in m. The first algorithm provides an O(log m) approximation. The second algorithm provides an O(√ m) approximation in the weaker model of value oracles. This algorithm is also incentive compatible. The third algorithm provides an improved 2-approximation for the more restricted case of " XOS bidders", a class which strictly contains submodular bidders. We also prove lower bounds on the possible approximations achievable for these classes of bidders. These bounds are not tight and we leave the gaps as open problems.