Mohammad Mahdian
Yahoo! Research
Nicole Immorlica
Northwestern University
Konstantinos Daskalakis
Microsoft Research
Jason Hartline
Northwestern University
Vahab Mirrokni
Amin Saberi
Stanford University
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 |
||
| 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 |
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-
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
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
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
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).