Noam Nisan
HomeBooksPublicationsCoursesBlog

Contact Information

School of Computer Science and Engineering, Hebrew University of Jerusalem. Email: noam(at)cs.huji.ac.il

Publications

back to top

2011-Latest

A Stable Marriage Requires Communication
by Y. Gonczarowski, N. Nisan, R. Ostrovsky and W. Rosenbaum. SODA 2015.
Sampling and Representation Complexity of Revenue Maximization
by S. Dughmi, L. Han, and N. Nisan. WINE 2014.
On the Efficiency of the Walrasian Mechanism
by M. Babaioff, B. Lucier, N. Nisan, and R. Paes Leme. ACM EC 2014
Economic Efficiency Requires Interaction
by S. Dobzinski, N. Nisan, and S. Oren. STOC 2014. An Experimental Evaluation of Bidders' Behavior in Ad Auctions
by G, Noti, N. Nisan, and I. Yaniv. WWW 2014.
Price Competition in Online Combinatorial Markets
by M. Babaioff, N. Nisan, and R. Paes Leme. WWW 2014.
Survey: Algorithmic Mechanism Design (through the lens of multi-unit auctions)
by N. Nisan. Handbook of Game Theory, IV.
The Query Complexity of Correlated Equilibria
by S. Hart and N. Nisan. SAGT 2013.
Bertrand Networks
by M. Babaioff, B. Lucier, and N. Nisan. EC 2013.
The Menu-Size Complexity of Auctions
by S. Hart and N. Nisan. EC 2013.
The AND-OR Game: Equilibrium Characterization
by A. Hassidim, H. Kalpan, Y. Mansour, and N. Nisan. WINE 2012.
Incentive Compatible Two Player Cake Cutting
by A. Maya and N. Nisan. WINE 2012.
Approximate Revenue Maximization with Multiple Items
by S. Hart and N. Nisan. EC 2012.
Doubleclick Ad Exchange Auction
by Y. Mansour, S. Muthukrishnan and N. Nisan. arXiv, 2012.
Fair Allocation without Trade
by A. Gutman and N. Nisan. AAMAS 2012.
Sketching Valuation Functions
by A. Badanidiyuru, S. Dobzinski, H. Fu, R. Kleinberg, N. Nisan and T. Roughgarden. SODA 2012.
Best Response Auctions
by N. Nisan, M. Schapira, G. Valiant, and A. Zohar. EC 2011.
Non-Price Equilibria in Markets of Discrete Goods
by A. Hassidim, H. Kaplan, Y. Mansour, and N. Nisan. EC 2011.
Multi-unit Auctions: Beyond Robetrs
by S. Dobzinski and N. Nisan. EC 2011.
Best Response Mechanisms
by N. Nisan, M. Schapira, G. Valiant, and A. Zohar. ICS 2011.
back to top

2006-2010

Free Riding and Free Labor in Combinatorial Agency
by M. Babaioff, M. Feldman, and N. Nisan. SAGT 2009.
A Modular approach to Roberts' Theorem
by S. Dobzinski and N. Nisan. SAGT 2009.
Google's auction for TV ads
by N. Nisan et al. Invited talk in EURO 2009, ICALP 2009, SAGT 2009, SODA 2010, and COLT 2010. Paper appeared in proceedings of ICALP 2009. Here are the talk slides (ppt).
Asynchronous Best-Reply Dynamics
by N. Nisan, M. Schapira, and A. Zohar. WINE 2008.
FairplayMP A System for Secure Multi-Party Computation
by A. Ben-David, N. Nisan, and B. Pinkas. ACM CCS 2008.
Theory Research at Google
by G. Aggarwal, N. Ailon, F. Constantin, E. Even-Dar, J. Feldman, G. Frahling, M. R. Henzinger, S. Muthukrishnan, N. Nisan, M. Pal, M. Sandler, and A. Sidiropoulos. SIGACT news, 2008.
Multi-unit Auctions with budget limits
by S. Dobzinski, R. Lavi, and N. Nisan. FOCS 2008.
A Quantitative Version of the Gibbard-Satterthwaite theorem for Three Alternatives
by E. Friedgut, G. Kalai, N. Keller and N. Nisan. Preliminary version titled Elections can be Manipulated Often appeared in FOCS 2008.
Introduction to Mechanism Design (for Computer Scientists)
by N. Nisan. In Algorithmic Game Theory by N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani, editors.
Combinatorial Auctions (a survey)
by L. Blumrosen and N. Nisan. In Algorithmic Game Theory, by N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani, editors.
Mechanisms for Multi-unit Auctions
by S. Dobzinski and N. Nisan. EC 2007.
Limitations of VCG-based Mechanisms
by S. Dobzinski and N. Nisan. STOC 2007.
A note on the computational hardness of Evolutionary stable strategies
by N. Nisan. ECCC technical report, 2006.
Mixed Strategies in Combinatorial Agency
by M. Babaioff, M. Feldman, and N. Nisan. WINE 2006.
Combinatorial Agency
by M. Babaioff, M. Feldman, and N. Nisan. EC 2006.
Truthful Randomized Mechanisms for Combinatorial Auctions
by S. Dobzinski, N. Nisan, and M. Schapira. STOC 2006.
Weak Monotonicity characterizes deterministic dominant strategy implementation.
by S. Bikhchandani, S. Chatterji, R. Lavi, A. Mu'alem, N. Nisan, and A. Sen. To appear in Econometrica. There is also some supporting material.
Exponential Communication Inefficiency of Demand Queries
by N. Nisan and I. Segal. TARK 2005.
Bidding Languages for Combinatorial Auctions
by N. Nisan. In Combinatorial Auctions by Cramton, Shoham and Steinberg (eds.), 2005.
The Communication Requirements of Efficient Allocations and Supporting Prices
by N. Nisan and I. Segal. Final version in JET, 2006. We also have a short CS-friendly exposition of the main result. Preliminary version presented in DIMACS workshop on on Computational Issues in Game Theory and Mechanism Design, 2001.
back to top

