Confirmed Speakers

Learning valuation functions

A core element of microeconomics and game theory is that consumers have valuation functions over bundles of goods and that these valuation functions drive their purchases. In particular, the value given to a bundle need not be the sum of values on the individual items but rather can be a more complex function of how the items relate. Common valuation classes considered in the literature include OXS, submodular, and XOS valuations. Typically it is assumed that these valuations are known to the center or come from a known distribution. In this work we initiate the study of the approximate learnability of valuation classes in a distributional learning setting. We prove upper and lower bounds on the approximation guarantees achievable for learning over general data distributions by using only a polynomial number of examples.
Our work combines central issues in economics with central issues in optimization (submodular functions and matroids) with central issues in learning (learnability of natural but complex classes of functions in a distributional setting). Our analysis brings a twist on the usual learning theory models and uncovers some interesting structural and extremal properties of submodular functions, which are likely to be useful in other contexts as well.

The price of uncertainty: safety conditions for multiagent systems

Suppose that, through whatever means, a system has been able to reach a low-cost equilibrium state. What assurances can one provide that the state will not arbitrarily deteriorate? We in particular consider a model in which players in a potential game experience a small degree of uncertainty about their true costs, and therefore can be expected only to perform "nearly-best-response" actions to the current state. We consider a variety of potential games including fair cost-sharing games, set-cover games, routing games, and job-scheduling games. We show that in certain cases, even extremely small fluctuations in perceived costs can cause dynamics to spin out of control and move to states of much higher social cost, whereas in other cases these dynamics are much more stable even to large fluctuations. We also consider the resilience of these dynamics to a small number of Byzantine players about which no assumptions are made. We show that in certain cases even a single Byzantine player can cause best-response dynamics to transition to states of substantially higher cost, whereas in others these dynamics are much more resilient. Joint work with Maria-Florina Balcan and Yishay Mansour

Crowdsourced Bayesian Auctions

We investigate the problem of generating revenue in auctions when the valuations of the players are jointly drawn from a (perhaps correlated) distribution D and "the players know each other better than the seller knows them." That is, when only the players have some information about D, so that the seller needs to elicit their help to sell the goods: he needs to crowdsource the auction to the players.
We work under a "very weak decentralized Bayesian assumption". Not only no information about D is common knowledge to the players, but no player even individually knows D. In fact, in our crowdsourced Bayesian assumption each player i only individually knows an arbitrary refinement of D|ti, that is, D.s posterior based on his own type ti.
Yet, we prove that such a weak assumption enables the seller to generate revenue that in expectation is close to the one he could generate by means of an optimal dominant-strategy-truthful mechanism if he himself knew D. Our results are "existential" for all auctions, and "constructive" for single-good ones. Joint work with Pablo Azar and Silvio Micali.

Algorithms for Security Games

I will talk about our work on algorithms for computing game-theoretic solutions (Stackelberg and Nash) in security games.
Joint work with Dmytro Korzhyk, Joshua Letchford, Kamesh Munagala, Ronald Parr (Duke); Manish Jain, Zhengyu Yin, Milind Tambe (USC); Christopher Kiekintveld (UT El Paso); Ondrej Vanek, Michal Pechoucek (Czech Technical University); and Tuomas Sandholm (CMU).

Bounding the Power of Truthfulness

It is widely believed that the power of computationally-efficient truthful mechanisms is severely limited. However, up until recently the community was missing the tools to prove this statement. In this talk we will discuss why previous attempts failed and some recent progress in proving bounds on the power of computationally-efficient truthful mechanisms. Specifically, we will demonstrate two techniques for proving impossibilities in two important settings: multi-unit auctions and combinatorial auctions with submodular valuations.

Revenue Maximization in Probabilistic Single-Item Auctions via Signaling

Signaling is an important topic in the study of asymmetric information in economic settings. In particular, the transparency of information available to a seller in an auction setting is a question of major interest. We introduce the study of signaling when auctioning a probabilistic good whose actual instantiation is known to the auctioneer but not to the bidders. In particular, this can be used to model impressions selling in display advertising. Our study focuses on finding an optimal signaling scheme, captured by a segmentation of the possible goods into disjoint clusters. We show that while the problem is computationally hard, it possesses constant approximation for natural families of distribution functions over bidders valuations for the goods. Joint work with Yuval Emek, Iftah Gamzu and Moshe Tennenholtz

Competitive Strategies for Routing Flow Over Time.

