Approximate Privacy: Foundations and Quantification (2009)
Feigenbaum, Joan, Jaggard, Aaron D., Schapira, Michael
Increasing use of computers and networks in business, government, recreation, and almost all aspects of daily life has led to a proliferation of online sensitive data about individuals and...
Towards a Unified Approach to (In)Decision: Routing, Games, Circuits, Consensus, and Beyond (2009)
Jaggard, Aaron D., Schapira, Michael, Wright, Rebecca N.
In this paper, we explore a unified treatment of the difficulty of reaching a decision in constrained distributed computing environments in which there is a lack of global coordination or knowledge....
Neighbor-Specific BGP: More Flexible Routing Policies While Improving Global Stability (2009)
Wang, Yi, Schapira, Michael, Rexford, Jennifer
Please Note: This document was written to summarize and facilitate discussion regarding (1) the benefits of changing the way BGP selects routes to selecting the most preferred route allowed by export...
Mossel, Elchanan, Papadimitriou, Christos, Schapira, Michael, Singer, Yaron
The existence of incentive-compatible computationally-efficient protocols for combinatorial auctions with decent approximation ratios is the paradigmatic problem in computational mechanism design. It...
Interdomain routing and games (2009)
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...
The Strategic Justification for BGP (Working Paper) (2008)
Hagay Levin, Michael Schapira, Aviv Zohar
The Internet consists of many administrative domains, or Autonomous Systems (ASes), each owned by an economic entity (Microsoft, AT&T, The Hebrew University, etc.). The task of ensuring...
Interdomain routing and games (2008)
Levin, Hagay, Schapira, Michael, Zohar, Aviv
We present a game-theoretic model that captures many of the intricacies of \emph{interdomain routing} in today's Internet. In this model, the strategic agents are source nodes located on a network,...
From the margins to the majority: the possibility of a liberal education in liquid times (2008)
Liberal philosophers of education often concentrate on issues of accommodation and recognition coming from minority cultures within pluralistic societies. While this remains an important task, I...
From the margins to the majority: the possibility of a liberal education in liquid times (2008)
Liberal philosophers of education often concentrate on issues of accommodation and recognition coming from minority cultures within pluralistic societies. While this remains an important task, I...
Incentive-Compatible Interdomain Routing (2007)
Feigenbaum, Joan, Ramachandran, Vijay, Schapira, Michael
The routing of traffic between Internet domains, or Autonomous Systems (ASes), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). Using BGP, autonomous...
Setting lower bounds on truthfulness (2007)
We present and discuss general techniques for proving inapproximability results for truthful mechanisms. We make use of these techniques to prove lower bounds on the approximability of several...
Tight information-theoretic lower bounds for combinatorial auctions (2007)
Vahab Mirrokni, Michael Schapira, Jan Vondrák
We provide tight information-theoretic lower bounds for the welfare maximization problem in combinatorial auctions. In this problem the goal is to partition m items between k bidders in a way that...
Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions (2007)
Vahab Mirrokni, Michael Schapira, Jan Vondrák
We provide tight information-theoretic lower bounds for the welfare maximization problem in combinatorial auctions. In this problem the goal is to partition m items between k bidders in a way that...
The Strategic Justification for BGP (2006)
Levin, Hagay, Schapira, Michael, Zohar, Aviv
The Internet consists of many administrative domains, or \emph{Autonomous Systems} (ASes), each owned by an economic entity (Microsoft, AT\&T, The Hebrew University, etc.). The task of ensuring...
Truthful randomized mechanisms for combinatorial auctions (2006)
Shahar Dobzinski, Noam Nisan, Michael Schapira
Abstract We design two computationally-eOEcient incentive-compatible mechanisms for combinatorial auctions with general bidder preferences. Both mechanisms are randomized, and are incentivecompatible...
Truthful randomized mechanisms for combinatorial auctions (2006)
Shahar Dobzinski, Noam Nisan, Michael Schapira
Abstract We design two computationally-efficient incentive-compatible mechanisms for combinatorialauctions with general bidder preferences. Both mechanisms are randomized, and are incentivecompatible...
Joan Feigenbaum, Vijay Ramachandran, Michael Schapira, Joan Feigenbaum, Michael Schapira, Vijay Ramachandran
The routing of traffic between Internet domains, or Autonomous Systems (ASes), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP) [17]. Using BGP,...
Approximation algorithms for combinatorial auctions with complement-free bidders (2005)
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...
Shahar Dobzinski, Michael Schapira
Abstract We study the allocation problem in combinatorial auctions with k duplicates of each item. We exhibit a min ( nk, O(m
Approximation algorithms for combinatorial auctions with complement-free bidders (2005)
Shahar Dobzinski, Noam Nisan, Michael Schapira
Abstract 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...
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...
The Strategic Justification for BGP
Levin, Hagay, Schapira, Michael, Zohar, Aviv
The Internet consists of many administrative domains, or \emph{Autonomous Systems} (ASes), each owned by an economic entity (Microsoft, AT\&T, The Hebrew University, etc.). The task of ensuring...
Levin, Hagay, Schapira, Michael, Zohar, Aviv
We present a game-theoretic model that captures many of the intricacies of \emph{interdomain routing} in today's Internet. In this model, the strategic agents are source nodes located on a network,...