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 and Jennifer Rexford. 2009.
- Routing Along DAGs
By Junda Liu, P. Brighten Godfrey, Michael Schapira, Martin Casado and Scott Shenker. 2009.
- Incentive
-Compatibility and Dynamics of Congestion Control
By P. Brighten Godfrey, Michael Schapira, Aviv Zohar and Scott Shenker. 2009.
- Beyond BGP Safety: From Backup
Routing to Misconfigurations
Roee Engelberg and Michael Schapira. Submitted, 2009.
- Approximate Privacy: Foundations and
Quantification
By Joan Feigenbaum, Aaron Jaggard and Michael Schapira. 2009.
- Towards a
Unified Approach to (In)Decision: Routing, Games, Circuits, Consensus and
Beyond
By Aaron D. Jaggard, Michael Schapira and Rebecca N. Wright. 2009.
- Best-Reply
Mechanisms
By Noam Nisan, Michael Schapira, Gregory Valiant and Aviv Zohar.
Presented at INFORMS 2007.
Book
Chapter
- Distributed
Algorithmic Mechanism Design
By Joan Feigenbaum, Michael Schapira and Scott Shenker.
In the book Algorithmic Game Theory, editors: Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani,
Cambridge University Press, 2007.
Internet
Protocols: Algorithmic Foundations and New Schemes
- Neighbor-Specific BGP: More Flexible Routing Policies
While Improving Global Stability (slides)
By Yi Wang, Michael Schapira and Jennifer Rexford. - In
the proceedings of SIGMETRICS
09.
- 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. Invited for publication in SIAM Journal on Computing (SICOMP) SpecialIssue on selected papers from STOC 08 (pending minor revisions).
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.
Journal version in preparation.
Mechanism
Design: Possibilies 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. - Presented
at BAGT
06.
- See Inapproximability
for VCG-based Combinatorial Auctions (merged)
By Dave Buchfuhrer et al. To appear 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.
Presented at GAMES 08.
- Mechanism
Design Over Discrete Domains (slides)
By Ahuva Mu'alem and Michael Schapira. - In
the proceedings of EC 08.
Presented at GAMES
08.
- 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 (pending).
- 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