# 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:

 Mohammad Mahdian received a B.S. degree in computer engineering from Sharif University of Technology in 1997, an M.S. degree in computer science from University of Toronto in 2000, and a Ph.D. degree in mathematics from Massachusetts Institute of Technology in 2004.  He has worked as an intern and a postdoctoral researcher at IBM Research Labs and Microsoft Research, and is currently a Research Scientist at Yahoo! Research Lab in Santa Clara, CA.  His current research interests include algorithm design, algorithmic game theory, and applications in online advertising and social networks. Nicole Immorlica is an assistant professor in the Economics Group of Northwestern University's EECS department in Chicago, IL, USA.  She joined Northwestern in Fall 2008 after postdoctoral positions at Microsoft Research in Seattle, Washington, USA and Centruum voor Wiskunde en Informatica (CWI) in Amsterdam, The Netherlands.  She received her Ph.D. from MIT in Boston, MA, USA, in 2005 under the joint supervision of Erik Demaine and David Karger.  Her main research area is algorithmic game theory where she investigates economic and social implications of modern technologies including social networks, advertising auctions, and online auction design. Constantinos (or Costis) Daskalakis grew up in Athens, Greece, where he received an undergraduate degree in Electrical and Computer Engineering from the National Technical University of Athens. In 2004 he moved to California where he completed his doctorate studies in Computer Science at UC Berkeley under the supervision of Professor Christos Papadimitriou. His research interests lie in Algorithmic Game Theory and Applied Probability, particularly in computational aspects of markets and the Internet, in social networks, and in computational problems in Biology. The Game Theory Society honored Costis and his collaborators, Paul Goldberg and Christos Papadimitriou, with the first Game Theory and Computer Science Prize for their work on the Computational Complexity of the Nash equilibrium. Costis was also the recipient of a Microsoft Research Fellowship in honor of Dean Richard Newton, and a UC Regents Fellowship. Costis will join the faculty at MIT in fall 2009, after spending a year in Microsoft Research-New England. Jason Hartline joined the EECS department (and MEDS, by courtesy) in January of 2008. He was a researcher at Microsoft Research, Silicon Valley from 2004 to 2007, where his research covered foundational topic of algorithmic mechanism designand applications to auctions for sponsored search. He was an active researcher in the San Francisco bay area algorithmic game theory community and was a founding organizer of the Bay Algorithmic Game Theory Symposium. In 2003, he held a postdoctoral research fellowship at the Aladdin Center at Carnegie Mellon University. He received his Ph.D. in Computer Science from the University of Washington in 2003 with advisor Anna Karlin. Vahab Mirrokni is a senior research scientist at Google.  He has joined the Google research group in New York, after two years in the Theory Group at Microsoft Research. He received his PhD from Massachusetts Institute of Technology and his B.Sc. from Sharif University of Technology. During his PhD studies, he spent some time doing research at IBM Research, Bell Laboratories, Microsoft Research, and Amazon.com. He is the co-winner of a SODA best student paper award and ACM EC best paper award. His research areas include algorithmic game theory, approximation algorithms, and social network analysis. At Microsoft and Google, he has been working on various algorithmic and economic problems related to the Internet search and online advertisement. Amin Saberi received his B.S. from Sharif Institute of Technology in 2000 and his Ph.D. in Computer Science from Georgia Tech in 2004. He joined the Management Science and Engineering department in Stanford University as an assistant professor after a short postdoc in Microsoft Research. His research focuses on algorithms, algorithmic game theory and applications in the context of the WWW, Internet and other large scale networks.  In his spare time, he enjoys playing volleyball.

Abstracts:

Externalities in Online Advertising

Mohammad Mahdian

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

In many settings, competing technologies -- for example, operating systems, instant messenger systems, or document formats -- can be seen adopting a limited amount of compatibility with one another; in other words, the difficulty in using multiple technologies is balanced somewhere between the two extremes of impossibility and effortless interoperability. There are a range of reasons why this phenomenon occurs, many of which -- based on legal, social, or business considerations -- seem to defy concise mathematical models. Despite this, we show that the advantages of limited compatibility can arise in a very simple model of diffusion in social networks, thus offering a basic explanation for this phenomenon in purely strategic terms. Our approach builds on work on the diffusion of innovations in the economics literature, which seeks to model how a new technology A might spread through a social network of individuals who are currently users of technology B. We consider several ways of capturing the compatibility of A and B, focusing primarily on a model in which users can choose to adopt A, adopt B, or -- at an extra cost -- adopt both A and B. We characterize how the ability of A to spread depends on both its quality relative to B, and also this additional cost of adopting both, and find some surprising non-monotonicity properties in the dependence on these parameters: in some cases, for one technology to survive the introduction of another, the cost of adopting both technologies must be balanced within a narrow, intermediate range. We also extend the framework to the case of multiple technologies, where we find that a simple model captures the phenomenon of two firms adopting a limited "strategic alliance" to defend against a new, third technology.

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

Computing Equilibria in Large Games

Konstantinos Daskalakis

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.

Questions? Please contact Samir Khuller (samir@cs.umd.edu), or Azarakhsh Malekian (malekian@cs.umd.edu).

http://www.cs.umd.edu/~samir/thday08.html
Last updated Sep 14, 2008.