20th Maryland Theoretical Computer Science Day

The University of Maryland Institute for Advanced Computer Studies (UMIACS) is organizing a Theoretical Computer Science Day to be held on Tuesday, Oct 14, 2008 at the University of Maryland, College Park. All talks will be held in room AVW 2460 A.V.Williams Building.

Schedule:

9:15--9:30 Gathering and refreshments

 9:30--10:15 Mohammad Mahdian Yahoo! Research 10:15-- 11:00 Nicole Immorlica Northwestern University The Role of Compatibility in Technology Diffusion on Social Networks 11:00-- 11:45 Konstantinos Daskalakis Microsoft Research Computing Equilibria in Large Games 12:00- 1:30 Lunch on your own 1:30-- 2:15 Jason Hartline Northwestern University Approximation in Multi-dimensional pricing 2:15-- 3:00 Vahab Mirrokni Google Submodular Optimization: Maximization, Learning, and Applications 3:15-- 4:00 Amin Saberi Stanford University Game Dynamics, Equilibrium Selection and Network Structure

Biography:

Abstracts:

Most models for online advertising assume that each ad has an inherent clickthrough-rate/conversion-rate, regardless of other ads served in the same session. This ignores an important externality effect: as the advertising audience has a limited attention span, a high-quality ad on a page can detract attention from other ads on the same page. In this talk, we will describe two models for online advertising that take this effect into account, and discuss the computational complexity of the winner determination problem in these models. One of our models is based on a rational-choice model on the audience side, and the other is based on a probabilistic model of the user behavior. We show that in the most general case of the rational-choice model, the winner determination problem is hard even to approximate. However, there are several interesting special cases, such as when the audience preferences are single peaked, that the problem can be solved efficiently. In such cases, the winner determination algorithm can be combined with standard VCG techniques to yield truthful mechanisms.  In the probabilistic model, which is inspired by a cascade model proposed and empirically evaluated by Craswell et al. for organic search results, we show that the winner determination problem can be solved in polynomial time.

This talk is based on joint work with Arpita Ghosh and David Kempe.

Bio:

The Role of Compatibility in Technology Diffusion on Social Networks

Nicole Immorlica

Joint work with J. Kleinberg, M. Mahdian, and T. Wexler.

Computing Equilibria in Large Games

The Nash equilibrium is one of Game Theory’s most important notions of equilibrium. But, how credible would it be as a framework for behavior prediction in large games such as the Internet, if there were no dynamics by which the game play could converge to such an equilibrium, within a non-prohibitively large number of iterations? Motivated by this question, recent work addressed the computational complexity of the Nash equilibrium, and it has been established that computing an equilibrium is an intractable problem, as hard as any fixed-point computation problem, in a precise technical sense.In view of this hardness result, we are motivated to study the complexity of computing approximate Nash equilibria, with arbitrarily close approximation.  In this regard, we consider a very natural and important class of games, called anonymous games. These are games in which every player is oblivious to the identities of the other players; examples arise in auction settings, congestion games, and social interactions. We present efficient approximation algorithms for anonymous games with a bounded number of strategies.

(Based on joint work with Christos Papadimitriou)

Approximation in Multi-dimensional pricing

Jason Hartline

There are concise characterizations of optimal mechanisms and monopoly pricings in single-dimensional cases (e.g., Myerson's (1981) optimal single-item auction). In multi-dimensional (e.g., multi-product) settings there are no such characterizations. In many simple, relevant settings optimal and even near-optimal item-pricings are computationally intractable. We consider item-pricing for a unit-demand consumer with values for each item drawn independently, perhaps not identically, from a known distribution. We draw a close analogy between this revenue maximization problem and Myerson's single-item auction problem. We show that considering the problem in virtual valuation space instead of valuation space simplifies the problem of approximating the optimal item-pricing. Indeed, with a constant virtual price for each item a seller can approximate the revenue of the optimal item-pricing. We prove an approximation factor of three.

Submodular Optimization: Maximization, Learning, and Applications

Vahab Mirrokni

Optimizing submodular functions in a central problem in combinatorial optimization with several applications. I will present the first constant-factor approximation algorithms for maximizing non-monotone submodular functions. In particular, we give a deterministic local search 1/3-approximation and a randomized 2/5-approximation algorithm for maximizing non-negative submodular functions. Furthermore, we prove that achieving an approximation factor better than 1/2 requires  exponential time. Finally, I will  describe a tight $O(\sqrt{n})$-approximation algorithm for learning a submodular function with polynomial number of queries.
If there is enough interest, I will discuss applications of submodular maximization in the growing field of the online advertisement, and in particular in marketing over social networks.
The talk surveys joint work with Feige, Vondrak (FOCS'07), Hartline, Sundararajan (WWW'08), and Goemans, Iwata, and Harvey (SODA'09).

Game Dynamics, Equilibrium Selection and Network Structure

Amin Saberi

Coordination games describe social or economic interactions in which the adoption of a common strategy has a higher payoff. They are classically used to model the spread of conventions, behaviors, and technologies in societies. Since the pioneering work of Ellison (1993), specific network structures have been shown to have dramatic influence on the convergence of such dynamics. In this talk, I will try to make these results more precise and use the intuition for designing effective algorithms.

Directions: Located just outside of Washington, D.C., College Park is approximately 10 miles from Capitol Hill. To reach the campus from the Capital Beltway, exit at interchange 25B/Route 1 South. You will be on Route 1 (south) for about 2 miles. Make a right (at the traffic light) on Campus Drive and after 40 yards another right onto Paint Branch Drive. After going through on stop sign AV Williams is on your right. However, keep going straight and immediately after the second stop sign you will see a pay lot on your left. Park there. The talks will be in Room 2460 (AV Williams). You may need additional directions if coming from out of town.