We introduce a model of dynamic matching in networked markets, where agents arrive and depart stochastically, and the composition of the trade network depends endogenously on the matching algorithm. We show that if the planner can identify agents who are about to depart, then waiting to thicken the market is highly valuable, and if the planner cannot identify such agents, then matching agents greedily is close to optimal. We characterize the optimal timing policy as a function of waiting costs and network sparsity. The planner’s decision problem in our model involves a combinatorially complex state space. However, we show that simple local algorithms that choose the right time to match agents, but do not exploit the global network structure, can perform close to complex optimal algorithms. Finally, we consider a setting where agents have private information about their departure times, and design a continuous-time dynamic mechanism to elicit this information.

We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer has a value for each item drawn independently according to (non-identical) distributions, and her value for a set of items is additive. The seller aims to maximize her revenue. It is known that an optimal mechanism in this setting may be quite complex, requiring randomization and menus of infinite size. Hart and Nisan have initiated a study of two very simple pricing schemes for this setting: item pricing, in which each item is priced at its monopoly reserve; and bundle pricing, in which the entire set of items is priced and sold as one bundle. Hart and Nisan have shown that neither scheme can guarantee more than a vanishingly small fraction of the optimal revenue. In sharp contrast, we show that for any distributions, the better of item and bundle pricing yields a 6-approximation to the optimal revenue. We further extend this result to settings where the buyer has a valuation function that is just subadditive, but "independent across items," showing that the better of item and bundle pricing still yields a constant-factor approximation.

Based on joint works with Moshe Babaioff, Nicole Immorlica and Brendan Lucier, and Aviad Rubinstein.

In mechanism design, strategy-proofness is often said to be desirable because it makes it easy for agents to decide what to do. However, some strategy-proof mechanisms are easier to understand than others.  To address this problem, I propose a new solution concept: Obviously Strategy-Proof (OSP).  Using a formal cognitive model, I show that a mechanism is OSP if each agent's dominant strategy can be verified without contingent reasoning. I show that a choice rule is OSP-implementable if it can be carried out by a social planner under a particular regime of partial commitment. Finally, I characterize the set of OSP mechanisms in a canonical setting, for that encompasses private-value auctions with unit demand and binary public good problems.

I consider a setting where multiple sellers of an identical, indivisible good, compete for buyers by simultaneously announcing auctions. I partially characterize the equilibria among sellers in this setting. I show that the oligopoly equilibrium may be in simple (second-price) mechanisms, where the monopolists optimal auction may have been complex (ironing). 

Exclusive social groups are ones in which the group members decide whether or not to admit a candidate to the group. Examples of exclusive social groups include academic departments and fraternal organizations. We introduce an analytic framework for studying the dynamics of exclusive social groups. In our model, every group member is characterized by his opinion, which is represented as a point on the real line. The group evolves in discrete time steps through a voting process carried out by the group's members. Due to homophily, each member votes for the candidate who is more similar to him (i.e., closer to him on the line). An admission rule is then applied to determine which candidate, if any, is admitted. We consider several natural admission rules including majority and consensus.

We ask: how do different admission rules affect the composition of the group in the long term?

We study both growing groups (where new members join old ones) and fixed-size groups (where new members replace those who quit). Our analysis reveals intriguing phenomena and phase transitions, some of which are quite counter-intuitive.

This is a joint work with Noga Alon, Michal Feldman, Yishay Mansour and Moshe Tennenholtz.

Border’s theorem characterizes the possible (interim) allocation probabilities in a single item auction.  It has received much interest lately in Algorithmic Mechanism Design as it allows optimization in Mechanism Design using polynomial-size linear programs rather than the natural exponential-size ones.  Known Generalizations of Border’s theorem beyond the simple case of single item auctions are either very limited or are only approximate. This talk will explain why significant extensions of Border’s theorem are impossible, assuming standard Computational Complexity assumption.  

Joint work with Parikshit Gopalan and Tim Roughgarden.

In discrete allocation problems, Walrasian equilibrium prices have a remarkable property: they allow each agent in the market to purchase a bundle of goods that he independently judges to be the most desirable, while guaranteeing that the jointly induced allocation will globally be social welfare maximizing. However, this otherwise clean story has two caveats:

 -- First, the prices themselves may induce a large number of indifferences among agents that need to be resolved in a coordinated manner. Hence, the prices themselves are not alone sufficient to coordinate the market. In fact, it is not hard to see that the minimal Walrasian equilibrium prices necessarily -always- induce indifferences, for any set of bidder valuations, so we cannot simply appeal to "genericity" to eliminate indifferences.

 -- Second, although we know natural procedures which converge to Walrasian equilibrium prices when used on a fixed population, in practice, we observe and interact with prices that were arrived at independently of our own participation in a tâtonnement process. We expect that these prices therefore are not perfect Walrasian equilibrium prices tailored exactly to the individuals in the market, but rather, that they result from some kind of "distributional" information about the market. This exacerbates the issue of coordination.

We give results of two sorts. First, we show a genericity condition under which the (exact) minimal Walrasian equilibrium prices in a commodity market induce allocations which result in vanishing overdemand for any tie breaking rule that buyers may use to resolve their indifferences. Second, we use techniques from learning theory to argue that the overdemand and welfare induced by a price vector converges to its expectation uniformly over the class of all price vectors, with sample complexity only linear in the number of goods in the market (without placing any assumption on the form of the valuation functions of the buyers).

Combining these two results implies that the exact Walrasian equilibrium prices computed in a commodity market (under a mild genericity condition) are guaranteed to induce both low overdemand and high welfare when used in a new market, in which agents are sampled independently from the same distribution, whenever the number of agents is larger than the number of commodities in the market.

Based on joint work and discussion with Justin Hsu, Jamie Morgenstern, Ryan Rogers, and Rakesh Vohra.