Michael Schapira – מיכאל שפירא

 

 

 

 

I am a postdoc at Yale University and UC Berkeley, co-advised by Prof. Joan Feigenbaum and Prof. Scott Shenker.
I completed a Ph.D. at the Hebrew University of Jerusalem under the supervision of Prof. Noam Nisan.

 

Research Interests:

1.      algorithmic foundations of networking. I am interested in the design and analysis of Internet protocols. My research focuses on (a) understanding existing Internet protocols and the fundamental tradeoffs that should guide the design of the future Internet, and (b) fixing today's protocols and devising long-term solutions that take us beyond what incremental fixes to these protocols can achieve.

2.      algorithmic game theory. I am interested in the interface of computer science, game theory and economic theory. My  research explores the possibility/impossibility borderline of incentive-compatible computation.

Publications

Working Papers

• Putting BGP on the Right Path: A Case for Next-Hop Routing
  By Michael Schapira, Yaping Zhu and Jennifer Rexford. Submitted, 2010.
  To be presented at the DIMACS/CCICADA Workshop on Secure Routing (2010).

 

• Routing Along DAGs
  By Junda Liu, P. Brighten Godfrey, Michael Schapira, Martin Casado, Jennifer Rexford and Scott Shenker. Submitted, 2010.
  
  
• How Secure are Secure Interdomain Routing Protocols?
  By Sharon Goldberg, Michael Schapira, Pete Hummon and Jennifer Rexford. Submitted, 2010.
  
  
• Approximate Privacy: Foundations and Quantification
  By Joan Feigenbaum, Aaron Jaggard and Michael Schapira. Submitted, 2010. Based on:
1. Approximate Privacy: Foundations and Quantification (arxiv)
2. Approximate Privacy: PARs for Set Problems (arxiv)
   
   
• Computation and Incentives in Combinatorial Public Projects
  By Dave Buchfuhrer, Michael Schapira and Yaron Singer. Submitted, 2010.
  
  
• Towards a Unified Approach to (In)Decision: Routing, Games, Circuits, Consensus and Beyond
  By Aaron D. Jaggard, Michael Schapira and Rebecca N. Wright. In preparation, 2010.

 

• Best-Reply Mechanisms
  By Noam Nisan, Michael Schapira, Gregory Valiant and Aviv Zohar. In preparation, 2010.
  Presented at INFORMS 2007.

Book Chapter

• Distributed Algorithmic Mechanism Design
  By Joan Feigenbaum, Michael Schapira and Scott Shenker.
  Chapter 14 of the book Algorithmic Game Theory, editors: Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani,
  Cambridge University Press, 2007.

Internet Protocols

• Incentive -Compatibility and Dynamics of Congestion Control
  By P. Brighten Godfrey, Michael Schapira, Aviv Zohar and Scott Shenker. To appear in the proceedings of SIGMETRICS 10.
  
  
• Neighbor-Specific BGP: More Flexible Routing Policies While Improving Global Stability (slides)
  By Yi Wang, Michael Schapira and Jennifer Rexford.
1. In the proceedings of SIGMETRICS 09.
2. See also this write-up for practitioners.
   
   
• Searching for Stability in Interdomain Routing (slides)
  By Rahul Sami, Michael Schapira and Aviv Zohar. In the proceedings of INFOCOM 09.
  
  
• Interdomain Routing and Games (slides)
  By Hagay Levin, Michael Schapira and Aviv Zohar. In the proceedings of STOC 08. To appear in SIAM Journal on Computing (SICOMP) Special Issue on selected papers from STOC 08.
  Presented at INFORMS 2007, BISFAI 2007, DIMACS Workshop: The Boundary between Economic Theory and Computer Science (2007) and DIMACS Workshop: On Secure Internet Routing (2008).
  
  
• Asynchronous Best-Reply Dynamics
  By Noam Nisan, Michael Schapira and Aviv Zohar. In the proceedings of WINE 08.
  Presented at INFORMS 2007.
  
  
• Incentive-Compatible Interdomain Routing (slides)
  By Joan Feigenbaum, Vijay Ramachandran and Michael Schapira. In the proceedings of EC 06.
  Submitted to Distributed Computing, 2009.

Mechanism Design: Possibilities and Impossibilities

• VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension (slides)
  By Elchanan Mossel, Christos Papadimitriou, Michael Schapira and Yaron Singer.
1. Presented at BAGT 06.
2. See Inapproximability for VCG-based Combinatorial Auctions  (merged)
   By Dave Buchfuhrer et al. In the proceedings of SODA 10.
   
   
• On the Hardness of Being Truthful (slides)
  By Christos Papadimitriou, Michael Schapira and Yaron Singer. In the proceedings of FOCS 08.
  
  
• Informational Overhead of Incentive Compatibility (slides)
  By Moshe Babaioff, Liad Blumrosen, Moni Naor and Michael Schapira. In the proceedings of EC 08. Submitted to Games and Economic Behavior (GEB), 2009.
  Presented at GAMES 08.
  
  
• Mechanism Design Over Discrete Domains (slides)
  By Ahuva Mu'alem and Michael Schapira.
1. In the proceedings of EC 08. Presented at GAMES 08.
2. See also short exposition of the motivation and some of the results in Characterizing Truthfulness in Discrete Domains, SIGecom Exchanges, June 2008.
   
   
• Setting Lower Bounds on Truthfulness (slides)
  By Ahuva Mu'alem and Michael Schapira. In the proceedings of SODA 07.
  Presented at AGATE 06.

Combinatorial Auctions (and Combinatorial Public Projects)

• Inapproximability of Combinatorial Public Projects (slides)
  By Michael Schapira and Yaron Singer. In the proceedings of WINE 08.
  
  
• Tight Information-Theoretic Lower Bounds For Welfare Maximization in Combinatorial Auctions
  By Vahab Mirrokni, Michael Schapira and Jan Vondrak. In the proceedings of EC 08.
  
  
• Bayesian Combinatorial Auctions (slides)
  By George Christodoulou, Annamaria Kovacs and Michael Schapira. In the proceedings of ICALP 08.
  
  
• Truthful Randomized Mechanisms for Combinatorial Auctions (slides)
  By Shahar Dobzinski, Noam Nisan and Michael Schapira. In the proceedings of STOC 06. Invited for publication in JCSS Special Issue on Knowledge  Representation and Reasoning. Submitted, 2009.
  
  
• An Improved Approximation Algorithm for Combinatorial Auctions with Submodular Bidders (slides)
  By Shahar Dobzinski and Michael Schapira. In the proceedings of SODA 06.
  
  
• Approximation Algorithms for Combinatorial Auctions with Complement Free Bidders (poster) (slides)
  By Shahar Dobzinski, Noam Nisan and Michael Schapira. In the proceedings of STOC 05. To appear in Mathematics of Operations Research.
  Presented at DIMACS Workshop on Computational Issues in Auction Design, 2004.

Unpublished Manuscripts

• Optimal Upper and Lower Approximation Bounds for k-Duplicates Combinatorial Auctions
  By Shahar Dobzinski and Michael Schapira.
  A technical report, Leibniz Center for Research in Computer Science, 2005.

Ph.D. Thesis

The Economics of Internet Protocols
By Michael Schapira, Hebrew University of Jerusalem.
Ph.D. committee: Prof. Sergiu Hart, Prof. Noam Nisan (advisor) and Prof. Jeff Rosenschein.

 

Academic Service

Program committee: NetEcon 2009, EC 2010.

 

e-mail address: first name dot last name @yale.edu