Latest EECS News
The Theory Seminar is the joint weekly seminar of the Theory Group and Economics Group in EECS. The Theory Seminar covers theoretical topics in algorithms, complexity, and economics. Seminars will range between neat proofs, informal presentations of local theory, and talks by visiting theoreticians. Approximately once a month the Theory Seminar will coincide with the Algorithmic Game Theory (AGT) Seminar which is the joint seminar of the EECS department and MEDS (Manegerial Economics and Decision Sciences department. In addition to Theory Seminar talks, the calendar lists relevant talks in EECS, MEDS, IEMS, and other departments.
Course Number: EECS 512-3 "Theory Seminar"
Locale: Monday, noon-1:00, Tech A230 (except as noted).
Sponsor: Yahoo! Research.
Our world has been transformed by modern technologies resulting in a mass of shared knowledge and fast, cheap communication. Hand-in-hand with these developments, we have seen the birth of a plethora of new systems for human interaction from marketplaces like eBay and Google's AdWords to online networking services like Facebook and Match.com. These systems give rise to numerous opportunities for scientific exploration, and such studies are fundamental to the future economic and social success of these systems.
The Economics Group in the Electrical Engineering and Computer Science Department at studies the interplay between the algorithmic, economic, and social aspects of the Internet and related systems, and develops ways to facilitate users' interactions in these systems. This work draws upon a wide variety of techniques from theoretical and experimental computer science to traditional economic frameworks. By applying these techniques to economic and social systems in place today, we can shed light on interesting phenomena and, ideally, provide guidance for future developments of these systems. This interdisciplinary effort is undertaken jointly with the Managerial Economics and Decision Sciences Department in the Kellogg School of Management, The Center for Mathematical Studies in Economics and Management Science, and other institutions at Northwestern University and the greater Chicago area.
Specific topics under active research include: algorithmic mechanism design, applied mechanism design, bounded rationality, market equilibria, network protocol design, prediction markets, security, social networks, and wireless networking. They are described in more detail below.
Algorithmic Mechanism Design. Mechanism design (in economics) studies how to design economic systems (a.k.a., mechanisms) that have good properties. Algorithm design (in computer science) studies how to design algorithms with good computational properties. Algorithmic mechanism design combines economic and algorithmic analyses, in gauging the performance of a mechanism; with optimization techniques for finding the mechanism that optimizes (or approximates) the desired objective. (Contact: Hartline, Immorlica)
Applied Mechanism Design. Internet services are fundamentally economic systems and the proper design of Internet services requires resolving the advice of mechanism design theory, which often formally only applies in ideological models, with practical needs and real markets and other settings. The interplay between theory and practice is fundamental for making the theoretical work relevant and developing guidelines for designing Internet systems, including auctions like eBay and Google's AdWords auction, Internet routing protocols, reputation systems, file sharing protocols, etc. For example the problem auctioning of advertisements on Internet search engines such as Yahoo!, Google, and Live Search, exemplifies many of the theoretical challenges in mechanism design as well as being directly relevant to a multi-billion dollar industry. Close collaboration with industry in this area is a focus. (Contact: Hartline, Immorlica)
Bounded Rationality. Traditional economic models assume that all parties understand the full consequences of their actions given the information they have, but often computational constraints limit their ability to make fully rational decisions. Properly modeling bounded rationality can help us better understand equilibrium in games, forecast testing, preference revelation, voting and new ways to model difficult concepts like unforeseen consequences in contracts and brand awareness. (Contact: Hartline)
Market Equilibria. The existence of equilibria has been the most important property for a "working" market or economy, and the most studied one in Economics. Existence of a desirable equilibrium is not enough; additionally, the market must converge naturally and quickly to this equilibrium. Of special interest here are decentralized algorithms, ones that do not rely on a central agent, that demonstrate how individual actions in a market may actually working in harmony to reach an equilibrium. (Contact: Zhou)
Network Protocol Design. Much of the literature on designing protocols assumes that all or most participants are honest and blindly follow instructions, whereas the rest may be adversarial. This is particularly apparent in distributed computing, where the aim is to achieve resilience against faults, and in cryptography, where the aim is to achieve security against a malicious adversary. A crucial question is whether such resilient protocols can also be made faithful -- that is, whether the (often unrealistic) assumption of honest participants can be weakened to an assumption of self-interested ones. Another question is whether one may be able to side-step impossibility results on the resilience of protocols by considering adversarial coalitions who do not act maliciously but rather in accordance with their own self-interests. (Contact: Gradwohl)
Prediction Markets. Prediction markets are securities based usually on a one-time binary event, such as whether Hillary Clinton will win the 2008 election. Market prices have been shown to give a more accurate prediction of the probability of an event happening than polls and experts. Several corporations also use prediction markets to predict sales and release dates of products. Our research considers theoretical models of these markets to understand why they seem to aggregate information so well, "market scoring rules" that allow prediction markets even with limited liquidity, the effect of market manipulation and ways to design markets and their presentation to maximize the usefulness of their predictive value. (Contact: Hartline)
Security. With the increasing popularity of Internet and the penetration of cyber-social networks, the security of computation and communication systems has become a critical issue. The traditional approach to system security assumes unreasonably powerful attackers and often end up with intractability. An economic approach to system security models the attacker as a rational agent who can be thwarted if the cost of attack is high.(Contact: Zhou)
Social Networks. A social network is a collection of entities (e.g., people, web pages, cities), together with some meaningful links between them. The hyperlink structure of the world-wide-web, the graph of email communications at a company, the co-authorship graph of a scientific community, and the friendship graph on an instant messenger service are all examples of social networks. In recent years, explicitly represented social networks have become increasingly common online, and increasingly valuable to the Internet economy. As a result, researchers have unprecedented opportunities to develop testable theories of social networks pertaining to their formation and the adoption and diffusion of ideas/technologies within these networks. (Contact: Immorlica)
Wireless Networking. Recent advances in reconfigurable radios can potentially enable wireless applications to locate and exploit underutilized radio frequencies (a.k.a., spectrum) on the fly. This has motivated the consideration of dynamic policies for spectrum allocation, management, and sharing; a research initiative that spans the areas of wireless communications, networking, game theory, and mechanism design. (Contact: Berry, Honig)
Theoretical computer science looks at fundamental questions about computation by creating formal models of computation and understanding the resources needed to solve general and specific algorithmic questions.
The theoretical computer science at Northwestern group has expertise in algorithms and computational complexity, with a particular emphasis on how they relate to economic questions.
Jason Hartline. Prof. Hartline has interests in randomized, online, and approximation algorithms and their application in multi-user settings such as the Internet. This field is known as algorithmic mechanism design and lies at the intersection of the theoretical computer science topic of algorithms and the microeconomic topic of mechanism design. He employs algorithmic design and analysis techniques to traditional economics problems to arrive at an algorithmic theory of mechanism design that is more appropriate for computer science settings than the traditional economic theory. One contribution of his work develops approximation and online algorithm techniques for designing mechanisms with good worst case properties. He has also reformulated fair resource allocation as an algorithmic pricing problem. This research lays the foundation for the future of computer science as the focus shifts from single-user algorithms to multi-user and Internet algorithms where algorithm correctness relies fundamentally on economic precepts.
Hartline also has interests in data structures, functional programming languages, and machine learning theory.
Nicole Immorlica. Prof. Immorlica studies algorithms and economics. She especially has interests in problems with applications to market design. How can we improve the efficiencies of current markets? Predict the success of particular technologies? Effectively engineer optimal social policies? In particular, her recent work has focused on advertising markets including sponsored search auctions, matching markets such as the National Residency Matching Program, and diffusion of innovations in social networks.
Ming-Yang Kao. Prof. Kao studies the design, analysis and implementation of algorithms. His work spans a broad range of applications including bioinformatics, computational finance, electronic commerce, and nanotechnology. Kao's most recent research includes work on DNA self-assembly, variants of the traveling salesman problem, and graph labeling problems.
Kao heads the EECS Computing, Algorithms & Applications Division and is the editor-in-chief of Algorithmica.