The study of routing games is motivated by the desire to understand the impact of individual user's decisions on network efficiency. To do this, prior work uses a simplified model of network flow where all flow exists simultaneously, and users route flow to either their maximum delay or their total delay. Both of these measures are surrogates for measuring how long it takes to get all of your traffic through the network over time.
Instead of using these surrogates, we attempt a more direct study of how competition among users effects network efficiency by examining routing games in a flow-over-time model. We show that the network owner can reduce available capacity so that the competitive equilibrium in the reduced network is no worse than a small constant times the optimal solution in the original network using two natural measures of optimum: the time by which all flow reaches the destination, and the average amount of time it takes flow to reach the destination. Joint work with Umang Bhaskar (Dartmouth) and Elliot Anshelevich (RPI).

Comparing and Measuring Risks

Stochastic dominance is a partial order on risky assets ("gambles") that is based on the uniform preference---of all decision-makers of an appropriate class---for one gamble over another. We modify this requirement, first, by taking into account the status quo (given by the current wealth) and the possibility of rejecting gambles, and second, by comparing rejections that are substantive (that is, uniform over wealth levels or over utilities). This yields two new stochastic orders: "wealth-uniform dominance" and "utility-uniform dominance". Unlike stochastic dominance, these two orders are _complete_: any two gambles can be compared. Moreover, they are equivalent to the orders induced by, respectively, the Aumann-Serrano (JPE 2008) index of riskiness and the Foster-Hart (JPE 2009) measure of riskiness.
http://www.ma.huji.ac.il/hart/abs/risk-u.html
http://www.ma.huji.ac.il/hart/abs/risk.html

Dueling Algorithms

We revisit classic algorithmic search and optimization problems from the perspective of competition. Rather than a single optimizer minimizing expected cost, we consider a zero-sum game in which an optimization problem is presented to two players, whose only goal is to outperform the opponent. Such games are typically exponentially large zero-sum games, but they often have a rich combinatorial structure. We provide general techniques by which such structure can be leveraged to find minmax-optimal and approximate minmax-optimal strategies. We give examples of ranking, hiring, compression, and binary search duels, among others. We give bounds on how often one can beat the classic optimization algorithms in such duels. Joint work with Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, and Moshe Tennenholtz.

Selling in exclusive markets: some observations about prior-free profit maximization.

We study the problem of designing truthful mechanisms to maximize a seller profit without prior knowledge of buyers' valuations. We look at a very simple setting where the seller can sell to any number of buyers in one of two exclusive markets. We show that even in this simple setting, a strong benchmark proposed by Hartline and Roughgarden (STOC' 08) is unattainable - that is, no truthful in expectation mechanism can be constant competitive to this benchmark. On the other hand, competitiveness to a symmetrized version of this benchmark is attained by a very simple mechanism. Joint work with Thach Nguyen and Yuval Peres.

Dominant-Strategy Auction Design for Agents with Uncertain, Private Values

We study the problem of designing auctions for agents who incur a cost if they choose to learn about their own preferences. We reformulate the revelation principle for use with such deliberative agents. Then we characterize the set of single-good auctions giving rise to dominant strategies for deliberative agents whose values are independent and private. Interestingly, this set of dominant-strategy mechanisms is exactly the set of sequential posted-price auctions, a class of mechanisms that has received much recent attention. This talk will describe joint work with David R.M. Thompson.

Welfare and Profit Maximization with Production Costs

Combinatorial Auctions are a central problem in Algorithmic Mechanism Design: pricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e.g., social welfare, revenue, or profit). The problem has been well-studied in the case of limited supply (one copy of each item), and in the case of digital goods (the seller can produce additional copies at no cost). Yet the case of resources---think oil, labor, computing cycles, etc.---neither of these abstractions is just right: additional supplies of these resources can be found, but only at a cost (where the marginal cost is an increasing function).
In this work, we initiate the study of the algorithmic mechanism design problem of combinatorial pricing under increasing marginal cost. The goal is to sell these goods to buyers with unknown and arbitrary combinatorial valuation functions to maximize either the social welfare, or our own profit; specifically we focus on the setting of \emph{posted item prices} with buyers arriving online. We give algorithms that achieve constant factor approximations for a class of natural cost functions---linear, low-degree polynomial, logarithmic---and that give logarithmic approximations for all convex marginal cost functions (along with a necessary additive loss). We show that these bounds are essentially best possible for these settings. This is a joint work with Avrim Blum, Anupam Gupta and Ankit Sharma

If not agreeing to disagree then agreeing on what?

