# Publications

Older papers 1997-2000 2001-2005 2006-2010 2011-

back to top## 2011-Latest

Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functionsby P. Gopalan, N. Nisan, R. A. Servedio, K. Talwar, and A. Wigderson. ITCS 2016. Welfare Maximization with Limited Interaction

by N. Alon, N. Nisan, R. Raz and O. Weinstein. FOCS 2015. Public Projects, Boolean Functions, and the Borders of Border's Theorem

by P. Gopalan, N. Nisan, and T. Roughgarden. EC 2015. Here is a video of a talk given at Microsoft, 2015. 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, 2014. 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 Agencyby 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. 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. Here is a Video of a talk at Israeli Theory Day 2011. 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 Biddersby 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. Here is a video of a talk in Google, 2007. 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.