Noam Nisan's Papers

  • 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 proceedings of ICALP 2009.

  • 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. P´al, M. Sandler, and A. Sidiropoulos. SIGACT news, 2008.

  • Multi-unit Auctions with budget limits by S. Dobzinski, R. Lavi, and N. Nisan. FOCS 2008.

  • Elections can be Manipulated Often by E. Friedgut, G. Kalai, and N. Nisan. 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. Working paper, 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.

  • 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 Iterative Auctions I: Demand Queries
    by L. Blumrosen and N. Nisan. Part I of an extended abstract in EC 2005. Preliminary version presented in the FCC combinatoiral bidding conference, 2003.

  • On the Computational Power of Iterative Auctions II: Ascending Auctions
    by L. Blumrosen and N. Nisan. 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.

  • 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.

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