Beginning with results of Aumann and Geanakoplos & Polemarchakis extensive research has been devoted to establishing conditions under which repeated actions in a Bayesian setup lead to a common posterior.
However, the analytic and computational difficulties involved in Bayesian game theory prevented thus-far from obtaining useful information regarding the value of the common posterior except in very simple cases.
I will describe some recent work (with Omer Tamuz) presenting models where the Bayesian updates are computationally feasible and Bayesian learning is statistically consistent for large number of players on general connected networks followed by very recent developments (with Allan Sly and Omer Tamuz) showing that even for models where efficient Bayesian implementations are not known Bayesian learning is statistically consistent in a very general setup.

Non-Price Equilibria in Markets of Discrete Goods

We study markets of indivisible items in which price-based (Walrasian) equilibria often do not exist due to the discrete non-convex setting. Instead we consider Nash equilibria of the market viewed as a game, where players bid for items, and where the highest bidder on an item wins it and pays his bid. We first observe that pure Nash-equilibria of this game excatly correspond to price-based equilibiria (and thus need not exist), but that mixed-Nash equilibria always do exist, and we analyze their structure in several simple cases where no price-based equilibrium exists. We also undertake an analysis of the welfare properties of these equilibria showing that while pure equilibria are always perfectly efficient ("first welfare theorem"), mixed equilibria need not be, and we provide upper and lower bounds on their amount of inefficiency. Joint work with Avinatan Hassidim, Haim Kaplan and Yishay Mansour

Title - TBD

Tight Bounds for Strategyproof Classification

Strategyproof (SP) classification considers situations in which a decision-maker must classify a set of input points with binary labels, minimizing expected error. Labels of input points are reported by self-interested agents, who may lie so as to obtain a classifier more closely matching their own labels. These lies would create a bias in the data, and thus motivate the design of truthful mechanisms that discourage false reporting.
I'll present an overview of our work on strategyproof classification, and answer some questions left open by previous research on the topic, in particular regarding the best approximation ratio (in terms of social welfare) that an SP mechanism can guarantee for n agents. Our primary result is a lower bound of on the approximation ratio of SP mechanisms under the shared inputs assumption; this shows that the previously known upper bound (for uniform weights) is tight. The proof relies on a result from Social Choice theory, showing that any SP mechanism must select a dictator at random, according to some fixed distribution. We then show how different randomizations can improve the best known mechanism when agents are weighted, matching the lower bound with a tight upper bound. These results contribute both to a better understanding of the limits of SP classification, as well as to the development of similar tools in other, related domains such as SP facility location and judgment aggregation. This is joint work with Reshef Meir, Shaull Almagor, and Assaf Michaely.

Network Formation in the Presence of Contagious Risk

There are a number of domains where agents must collectively form a network in the face of the following trade-off: each agent receives benefits from the direct links it forms to others, but these links expose it to the risk of being hit by a cascading failure that might spread over multi-step paths. Financial contagion, epidemic disease, and the exposure of covert organizations to discovery are all settings in which such issues have been articulated. In this talk we formulate the problem in terms of strategic network formation, and provide asymptotically tight bounds on the welfare of both optimal and stable networks. Our analysis enables us to explore such issues as the trade-offs between clustered and anonymous market structures, and it exposes a fundamental sense in which very small amounts of "over-linking" in networks with contagious risk can have strong consequences for the welfare of the participants. Joint work with Larry Blume, David Easley, Jon Kleinberg, and Robert Kleinberg

Extending General Equilibrium Theory to the Digital Economy

General Equilibrium Theory, the undisputed crown jewel of Mathematical Economics for over a century, gave a very satisfactory solution to the central problem of arriving at a principled method of pricing goods and services -- one that leads to an efficient allocation of scarce resources among alternative uses. The solution was based on Adam Smith's principle of maintaining parity between supply and demand, Walras' notion of equilibrium, and the Arrow-Debreu Theorem, which proved the existence of equilibrium in a very general model of the economy.
However, this solution, designed for conventional goods, is not applicable for digital goods -- once produced, a digital good can be reproduced at (essentially) zero cost, thus making its supply infinite. Considering the current size of the digital economy and its huge growth potential, it is imperative that we obtain an equally convincing theory for pricing of digital goods. In this talk, I will describe what appears to be a first step in this direction.
After taking into consideration idiosyncrasies of the digital realm, we give a market model that is appropriate for the digital setting, a notion of equilibrium for this model, and a proof of existence of equilibrium using Kakutani's fixed point theorem. For a special case, we also give a polynomial time algorithm and we show that a rational equilibrium always exists. Finally, I will outline a multitude of issues that still need to be addressed to obtain a theory for the digital economy that is on par with the original theory.
Based on the joint paper with Kamal Jain: http://arxiv.org/abs/1007.4586