On the Computational Power of Demand Queries (2009)
We study the computational power of iterative combinatorial auctions. Most existing iterative combinatorial auctions are based on repeatedly suggesting prices for bundles of items, and querying the...
Elections Can be Manipulated Often Draft – Comments Welcome (2009)
Ehud Friedgut, Gil Kalai, Noam Nisan
The Gibbard-Satterthwaite theorem states that every non-trivial voting method between at least 3 alternatives can be strategically manipulated. We prove a quantitative version of the...
Two Simplified Proofs for Roberts ’ Theorem (2009)
Roberts (1979) showed that every social choice function that is ex-post implementable in private value settings must be weighted VCG, i.e. it maximizes the weighted social welfare. This paper...
Mixed Strategies in Combinatorial Agency [Extended Abstract] (2009)
Moshe Babaioff, Michal Feldman, Noam Nisan
Abstract. We study a setting where a principal needs to motivate a team of agents whose combination of hidden efforts stochastically determines an outcome. In a companion paper we devise and study a...
Algorithmic Mechanism Design contact: (2009)
Noam Nisan, Amir Ronen Y, Amir Ronen
We consider algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are...
Abstract Combinatorial Agency (2008)
Moshe Babaioff, Michal Feldman, Noam Nisan
We study a combinatorial variant of the classical principal-agent problem. In our setting a principal must motivate a team of strategic agents to exert costly effort on his behalf, but their actions...
Noam Nisan, Tim Roughgarden, Éva Tardos, Vijay Vazirani, S. Lahaie, D. Pennock, ...
page 4
Algorithmic Mechanism Design contact: (2008)
Noam Nisan, Amir Ronen Y, Amir Ronen
We consider algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are...
Truthful approximation mechanisms for restricted combinatorial auctions (2008)
When attempting to design a truthful mechanism for a computationally hard problem such as combinatorial auctions, one is faced with the problem that most efficiently computable heuristics can not be...
Mixed Strategies in Combinatorial Agency (2008)
Moshe Babaioff, Michal Feldman, Noam Nisan
Abstract. We study a setting where a principal needs to motivate a team of agents whose combination of hidden efforts stochastically determines an outcome. In a companion paper we devise and study a...
Mechanisms for a Spatially Distributed Market 1 (2008)
Moshe Babaioff, Noam Nisan, Elan Pavlov
We consider the problem of a spatially distributed market with strategic agents. In this problem a single good is traded in a set of independent markets, where shipment between markets is possible...
Mixed Strategies in Combinatorial Agency (2008)
Moshe Babaioff, Michal Feldman, Noam Nisan
Abstract. We study a setting where a principal needs to motivate a team of agents whose combination of hidden efforts stochastically determines an outcome. In a companion paper we devise and study a...
Abstract Pseudorandomness for Network Algorithms (2008)
Russell Impagliazzo, Noam Nisan, Avi Wigderson
We define pseudorandom generators for Yao’s twoparty communication complexity model and exhibit a simple construction, based on expanders, for it. We then use a recursive composition of such...
Mixed Strategies in Combinatorial Agency [Extended Abstract] (2008)
Moshe Babaioff, Michal Feldman, Noam Nisan
Abstract. We study a setting where a principal needs to motivate a team of agents whose combination of hidden efforts stochastically determines an outcome. In a companion paper [2] we devise and...
Algorithmic Game Theory Edited by (2008)
Noam Nisan, Tim Roughgarden, Éva Tardos, Vijay Vazirani, L. Blumrosen, N. Nisan Page
Sushil Bikhch, Shurojit Chatterji, Ron Lavi, Noam Nisan, Arunava Sen
We characterize dominant-strategy incentive compatibility with multi-dimensional types. A deterministic social choice function is dominant-strategy incentive compat-ible if and only if it is weakly...
Abstract Combinatorial Agency (2008)
Moshe Babaioff, Michal Feldman, Noam Nisan
Much recent research concerns systems, such as the Internet, whose components are owned and operated by different parties with different “selfish ” goals. The field of Algorithmic Mechanism...
Contents 1 Introduction to Mechanism Design (for Computer Scientists) (2008)
Noam Nisan, Tim Roughgarden, Éva Tardos, Vijay Vazirani, N. Nisan Page
Abstract One of the major achievements of mechanism design theory is the family of truthful (incentive compatible) mechanisms often called VCG (named after Vickrey, Clarke and Groves). When applying...
A Note on the Computational Hardness of Evolutionary Stable Strategies Draft (2008)
We present a very simple reduction that when given a graph G and an integer k produces a game that has an evolutionary stable strategy if and only if the maximum clique size of G is not exactly k....
Algorithmic Mechanism Design contact: (2008)
Noam Nisan, Amir Ronen Y, Amir Ronen
We consider algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are...
Sushil Bikhch, Shurojit Chatterji, Ron Lavi, Noam Nisan, Arunava Sen
In our main paper, we define a weak-monotonicity (W-Mon) condition that is necessary and sufficient for dominant-strategy implementation in a variety of do-mains. This supplementary material...
Abstract One of the major achievements of mechanism design theory is the family of truthful (incentive compatible) mechanisms often called VCG (named after Vickrey, Clarke and Groves). When applying...
Limitations of VCG-based mechanisms (2008)
Abstract We consider computationally-efficient incentive-compatible mechanisms that use the VCG pay-ment scheme, and study how well they can approximate the social welfare in auction settings. We...
Mixed Strategies in Combinatorial Agency [Extended Abstract] (2008)
Moshe Babaioff, Michal Feldman, Noam Nisan
Abstract. We study a setting where a principal needs to motivate a team of agents whose combination of hidden efforts stochastically determines an outcome. In a companion paper we devise and study a...
Noam Nisan, Tim Roughgarden, Éva Tardos, Vijay Vazirani, Stengel Page
3.2 Bimatrix games and the best response condition 5
Inductive and Co-inductive Techniques (2008)
Miklos Ajtai, Oded Goldreich, Mark Jerrum, Noam Nisan, Er Razborov
WelcometothefirstissueoftheBRICSnewsletter.Itspurposeistoinformyouofappointments, publications,coursesandotheractivitieswithin BRICS.Furtherdetailscanbeobtainedbycontactingtheaddressesbelow....
Exponential Communication Inefficiency of Demand Queries (2008)
In the problem of nding an e cient allocation when agentsutilities are privately known, we examine the eect of restricting attention to mechanisms using demand queries, which ask agents to report an...
Ehud Friedgut, Gil Kalai, Noam Nisan, Ehud Friedgut, Gil Kalai, Noam Nisan
The Gibbard-Satterthwaite theorem states that every non-trivial voting method between at least 3 alternatives can be strategically manipulated. We prove a quantitative version of the...
Undirected Connectivity in (2007)
Log Space Noam, Noam Nisan, Endre Szemeredi, Avi Wigderson
We present a deterministic algorithm for the connectivity problem on undirected graphs that runs in O(log 1:5 n) space. Thus, the recursive doubling technique of Savich which requires O(log 2 n)...
Undirected Connectivity in O(log^1.5 n) Space (2007)
Noam Nisan, Endre Szemeredi, Avi Wigderson
We present a deterministic algorithm for the connectivity problem on undirected graphs that runs in O(log^1.5 n) space. Thus, the recursive doubling technique of Savich which requires...
Peter Bro Miltersen, Noam Nisan, Avi Wigderson
In this paper we consider two-party communication complexity, the ``asymmetric case'', when the input sizes of the two players differ significantly. Most of previous work on communication...
Benny Lehmann, Daniel Lehmann, Noam Nisan
In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such submodular buyers. The valuations of such...
Dorit Aharonov, Michael Ben-or, Russell Impagliazzo, Noam Nisan
In this paper we study noisy reversible circuits. Noisy computation and reversible computation have been studied separately, and it is known that they are equivalent in power to unrestricted...
Institute of Computer Science, (2007)
Lior Levy, Liad Blumrosen, Noam Nisan
We describe a general-purpose architecture for applying economic mechanisms for resource allocation in distributed systems. Such economic mechanisms are required in settings such as the Internet,...
Benny Lehmann, Daniel Lehmann, Noam Nisan
The major part of the literature dealing with computational aspects of combinatorial auctions has considered only the most general setting, in which buyers may express complementarities. This paper...
On Line Markets for Distributed Object Services: The Majic System (2007)
Lior Levy, Liad Blumrosen, Noam Nisan
We describe a general-purpose architecture for applying economic mechanisms for resource allocation in distributed systems. Such economic mechanisms are required in settings such as the Internet,...
Moshe Babaioff, Noam Nisan, Elan Pavlov
We consider the problem of a spatially distributed market with strategic agents. In this problem a single good is traded in a set of independent markets, where shipment between markets is possible...
Rica Gonen School, Rica Gonen, Yair Bartal, Noam Nisan, Mira Gonen
ion rule describes a payment p j for each bidder j. We assume the bidders have quasi-linear utilities, so bidder j's overall utility for winning the set S j and paying p j is u j = v j (S j ) p...
An impossibility result for ex-post implementable multi-item auctions with private values (2007)
We analyze ex-post implementable social choice functions for private-value and quasi-linear settings over restricted domains of preferences, the leading example being multi-item auctions (with either...
Mechanisms for Multi-Unit Auctions (2007)
Abstract We present an incentive-compatible polynomial-time approximation scheme for multi-unitauctions with general k-minded player valuations. The mechanism fully optimizes over anappropriately...
Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation (2006)
Bikhchandani, Sushil, Chatterji, Shurojit, Lavi, Ron, Mu'alem, Ahuva, Nisan, Noam, Sun, Arunava
We characterize dominant-strategy incentive compatibility with multidimensional types. A deterministic social choice function is dominant-strategy incentive compatible if and only if it is weakly...
Moshe Babaioff, Michal Feldman, Noam Nisan
Much recent research concerns systems, such as the Internet, whose components are owned and operated by different parties, each with his own “selfish ” goal. The field of Algorithmic Mechanism...
The communication complexity of uncoupled Nash equilibrium procedures (2006)
Sergiu Hart, Yishay Mansour, Fabrizio Germano, Adam Kalai, Eyal Kushilevitz, Andreu Mas-colell, ...
We study the question of how long it takes players to reach a Nash equilibrium in uncoupled setups, where each player initially knows only his own payoff function. We derive lower bounds on the...
The communication requirements of efficient allocations and supporting prices (2006)
We show that any communication finding a Pareto efficient allocation in a private-information economy must also discover supporting Lindahl prices. In particular, efficient allocation of L...
Truthful randomized mechanisms for combinatorial auctions (2006)
Shahar Dobzinski, Noam Nisan, Michael Schapira
Abstract We design two computationally-eOEcient incentive-compatible mechanisms for combinatorial auctions with general bidder preferences. Both mechanisms are randomized, and are incentivecompatible...
Truthful randomized mechanisms for combinatorial auctions (2006)
Shahar Dobzinski, Noam Nisan, Michael Schapira
Abstract We design two computationally-efficient incentive-compatible mechanisms for combinatorialauctions with general bidder preferences. Both mechanisms are randomized, and are incentivecompatible...
Moshe Babaioff, Michal Feldman, Noam Nisan
We study a combinatorial variant of the classical principal-agent model. In our setting a principal wishes to motivate a team of strategic agents to exert costly effort on his behalf, but their...
Online ascending auctions for gradually expiring items (2005)
In this paper we consider online auction mechanisms for the allocation of M items that are identical to each other except for the fact that the items have dierent expiration times, and each item must...
Approximation algorithms for combinatorial auctions with complement-free bidders (2005)
Shahar Dobzinski, Noam Nisan, Michael Schapira
We exhibit three approximation algorithms for the allocation problem in combinatorial auctions with complement free bidders. The running time of these algorithms is polynomial in the number of items...
Online ascending auctions for gradually expiring items (2005)
Abstract In this paper we consider online auction mechanisms forthe allocation of M items that are identical to each otherexcept for the fact that they have different expiration
Online ascending auctions for gradually expiring items (2005)
In this paper we consider online auction mechanisms for the allocation of M items that are identical to each other except for the fact that the items have dierent expiration times, and each item must...
Exponential Communication Ine ¢ ciency of Demand Queries (2005)
In the problem of …nding an e ¢ cient allocation when agents’utilities are privately known, we examine the e¤ect of restricting attention to mechanisms using “demand queries, ” which ask...
Approximation algorithms for combinatorial auctions with complement-free bidders (2005)
Shahar Dobzinski, Noam Nisan, Michael Schapira
Abstract We exhibit three approximation algorithms for the allocation problem in combinatorial auctions with complement free bidders. The running time of these algorithms is polynomial in the number...
On the Computational Power of Iterative Auctions I: Demand Queries (2005)
We study the computational power and limitations of iterative combinatorial auctions. Most existing iterative combinatorial auctions are based on repeatedly suggesting prices for bundles of items,...
Online ascending auctions for gradually expiring items (2005)
We consider dynamic auction mechanisms for the allocation of multiple items. Items are identical, but have different expiration times, and each item must be allocated before it expires. Buyers are of...
Mechanisms for a spatially distributed market (2004)
Moshe Babaioff, Noam Nisan, Elan Pavlov
We consider the problem of a spatially distributed market with strategic agents. In this problem a single good is traded in a set of independent markets, where shipment between markets is possible...
Fairplay — a secure two-party computation system (2004)
Dahlia Malkhi, Noam Nisan, Benny Pinkas, Yaron Sella
Advances in modern cryptography coupled with rapid growth in processing and communication speeds make secure twoparty computation a realistic paradigm. Yet, thus far, interest in this paradigm has...
Compact name-independent routing with minimum stretch (2004)
Ittai Abraham, Noam Nisan, Cyril Gavoille, Dahlia Malkhi, Mikkel Thorup
Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a �O ( √ n) space routing table at each node, and routing along paths of stretch 3, that...
Concurrent Auctions across the Supply Chain (2004)
With the recent technological feasibility of electronic commerce over the Internet, much attention has been given to the design of electronic markets for various types of electronically-tradable...
Concurrent Auctions across the Supply Chain (2004)
With the recent technological feasibility of electronic commerce over the Internet, much attention has been given to the design of electronic markets for various types of electronically-tradable...
Fairplay - A Secure Two-Party Computation System (2004)
Dahlia Malkhi, Noam Nisan, Benny Pinkas, Yaron Sella
Advances in modern cryptography coupled with rapid growth in processing and communication speeds make secure two-party computation a realistic paradigm. Yet, thus far, interest in this paradigm has...
Fairplay - A Secure Two-Party Computation System (2004)
Dahlia Malkhi, Noam Nisan, Benny Pinkas, Yaron Sella
Advances in modern cryptography coupled with rapid growth in processing and communication speeds make secure twoparty computation a realistic paradigm. Yet, thus far, interest in this paradigm has...
Fairplay — a secure two-party computation system (2004)
Dahlia Malkhi, Noam Nisan, Benny Pinkas, Yaron Sella
Advances in modern cryptography coupled with rapid growth in processing and communication speeds make secure two-party computation a realistic paradigm. Yet, thus far, interest in this paradigm has...
Exponential Communication Ine ¢ ciency of Demand Queries (2004)
Nisan and Segal (forthcoming) show that when verifying the e ¢ ciency of a combinatorial allocation, without increasing the communication burden one
Compact name-independent routing with minimum stretch (2004)
Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, Mikkel Thorup
Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a � O ( √ n) space routing table at each node, and routing along paths of stretch 3, that...
Fairplay - A Secure Two-Party Computation System (2004)
Dahlia Malkhi, Noam Nisan, Benny Pinkas, Yaron Sella
Advances in modern cryptography coupled with rapid growth in processing and communication speeds make secure two-party computation a realistic paradigm. Yet, thus far, interest in this paradigm has...
Towards a characterization of truthful combinatorial auctions (2003)
This paper analyzes implementable social choice functions (in dominant strategies) over restricted domains of preferences, the leading example being combinatorial auc-tions. Our work generalizes the...
Incentive compatible multi unit combinatorial auctions (2003)
Yair Bartal, Rica Gonen, Noam Nisan
This paper deals with multi-unit combinatorial auctions where there are n types of goods for sale, and for each good there is some fixed number of units. We focus on the case where each bidder...
Towards a characterization of truthful combinatorial auctions (2003)
In recent years we have seen much research aimed atdesigning algorithms that are intended to function in environments where the inputs to the algorithm are distributedamong players who have different...
Towards a characterization of truthful combinatorial auctions (2003)
This paper analyzes incentive compatible (truthful) mechanisms over restricted domains of preferences, the leading example being combinatorial auctions. Our work generalizes the characterization of...
Incentive Compatible Multi Unit Combinatorial Auctions (2003)
Yair Bartal, Rica Gonen, Noam Nisan
The problem we deal with in this paper is a multi-unit combinatorial auction: there are n types of goods for sale, and for each good there is some fixed number of units. We focus on the case where...
Incentive compatible multi unit combinatorial auctions (2003)
Yair Bartal, Rica Gonen, Noam Nisan
The problem we deal with in this paper is a multi-unit combinatorial auction: there are n types of goods for sale, and for each good there is some xed number of units. We focus on the case where each...
Towards a characterization of truthful combinatorial auctions (2003)
This paper analyzes implementable social choice functions (in dominant strategies) over restricted domains of preferences, the leading example being combinatorial auc-tions. Our work generalizes the...
Incentive compatible multi unit combinatorial auctions (2003)
Yair Bartal, Rica Gonen, Noam Nisan
The problem we deal with in this paper is a multi-unit combinatorial auction: there are n types of goods for sale, and for each i there are k i units of good i. We are interested in the case where...
Towards a Characterization of Truthful Combinatorial Auctions (2003)
Preliminary Version Comments, Ron Lavi, Noam Nisan
This paper analyzes incentive compatible (truthful) mechanisms over restricted domains of preferences, the leading example being combinatorial auctions. Our work generalizes the characterization of...
Multi-Player and Multi-Round Auctions with Severely Bounded Communication (2003)
Liad Blumrosen, Noam Nisan, Ilya Segal
We study auctions in which bidders have severe constraints on the size of messages they are allowed to send to the auctioneer. In such auctions, each bidder has a set of k possible bids (i.e. he can...
Multi-player and multi-round auctions with severely bounded communication. ESA (2003)
Liad Blumrosen, Noam Nisan, Ilya Segal
Abstract. We study auctions in which bidders have severe constraints on the size of messages they are allowed to send to the auctioneer. In such auctions, each bidder has a set of k possible bids...
The communication requirements of efficient allocations and supporting prices (2003)
We show that any communication finding a value-maximizing allocation in a private-information economy must also discover supporting prices (in general personalized and nonlinear). In particular, to...
Multi-Player and Multi-Round Auctions with Severely Bounded Communication (2003)
Liad Blumrosen, Noam Nisan, Ilya Segal
We study auctions in which bidders have severe constraints on the size of messages they are allowed to send to the auctioneer. In such auctions, each bidder has a set of k possible bids (i.e. he can...
Combinatorial Auctions with Decreasing Marginal Utilities (2002)
Lehmann, Benny, Lehmann, Daniel, Nisan, Noam
In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such submodular buyers. The valuations of such...
Truthful approximation mechanisms for restricted combinatorial auctions (2002)
When attempting to design a truthful mechanism for a computationally hard problem such as combinatorial auctions, one is faced with the problem that most efficiently computable heuristics can not be...
Truthful approximation mechanisms for restricted combinatorial auctions (2002)
Abstract When attempting to design a truthful mechanism for a computationally hard problem such ascombinatorial auctions, one is faced with the problem that most efficiently computable heuristics can...
Truthful approximation mechanisms for restricted combinatorial auctions (2002)
Abstract When attempting to design a truthful mechanism for a computationally hard problem such as combinatorial auctions, one is faced with the problem that most efficiently computable heuristics...
The communication complexity of approximate set packing and covering (2002)
n))-approximation for the packing number can be done with polynomial (in n) amount of communication, getting a (1=2 \Gamma ffl) log n approximation for the cover number or a better than min(k; n...
The communication complexity of approximate set packing and covering (2002)
We prove that while computing a (ln n)-approximation for the cover number and an min(k; O( p n))-approximation for the packing number can be done with polynomial (in n) amount of communication,...
Agents’ privacy in distributed algorithmic mechanisms. Position Paper (2002)
Joan Feigenbaum, Noam Nisan, Vijay Ramachandran, Rahul Sami, Scott Shenker
In traditional theoretical computer science (TCS), computational agents are typically assumed either to be obedient (i.e., to follow the prescribed algorithm) or to be adversaries who “play against...
Auctions with severely bounded communication (2002)
We study auctions with severe bounds on the communication allowed: each bidder may only transmit t bits of information to the auctioneer. We consider both welfare-maximizing and revenuemaximizing...
The communication complexity of efficient allocation problems (2002)
We analyze the communication complexity of surplus-maximizing allocations. We study both the continuous and discrete models of communication, measuring its complexity with the dimensionality of...
Truthful approximation mechanisms for restricted combinatorial auctions (2002)
When attempting to design a truthful mechanism for a computationally hard problem such as combinatorial auctions, one is faced with the problem that most eciently computable heuristics can not be...
The communication complexity of approximate set packing and covering (2002)
We consider a setting where k players are each holding some collection of subsets of f1::ng. We consider the communication complexity of approximately solving two problems: The cover number: the...
Auctions with Severely Bounded Communication (2002)
We study auctions with severe bounds on the communication allowed: each bidder may only transmit t bits of information to the auctioneer. We consider both welfaremaximizing and revenue-maximizing...
The communication complexity of efficient allocation problems (2002)
participants of seminars at Stanford and the DIMACS Workshop on Computational Issues in Game Theory and Mechanism Design for useful comments. y
Auctions with severely bounded communication (2002)
Liad Blumrosen, Noam Nisan, Ilya Segal
We study auctions with severe bounds on the communication allowed: each bidder may only transmit t bits of information to the auctioneer. We consider both welfare- and profit-maximizing auctions...
Auctions with severely bounded communication (2002)
Liad Blumrosen, Noam Nisan, Ilya Segal
We study auctions with severe bounds on the communication allowed: each bidder may only transmit t bits of information to the auctioneer. We consider both welfare- and profit-maximizing auctions...
The communication complexity of efficient allocation problems (2002)
We analyze the communication burden of surplus-maximizing allocations. We study both the continuous and discrete models of communication, measuring its burden with the dimensionality of the message...
Auctions with Severely Bounded Communication (2002)
Liad Blumrosen, Noam Nisan, Ilya Segal
We study auctions with severe bounds on the communication allowed: each bidder may only transmit t bits of information to the auctioneer. We consider both welfare-maximizing and prot-maximizing...
The Communication Complexity of Efficient Allocation Problems (2001)
We analyze the communication complexity of surplus-maximizing allocations. We study both the continuous and discrete models of communication, measuring its complexity with the dimensionality of the...
Combinatorial Auctions with Decreasing Marginal Utilities (2001)
Benny Lehmann, Daniel Lehmann, Noam Nisan
In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such buyers. The valuations of such buyers are...
An Efficient Approximate Allocation Algorithm for Combinatorial Auctions (2001)
We propose a heuristic for allocation in combinatorial auctions. We first run an approximation algorithm on the linear programming relaxation of the combinatorial auction. We then run a sequence of...
The communication complexity of combinatorial auctions (2001)
We show that any implementation of combinatorial auctions that produces efficient allocations requires an exponential amount of information transfer. The lower bound is independent of any...
With the recent technological feasibility of electronic commerce over the Internet, much attention has been given to the design of electronic markets for various types of electronically-tradable...
Concurrent auctions across the supply chain (2001)
With the recent technological feasibility of electronic commerce over the Internet, much attention has been given to the design of electronic markets for various types of electronically-tradable...
Bidding and allocation in combinatorial auctions (2000)
When an auction of multiple items is performed, it is often desirable to allow bids on combinations of items, as opposed to only on single items. Such an auction is often called...
Competitive analysis of incentive compatible on-line auctions (2000)
This paper studies auctions in a setting where the dierent bidders arrive at dierent times and the auction mechanism is required to make decisions about each bid as it is received. Such settings...
Computationally Feasible VCG Mechanisms (2000)
One of the major achievements of mechanism design theory is the family of truthful (incentive compatible) mechanisms often called VCG (named after Vickrey, Clarke and Groves). When applying VCG...
Competitive Analysis of Incentive Compatible On-Line Auctions (2000)
This paper studies auctions in a setting where the different bidders arrive at different times and the auction mechanism is required to make decisions about each bid as it is received. Such settings...
Computationally feasible VCG mechanisms (2000)
A major achievement of mechanism design theory is a general method for the construction of truthful mechanisms called VCG (Vickrey, Clarke, Groves). When applying this method to complex problems such...
Computationally feasible VCG mechanisms (2000)
A major achievement of mechanism design theory is a general method for the construction of truthful mechanisms called VCG (Vickrey, Clarke, Groves). When applying this method to complex problems such...
Computationally Feasible VCG Mechanisms (2000)
One of the major achievements of mechanism design theory is the family of truthful (incentive compatible) mechanisms often called VCG (named after Vickrey, Clarke and Groves). When applying VCG...
Algorithms for selfish agents: Mechanism design for distributed computation (1999)
Abstract This paper considers algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. Such scenarios arise,...
Algorithms for sel sh agents - mechanism design for distributed computation (1999)
This paper considers algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. Such scenarios arise, in...
Algorithms for sel sh agents - mechanism design for distributed computation (1999)
This paper considers algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. Such scenarios arise, in...
Algorithmic mechanism design (1999)
We consider algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are...
Algorithmic mechanism design (1999)
Noam Nisan, Amir Ronen, Amir Ronen
We consider algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are...
Algorithms for selfish agents: Mechanism design for distributed computation (1999)
This paper considers algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. Such scenarios arise, in...
Algorithmic mechanism design (1999)
We consider algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are...
On randomized one-round communication complexity (1999)
Ilan Kremer, Noam Nisan, Dana Ron
Abstract. We present several results regarding randomized one-round communication complexity. Our results include a connection to the VCdimension, a study of the problem of computing the inner...
Bidding and Allocation in Combinatorial Auctions (1999)
When an auction of multiple items is performed, it is often desirable to allow bids on combinations of items, as opposed to only on single items. Such an auction is often called...
Algorithmic Mechanism Design (1999)
Noam Nisan, Amir Ronen, Amir Ronen
We consider algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are...
Algorithmic Mechanism Design (1999)
We consider algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are...
Algorithmic Mechanism Design (1999)
Noam Nisan, Amir Ronen, Amir Ronen
We consider algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are...
Quantum Circuits with Mixed States (1998)
Aharonov, Dorit, Kitaev, Alexei, Nisan, Noam
We define the model of quantum circuits with density matrices, where non-unitary gates are allowed. Measurements in the middle of the computation, noise and decoherence are implemented in a natural...
On data structures and asymmetric communication complexity (1998)
Peter Bro Miltersen, Peter Bro Miltersen, Noam Nisan, Noam Nisan, Avi Wigderson, Avi Wigderson
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Quantum circuits with mixed states (1998)
Dorit Aharonov, Alexei Kitaev, Noam Nisan
Current formal models for quantum computation deal only with unitary gates operating on "pure quantum states". In these models it is difficult or impossible to deal formally with...
Efficient Approximation of Product Distributions (1998)
Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic
We describe efficient constructions of small probability spaces that approximate the joint distribution of general random variables. Previous work on efficient constructions concentrate on...
Oded Goldreich, Noam Nisan, Avi Wigderson
A fundamental Lemma of Yao states that computational weak-unpredictability of functions gets amplified if the results of several independent instances are XOR together. We survey two known proofs of...
Extracting Randomness: A Survey and New Constructions (1998)
Extractors are boolean functions that allow, in some precise sense, extraction of randomness from somewhat random distributions, using only a small amount of truly random bits. Extractors, and the...
Trade-offs Between Communication Throughput and Parallel Time (1998)
Yishay Mansour, Noam Nisan, Uzi Vishkin
We study the effect of limited communication throughput on parallel computation in a setting where the number of processors is much smaller than the length of the input. Our model has p processors...
On data structures and asymmetric communication complexity (1998)
Peter Bro Miltersen, Noam Nisan, Peter Bro, Miltersen Noam, Nisan Shmuel Safra, Avi Wigderson, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
Pointer jumping requires concurrent read (1997)
We consider the well known problem of determining the k'th vertex reached by chasing pointers in a directed graph of out-degree 1. The famous "pointer doubling " technique...
Efficient Approximation of General Product Distributions (1997)
Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic
We describe efficient constructions of small probability spaces that approximate the joint distribution of general random variables. Previous work on efficient constructions concentrate on...
Pointer Jumping Requires Concurrent Read (1997)
We consider the well known problem of determining the k'th vertex reached by chasing pointers in a directed graph of out-degree 1. The famous "pointer doubling" technique provides an...
Pointer jumping requires concurrent read (1997)
We consider the well known problem of determining the ¡ ’th vertex reached by chasing pointers in a directed graph of out-degree 1. The famous “pointer doubling” technique provides...
Lower Bounds on Arithmetic Circuits Via Partial Derivatives (1996)
Noam Nisan, Noam Nisan, Avi Wigderson, Avi Wigderson
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Randomness is linear in space (1996)
We show that any randomized algorithm that runs in space S and time T and uses poly(S) random bits can be simulated using only O(S) random bits in space S and time T + poly(S). A deterministic...
Lower Bounds on Arithmetic Circuits Via Partial Derivatives (1996)
In this paper we describe a new technique for obtaining lower bounds on restricted classes of nonmonotone arithmetic circuits. The heart of this technique is a complexity measure for multivariate...
Oded Goldreich, Noam Nisan, Avi Wigderson
A fundamental Lemma of Yao states that computational weak-unpredictability of functions gets amplified if the results of several independent instances are XOR together. We survey two known proofs of...
Symmetric Logspace is closed under complement (1995)
Noam Nisan, Noam Nisan, Amnon Ta-shma, Amnon Ta-shma
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Oded Goldreich, Noam Nisan, Avi Wigderson
A fundamental Lemma of Yao states that computational weak-unpredictability of functions gets amplified if the results of several independent instances are XOR together. We survey two known proofs of...
Symmetric Logspace is Closed Under Complement (1995)
We present a Logspace, many-one reduction from the undirected st-connectivity problem to its complement. This shows that SL = coSL. 1 Introduction This paper deals with the complexity class symmetric...
On Randomized One-Round Communication Complexity (1995)
Ilan Kremer, Noam Nisan, Dana Ron
We present several results regarding randomized one-round communication complexity. These include a connection to the VC dimension, a study of the problem of computing the inner product of two real...
Lower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version) (1995)
In this paper we describe a new technique for obtaining lower bounds on restriced classes of nonmonotone arithmetic circuits. The heart of this technique is a complexity measure for multivariate...
On Constructing 1-1 One-Way Functions (1995)
Oded Goldreich, Leonid A. Levin, Noam Nisan
We show how to construct length-preserving 1-1 one-way functions based on popular intractability assumptions (e.g., RSA, DLP). Such 1-1 functions should not be confused with (infinite) families of...
Symmetric Logspace is Closed Under Complement (1995)
Noam Nisan, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 st connectivity problem to its complement. This shows that SL = coSL. 1 Introduction This paper deals with the complexity...
We show that any randomized Logspace algorithm (running in polynomial time, with bounded two-sided error) can be simulated deterministically in polynomial time and O(log 2 n) space. This puts RL in...
On Constructing 1-1 One-Way Functions (1995)
Oded Goldreich, Leonid A Levin, Noam Nisan
We show how to construct length-preserving 1-1 one-way functions based on popular intractability assumptions (e.g., RSA, DLP). Such 1-1 functions should not be confused with (infinite) families of...
On Randomized One-Round Communication Complexity (1995)
Ilan Kremer, Noam Nisan, Dana Ron
We present several results regarding randomized one-round communication complexity. Our results include a connection to the VC-dimension, a study of the problem of computing the inner product of two...
Probabilistic Analysis of Network Flow Algorithms (1995)
Richard M. Karp, Rajeev Motwani, Noam Nisan
This paper is concerned with the design and probabilistic analysis of algorithms for the maximumflow problem and capacitated transportation problems. These algorithms run in linear time and, under...
On Randomized One-Round Communication Complexity (1995)
Ilan Kremer, Noam Nisan, Dana Ron
We present several results regarding randomized oneround communication complexity. These include a connection to the VC-dimension, a study of the problem of computing the inner product of two real...
Amortized Communication Complexity (1995)
Tomàs Feder, Moni Naor, Eyal Kushilevitz, Noam Nisan
In this work we study the direct-sum problem with respect to communication complexity: Consider a relation f defined over f0; 1g n \Theta f0; 1g n . Can the communication complexity of simultaneously...
Symmetric Logspace is Closed under Complement (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 s--t connectivity problem to its complement. This shows that SL = coSL.
Symmetric Logspace is closed under complement (1995)
Noam Nisan, Noam Nisan, Amnon Ta-shma, Amnon Ta-shma
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
Products and Help Bits in Decision Trees (1994)
Noam Nisan, Steven Rudich, Michael Saks
We investigate two problems concerning the complexity of evaluating a function f at a k-tuple of unrelated inputs by k parallel decision tree algorithms. In the product problem, for some fixed depth...
On the Complexity of Bilinear Forms (Extended Abstract) (1994)
) Noam Nisan y Institute of Computer Science, Hebrew University of Jerusalem, Israel. Avi Wigderson z Institute of Computer Science, Hebrew University of Jerusalem, Israel. November 29, 1994 Abstract...
Products and Help Bits in Decision Trees (1994)
Noam Nisan, Steven Rudich, Michael Saks
We investigate two problems concerning the complexity of evaluating a function f at a k-tuple of unrelated inputs by k parallel decision tree algorithms. In the product problem, for some fixed depth...
Trade-offs Between Communication Throughput and Parallel Time (1994)
Yishay Mansour Noam, Noam Nisan
We study the effect of limited communication throughput on parallel computation in a setting where the number of processors is much smaller than the length of the input. Our model has p processors...
On Rank vs. Communication Complexity (1994)
. This paper concerns the open problem of Lovasz and Saks regarding the relationship between the communication complexity of a boolean function and the rank of the associated matrix. We first give an...
Pseudorandomness for Network Algorithms (1994)
Russell Impagliazzo, Noam Nisan, Avi Wigderson
We define pseudorandom generators for Yao's twoparty communication complexity model and exhibit a simple construction, based on expanders, for it. We then use a recursive composition of such...
Pseudorandomness for Network Algorithms (1994)
Russell Impagliazzo, Noam Nisan, Avi Wigderson
We define pseudorandom generators for Yao's twoparty communication complexity model and exhibit a simple construction, based on expanders, for it. We then use a recursive composition of such...
Trade-offs Between Communication Throughput and Parallel Time (1994)
Yishay Mansour, Noam Nisan, Uzi Vishkin
We study the effect of limited communication throughput on parallel computation in a setting where the number of processors is much smaller than the length of the input. Our model has p processors...
Symmetric Logspace is Closed Under Complement (1994)
. We present a Logspace, many-one reduction from the undirected stconnectivity problem to its complement. This shows that SL = co \Gamma SL. y Institute of Computer Science, Hebrew University of...
The Communication Complexity of Threshold Gates (1994)
We prove upper bounds on the randomized communication complexity of evaluating a threshold gate (with arbitrary weights). For linear threshold gates this is done in the usual 2 party communication...
Hardness vs. randomness (1994)
We present a simple new construction of a pseudorandom bit generator, based on the constant depth generators of [N]. It stretches a short string of truly random bits into a long string that looks...
Rounds in communication complexity revisited (1993)
We also study the three party communication model, and exhibit an exponential gap in 3-round protocols that differ in the starting player.
The Computational Complexity of Universal Hashing (1993)
Yishay Mansour, Noam Nisan, Prasoon Tiwari
Any implementation of Carter-Wegman universal hashing from n-bit strings to m-bit strings requires a time-space tradeo of TS = nm). The bound holds in the general boolean branching program model, and...
On read-once vs. multiple access to randomness in logspace (1993)
In the "correct " definition of randomized space-bounded computation, the machine has access to a random coin. The coin can be flipped at will, but outcomes of previous coin flips...
A Parallel Approximation Algorithm for Positive Linear Programming (1993)
We introduce a fast parallel approximation algorithm for the positive linear programming optimization problem, i.e. the special case of the linear programming optimization problem where the input...
The Effect of Random Restrictions on Formula Size (1993)
Russell Impagliazzo, Noam Nisan
We consider the formula size complexity of boolean functions over the base consisting of , , and : gates. In 1961 Subbotovskaya proved that, for any boolean function on n variables, setting all but a...
A Parallel Approximation Algorithm for Positive Linear Programming (1993)
Michael Luby Noam, Michael Luby, Noam Nisan
We introduce a fast parallel approximation algorithm for the positive linear programming optimization problem, i.e. the special case of the linear programming optimization problem where the input...
BPP has Subexponential Time Simulations unless EXPTIME has Publishable Proofs (1993)
László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson, Ma P
. We show that BPP can be simulated in subexponential time for infinitely many input lengths unless exponential time ffi collapses to the second level of the polynomial-time hierarchy, ffi has...
Rounds in Communication Complexity Revisited (1993)
The k-round two-party communication complexity was studied in the deterministic model by [14] and [4] and in the probabilistic model by [20] and [6]. We present new lower bounds that give (1)...
Rounds in communication complexity revisited (1993)
Abstract. The k-round two-party communication complexity was studied in the deterministic
Using hard problems to create pseudorandom generators /--Noam Nisan. (1992)
Revision of the author's thesis (Ph. D.)--University of California, Berkeley, 1988.
Approximations of General Independent Distributions (1992)
Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovi'c
We describe efficient constructions of small probability spaces that approximate the independent distribution for general random variables. Previous work on efficient constructions concentrate on...
Algebraic Methods for Interactive Proof Systems (1992)
Carsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan
We present a new algebraic technique for the construction of interactive proof systems. We use our technique to prove that every language in the polynomial-time hierarchy has an interactive proof...
Fast Connected Components Algorithms For The Erew Pram (1992)
Erew Pram, David R. Karger, Noam Nisan, Michal Parnas
.<F3.822e+05> We present fast and e#cient parallel algorithms for finding the connected components of an undirected graph. These algorithms run on the exclusive-read, exclusive-write (EREW)...
bounds for non-commutative computation (Extended Abstract (1991)
We consider algebraic computations which are not allowed to rely on the commutativity of multiplication. We obtain various lower bounds for algebraic formula size in this model: (1) Computing the...
Algebraic Methods for Interactive Proof Systems (1990)
Carsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan
We present a new algebraic technique for the construc-tion of interactive proof systems. We use our technique to prove that every language in the polynomial-time hierarchy has an interactive proof...
Approximate inclusion-exclusion (1990)
The Inclusion-Exclusion formula expresses the size of a union of a family of sets in terms of the sizes of intersections of all subfamilies. This paper considers approximating the size of the union...
Lower Bounds on Random-Self-Reducibility (Extended Abstract) (1990)
Joan Feigenbaum, Sampath Kannan, Noam Nisan
Structures-1990 Proceedings) Joan Feigenbaum Sampath Kannan y Noam Nisan z Abstract: Informally speaking, a function f is random-self-reducible if, for any x, the computation of f(x) can be reduced...
Using hard problems to create pseudorandom generators /--by Noam Nisan. (1989)
Thesis (Ph. D. in Computer Science)--University of California, Berkeley, May 1989.
Truthful Randomized Mechanisms for Combinatorial Auctions
Shahar Dobzinski, Noam Nisan, Michael Schapira
We design two computationally-efficient incentive-compatible mechanisms for combinatorial auctions with general bidder preferences. Both mechanisms are randomized, and are incentive-compatible in the...
On the Computational Power of Iterative Auctions I: Demand Queries
We study the computational power and limitations of iterative combinatorial auctions. Most existing iterative combinatorial auctions are based on repeatedly suggesting prices for bundles of items,...
Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation
Sushil Bikhchandani, Shurojit Chatterji, Ron Lavi, Ahuva Mu'alem, Noam Nisan, Arunava Sen
We characterize dominant-strategy incentive compatibility with multidimensional types. A deterministic social choice function is dominant-strategy incentive compatible if and only if it is weakly...
On the Computational Power of Iterative Auctions II: Ascending Auctions
We embark on a systematic analysis of the power and limitations of iterative ascending-price combinatorial auctions. We prove a large number of results showing the boundaries of what can be achieved...
Elections Can be Manipulated Often
Ehud Friedgut, Gil Kalai, Noam Nisan
The Gibbard-Satterthwaite theorem states that every non-trivial voting method between at least 3 alternatives can be strategically manipulated. We prove a quantitative version of the...
Mechanisms for a spatially distributed market
Babaioff, Moshe, Nisan, Noam, Pavlov, Elan
We consider the problem of a spatially distributed market with strategic agents. A single good is traded in a set of independent markets, where shipment between markets is possible but costly. The...