2001-2005

Approximation Algorithms for Combinatorial Auctions with Complement-free Bidders
by S. Dobzinski, N. Nisan, and M. Schapira. STOC 2005. Preliminary version presented in DIMACS Workshop on Computational Issues in Auction Design, 2004.
On the Computational Power of Demand Queries
by L. Blumrosen and N. Nisan. Siam Journal of Computation, 2009. Part I of an extended abstract in EC 2005. Preliminary version presented in the FCC combinatoiral bidding conference, 2003.
Informational limitations of ascending combinatorial auctions
by L. Blumrosen and N. Nisan. JET, 2010. Extension of part II of an extended abstract in EC 2005. Preliminary version presnted in Stanford Institute on Theoretical Economics Workshop on Bounded Rationality in the Design of Markets and Organizations, 2004.
Online Ascending Auctions for Gradually Expiring Goods
by R. Lavi and N. Nisan. SODA 2005. Preliminary version presented in AGATE 2004.
Mechanisms for a Spatially Distributed Market
by M. Babaioff, N. Nisan, and E. Pavlov. EC 2004.
Fairplay: A Secure Two Party Computation System
by D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Usenix Security Symposium, 2004.
Incentive Compatible Multi-Unit Combinatorial Auctions
by Y. Bartal, R. Gonen, and N. Nisan. TARK 2003. Preliminary version presented in Dagstuhl seminar on electronic market design 2002.
Towrads a Characterization of Truthful Combinatorial Auctions
by R. Lavi, A. Mu'alem, and N. Nisan. FOCS 2003. Preliminary version presented in Dagstuhl seminar on Algorithmic Game Theory and the Internet 2003.
Multi-Player and Multi-Round Auctions with Severely Bounded Communication
by L. Blumrosen, N. Nisan, and I. Segal. ESA 2003.
The Communication Complexity of Approximate Set Packing and Covering,
by N.Nisan. ICALP 2002.
Truthful Approximation Mechanisms for Restricted Combinatorial Auctions
by A. Mu'alem and N. Nisan. AAAI 2002.
Auctions with Severely Bounded Communication. (Also available in pdf format)
by L. Blumrosen and N. Nisan. FOCS 2002.
OnLine Markets for Distributed Object Services: the MAJIC system
by L. Levy, L. Blumrosen, and N. Nisan. USITS 2001.
An Efficient Approximate Allocation Algorithm for Combinatorial Auctions.
by E. Zurel and N. Nisan. EC 2001. The (unsupported) C++ source files for the algorithm are here.
Combinatorial Auctions with Decreasing Marginal Utilities (Also available in pdf format)
by B. Lehmann, D. Lehmann, and N. Nisan. EC 2001. Final version in GEB, 2006.
Concurrent Auctions Across the Supply Chain
by M. Babaioff and N. Nisan. EC 2001.
back to top

1997-2000

Bidding and Allocation in Combinatorial Auctions (Also available in pdf format)
by N. Nisan. Appeared in EC 2000. Preliminary Version presented in the 1999 NWU Microeconomics Workshop, and copies of the slides are available in power point format.
Competitive Analysis of Online Auctions
by R. Lavi and N. Nisan. EC 2000.
Computationally Feasable VCG Mechanisms
by N. Nisan and A. Ronen. JAIR, 2007. Preliminary version appeared in EC 2000.
Algorithms for Selfish Agents -- Mechanism Design for Distributed Computation
by N. Nisan. STACS 1999.
Algorithmic Mechanism Design
by N. Nisan and A. Ronen. Expanded version of the paper that appeared in STOC 1999.
Globally Distributed Computation over the Internet -- The POPCORN Project
by N. Nisan, S. London, O. Regev, and N. Camiel. ICDCS 1998. Preliminary poster version apperaed in WWW6, 1997.
The Popcorn Market: Online Markets for Computational Resources.
by O. Regev and N. Nisan. ICE 1998.
back to top

Older Papers

Some of my older papers on theoretical computer science can be found here.

Written and designed by Tali Gutman ©