Economic and Social Systems - Algorithmic Economics

By David Pennock


The design of Internet services requires an understanding of both computer science and economics: CS to get the engineering and algorithms right; economics to get user behavior and monetization right.

Historically, Internet services focused on engineering and caricatured users as either cooperative or malicious. In truth, few users are purely benevolent, and fewer still are vandals: even spammers act in response to rational economic calculations.

Nearly all mass-market services, including email, web search, social networks, recommendations, user content, and ad networks, are beset by attempts at manipulation. New services like the semantic web are immune only while they remain niche.

Even monetization efforts are guided by technology ahead of economics. Understanding how to align the incentives of participants with system-wide objectives is fundamental to the design of the next generation of web-scale services. Increasingly, design teams will require dual expertise in social science and computer science, adding competence in economics, sociology, and psychology to more traditionally recognized requirements like algorithms, interfaces, systems, machine learning, and optimization.

The need for hybrid CS/econ science is crucial as markets of all types move to electronic platforms, as exchanges support more expressive combinatorial bidding, as people rely on programmatic aids, as market designers utilize equilibrium simulations, and as machine learning becomes part of the inner loop of market clearing algorithms.

Significant CS/econ research groups have emerged in the last several years, including industry labs at Google, Microsoft, and Yahoo! and academic groups at Cornell, Georgia Tech, Harvard, Northwestern, Stanford, U Michigan, and U Penn. For a look at the front lines of research, see publications and venues like AGT, AMMA, BAGT, EC, GEB, EI, NYCE, SAGT, WINE, and WWW.

Challenges

Incentive-centered design

For too long, understanding incentives has been an emergency afterthought in the design of Internet systems (think spam). How can we bring incentives to the forefront of the design process?
(Read article: Incentive-centered design.)

Internet monetization

Currently advertising dominates, with trends toward increasing automation, including the sale, delivery, and measurement of ads. We're still in early days of industry growth and scientific progress. Success means striking a game-theoretic balance among users, publishers, and advertisers. We have effective means of monetizing search, less so content and social media. What modes of advertising work best in what contexts? When might advertising fail?

Behavior in social networks

How do ideas, information, and behavioral norms spread in a social network, and how can such processes be influenced by means of advertising, recommendation, and viral marketing?

Modeling user attention

Attention is one of the most valuable commodities in the world, bought via advertising. How can we reward and protect users? Are there different attention qualities? How can attention be measured, grown, and priced?

Algorithmic game theory and algorithmic mechanism design

What are the computational implications of incentive constraints? How does the reality of computational limits change market design and economic models? For example, how can we characterize and reduce the gap between equilibrium and global solutions (the so-called "price of anarchy")?

Economic computations

Effective algorithms are required for economic calculations like market equilibria in exchanges, Nash equilibria in games, combinatorial auctioneers, and market makers. Predicting economic behavior means understanding which equilibria are reachable with reasonable computational effort. When an economic calculation is computationally intractable, as recently proven for Nash equilibria, what are good heuristics, tractable special cases, or approximation algorithms?

Wisdom of crowds

How can prediction markets and other group tools help us improve predictions and decisions by harnessing a diverse user base? How can we design markets to maximize forecast accuracy?

Mixed Bayesian and worst-case optimization

How can we trade-off or combine econ-style Bayesian objectives and CS-style worst-case objectives for optimization?

Balancing expressiveness with automation

What information must come from bidders and what can be optimized "black-box style"? How are bidders' preferences structured and how can we query them? Can we develop fast pricing and allocation algorithms to meet their demands? How do we balance expressiveness with computational complexity?

Integrating learning and allocation

How can allocation algorithms and machine learning algorithms interact, including balancing exploration and exploitation? In advertising, how do we mix expressive targeting languages with automated machine-learned matching of users to ads?

Adversarial machine learning

How can machines learn in a game-theoretic environment, for example spam filters in the arms race against spammers?