Tutorial 12: Games and Design in Signal Processing

Monday, May 27, 2-5 pm

Presented by

Mihaela van der Schaar, William Robin Zame

Abstract

Motivation

A larger and larger fraction of interactions involving humans and machines take place remotely, rather than in person, typically on a network. Remote interactions present enormous challenges - especially to efficiency - because the entities involved (humans, smart machines, humans acting through smart machines) are self-interested (with different interests) and have limited information about each other and about the environment. However, the fact that interactions take place on a network and that they are typically ongoing interactions, presents opportunities for the network manager to manipulate the network environment to achieve a desired goal. If the manager is benevolent (a government, for instance), this goal might be to maximize social welfare or to maximize the welfare of the worst-off entity. If the manager is self-interested and a monopolist, this goal might be to maximize manager revenue. If the manager is self-interested but must compete with other network providers, this goal might be to maximize manager revenue subject to providing a competitive level of benefits net (net of charges) to the entities. This tutorial provides an introduction to strategic design, which provides methodologies and tools for the network manager to accomplish these goals - despite the fact that the entities are self-interested. These methodologies may require active participation by the manager (intervention), but more often only require that the manager sets guidelines but thereafter is completely passive/absent; the methodologies typically exploit the fact that the interactions are ongoing, so that the current actions of each entity can be conditioned on the past actions of that entity and other entities - or on some summary of these actions, a summary that may be manipulated by the manager/designer. The object of the tutorial is to present some of the basic methodologies and tools and some applications of strategic design, to show how it can be used and what it can accomplish.

Multi-Agent Systems

Strategic design treats systems comprised of many entities (agents), but it is important first of all to recognize the difference between strategic design and multi-agent systems. The study of multi-agent systems treats environments in which the participating entities have a common interest and are compliant; the goal of multi-agent systems is to allow the entities to act cooperatively in a distributed fashion, using only local information and without extensive information exchange. In approaches to multi-agent systems, it is assumed that entities will comply with instructions; this assumption is reasonable because the entities have identical goals - the performance of the system as a whole. By contrast, strategic design treats situations in which the participating entities are self-interested and strategic, not necessarily compliant. Entities will only comply with instructions if it is their own self-interest to do so - and their own self-interest will not be the performance of the system as a whole. As is very well known by now, such self-interested behavior tends to lead to inefficient outcomes or to complete system collapse (price of anarchy, tragedy of the commons).

Strategic design can be applied to design a variety of signal processing applications and systems: information production, processing and dissemination in social networks, peer-to-peer networks, social computing systems, online labor markets, online learning in communication systems, recommendation and rating systems; multi-user resource allocation, sharing, and learning in multimedia systems, cognitive radios, smart grids; economics of distributed networks and systems etc.

Tutorial outline

  1. Strategic design: a new research field
    • Multi-agent systems: Examples
    • Cooperative agents
    • Self-interested agents
    • Descriptive (game theory)/Prescriptive (strategic design)
  2. One-shot interactions
    • Implications of self-interest
    • Examples
  3. Ongoing interactions
    • Planning on the future
    • Conditioning on history
    • Reciprocity
      • Direct
      • Indirect
    • What can be observed?
      • Anonymous interactions/Non-anonymous interactions
      • Errors
    • Designing ongoing interactions
      • Tokens
      • Ratings
      • Reviews
  4. Research directions

Speaker Biography

Mihaela van der Schaar

Mihaela van der Schaar is Chancellor's Professor of Electrical Engineering at University of California, Los Angeles. Her research interests include engineering economics and game theory, strategic design, expert and social networks, online reputation and social media, dynamic multi-user networks and system designs, wireless networks, online learning, real-time stream mining, meta-learning and multimedia networking and systems. She is an IEEE Fellow, a Distinguished Lecturer of the Communications Society for 2011-2012, the Editor in Chief of IEEE Transactions on Multimedia and a member of the Editorial Board of the IEEE Journal on Selected Topics in Signal Processing. She received an NSF CAREER Award (2004), the Best Paper Award from IEEE Transactions on Circuits and Systems for Video Technology (2005), the Okawa Foundation Award (2006), the IBM Faculty Award (2005, 2007, 2008), the Most Cited Paper Award from EURASIP: Image Communications Journal (2006), the Gamenets Conference Best Paper Award (2011) and the 2011 IEEE Circuits and Systems Society Darlington Award Best Paper Award. She received three ISO awards for her contributions to the MPEG video compression and streaming international standardization activities, and holds 33 granted US patents. She is also the founding director of the UCLA Center for Engineering Economics, Learning, and Networks (see netecon.ee.ucla.edu).

For more information about her research visit: http://medianetlab.ee.ucla.edu/

William Zame

William Zame is Distinguished Professor in the Departments of Economics and of Mathematics at UCLA and past Director of the California Social Sciences Experimental Laboratory. He is the author/co-author of more than 80 journal articles in pure mathematics, economic theory, finance, experimental economics, and economics and engineering. His research has been recognized by selection as a Fellow of the Econometric Society (1994) and of the John Simon Guggenheim Foundation (2004-2005). He delivered a keynote address at the Bachelier International Finance Congress (2003) and a plenary address at the NBER Conference in Honor of Gerard Debreu (2006). He was formerly Editor-in-Chief of Foundation and Trends in Economics Theory and is currently Co-Editor of Economic Theory. He has organized conferences covering economic theory, finance and experimental economics. He is Co-Founder of the UCLA Center for Learning Engineering Economics and Networks and the Southern California Network Economics and Game Theory (NEGT) Conference series.