Chapters (26)
Last 3 years (1)
Cambridge University Press (27)
38 - Solving the Station Repacking Problem
from Part VI - Secondary Markets and Exchanges
By Alexandre Fréchette, Department of Computer Science, University of British Columbia, Neil Newman, Department of Computer Science, University of British Columbia, Kevin Leyton-Brown, Department of Computer Science, University of British Columbia
Edited by Martin Bichler, Technische Universität München, Jacob K. Goeree, University of New South Wales, Sydney
Book: Handbook of Spectrum Auction Design
Print publication: 26 October 2017, pp 813-827
Over 13 months in 2016–17, the US government held an innovative "incentive auction" for radio spectrum, in which television broadcasters were paid to relinquish broadcast rights via a "reverse auction", remaining broadcasters were repacked into a narrower band of spectrum, and the cleared spectrum was sold to telecommunications companies. The stakes were enormous: the auction was forecast to net the government tens of billions of dollars, as well as creating massive economic value by reallocating spectrum to more socially beneficial uses (Congressional Budget Office 2015). As a result of both its economic importance and its conceptual novelty, the auction has been the subject of considerable recent study by the research community, mostly focusing on elements of the auction design (Bazelon, Jackson, and McHenry 2011; Kwerel, LaFontaine, and Schwartz 2012; Milgrom et al. 2012; Calamari et al. 2012; Marcus 2013; Milgrom and Segal 2014; Dütting, Gkatzelis, and Roughgarden 2014; Vohra 2014; Nguyen and Sandholm 2014; Kazumori 2014). After considerable study and discussion, the FCC has selected an auction design based on a descending clock (FCC 2014c; 2014a). Such an auction offers each participating station a price for relinquishing its broadcast rights, with this price offer falling for a given station as long as it remains repackable. A consequence of this design is that the auction must (sequentially!) solve hundreds of thousands of such repacking problems. This is challenging, because the repacking problem is NP-complete. It also makes the performance of the repacking algorithm extremely important, as every failure to solve a single, feasible repacking problem corresponds to a lost opportunity to lower a price offer. Given the scale of the auction, individual unsolved problems can cost the government millions of dollars each.
This chapter shows how the station repacking problem can be solved exactly and reliably at the national scale. It describes the results of an extensive, multi-year investigation into the problem, which culminated in a solver that we call SATFC.
Yoav Shoham, Stanford University, California, Kevin Leyton-Brown, University of British Columbia, Vancouver
Book: Multiagent Systems
Print publication: 15 December 2008, pp i-vi
13 - Logics of Knowledge and Belief
Print publication: 15 December 2008, pp 393-420
In this chapter we look at how one might represent statements such as "John knows that it is raining," "John believes that it will rain tomorrow," "Mary knows that John believes that it will rain tomorrow" and "It is common knowledge between Mary and John that it is raining."
The partition model of knowledge
Consider a distributed system, in which multiple processors autonomously performing some joint computation. Of course, the joint nature of the computation means that the processors need to communicate with one another. One set of problems comes about when the communication is error prone. In this case the system analyst may find himself saying something like the following: "Processor A sent the message to processor B. The message may not arrive, and processor A knows this. Furthermore, this is common knowledge, so processor A knows that processor B knows that it (A) knows that if a message was sent it may not arrive." The topic of this chapter is how to make such reasoning precise.
Muddy children and warring generals
Often the modeling is done in the context of some stylized problem, with an associated entertaining story. Thus, for example, when we return to the distributed computing application in Section 13.4, rather than speak about computer processors, we will tell the story of two generals who attempt to coordinate among themselves to gang up on a third.
3 - Introduction to Noncooperative Game Theory: Games in Normal Form
Print publication: 15 December 2008, pp 47-86
Game theory is the mathematical study of interaction among independent, self-interested agents. It has been applied to disciplines as diverse as economics (historically, its main area of application), political science, biology, psychology, linguistics—and computer science. In this chapter we will concentrate on what has become the dominant branch of game theory, called noncooperative game theory, and specifically on normal-form games, a canonical representation in this discipline.
As an aside, the name "noncooperative game theory" could be misleading, since it may suggest that the theory applies exclusively to situations in which the interests of different agents conflict. This is not the case, although it is fair to say that the theory is most interesting in such situations. By the same token, in Chapter 12 we will see that coalitional game theory (also known as cooperative game theory) does not apply only in situations in which the interests of the agents align with each other. The essential difference between the two branches is that in noncooperative game theory the basic modeling unit is the individual (including his beliefs, preferences, and possible actions) while in coalitional game theory the basic modeling unit is the group. We will return to that later in Chapter 12, but for now let us proceed with the individualistic approach.
Self-interested agents
What does it mean to say that agents are self-interested? It does not necessarily mean that they want to cause harm to each other, or even that they care only about themselves.
11 - Protocols for Multiagent Resource Allocation: Auctions
In this chapter we consider the problem of allocating (discrete) resources among selfish agents in a multiagent system. Auctions—an interesting and important application of mechanism design—turn out to provide a general solution to this problem. We describe various different flavors of auctions, including single-good, multiunit, and combinatorial auctions. In each case, we survey some of the key theoretical, practical, and computational insights from the literature.
The auction setting is important for two reasons. First, auctions are widely used in real life, in consumer, corporate, as well as government settings. Millions of people use auctions daily on Internet consumer Web sites to trade goods. More complex types of auctions have been used by governments around the world to sell important public resources such as access to electromagnetic spectrum. Indeed, all financial markets constitute a type of auction (one of the family of so-called double auctions). Auctions are also often used in computational settings, to efficiently allocate bandwidth and processing power to applications and users.
The second—and more fundamental—reason to care about auctions is that they provide a general theoretical framework for understanding resource allocation problems among self-interested agents. Formally speaking, an auction is any protocol that allows agents to indicate their interest in one or more resources and that uses these indications of interest to determine both an allocation of resources and a set of payments by the agents.
Print publication: 15 December 2008, pp xv-xvi
D - Classical Logic
from Appendices: Technical Background
The following is not intended as an introduction to classical logic, but rather as a review of the concepts and a setting of notation. We start with propositional calculus and then move to first-order logic. (We do the latter for completeness, but in fact first-order logic plays almost no role in this book.)
Propositional calculus
Given a set P of propositional symbols, the set of sentences in the propositional calculus is the smallest set ℒ containing P such that if φ, ψ ∈ ℒ then also ¬φ ∈ ℒ and ∈ ∧ ψ ℒ. Other connectives such as ∨, →, and ≡ can be defined in terms of ∧ and ¬.
A propositional interpretation (or a model) is a set M ⊂ P, the subset of true primitive propositions. The satisfaction relation ⊧ between models and sentences is defined recursively as follows.
For any p ∈ P, M ⊧ p iff p ∈ M.
M ⊧ φ ∧ ψ iff M ⊧ φ and M ⊧ ψ.
M ⊧ ¬φ iff it is not the case that M ⊧ φ.
We overload the ⊧ symbol. First, it is used to denote validity; ⊧ φ means that φ is true in all propositional models. Second, it is used to denote entailment; φ ⊧ ψ means that any model that satisfies φ also satisfies ψ.
5 - Games with Sequential Actions: Reasoning and Computing with the Extensive Form
In Chapter 3 we assumed that a game is represented in normal form: effectively, as a big table. In some sense, this is reasonable. The normal form is conceptually straightforward, and most see it as fundamental. While many other representations exist to describe finite games, we will see in this chapter and in Chapter 6 that each of them has an "induced normal form": a corresponding normal-form representation that preserves game-theoretic properties such as Nash equilibria. Thus the results given in Chapter 3 hold for all finite games, no matter how they are represented; in that sense the normal-form representation is universal.
In this chapter we will look at extensive-form games, a finite representation that does not always assume that players act simultaneously. This representation is in general exponentially smaller than its induced normal form, and furthermore can be much more natural to reason about. While the Nash equilibria of an extensiveform game can be found through its induced normal form, computational benefit can be had by working with the extensive form directly. Furthermore, there are other solution concepts, such as subgame-perfect equilibrium (see Section 5.1.3), which explicitly refer to the sequence in which players act and which are therefore not meaningful when applied to normal-form games.
Perfect-information extensive-form games
The normal-form game representation does not incorporate any notion of sequence, or time, of the actions of the players.
10 - Protocols for Strategic Agents: Mechanism Design
As we discussed in the previous chapter, social choice theory is nonstrategic; it takes the preferences of the agents as given, and investigates ways in which they can be aggregated. But of course those preferences are usually not known. What you have, instead, is that the various agents declare their preferences, which they may do truthfully or not. Assuming the agents are self interested, in general they will not reveal their true preferences. Since as a designer you wish to find an optimal outcome with respect to the agents' true preferences (e.g., electing a leader that truly reflects the agents' preferences), optimizing with respect to the declared preferences will not in general achieve the objective.
Mechanism design is a strategic version of social choice theory, which adds the assumption that agents will behave so as to maximize their individual payoffs. For example, in an election agents may not vote their true preference.
Example: strategic voting
Consider again our babysitting example. This time, in addition to Will, Liam, and Vic you must also babysit their devious new friend, Ray. Again, you invite each child to select their favorite among the three activities—going to the video arcade (a), playing basketball (b), and going for a leisurely car ride (c). As before, you announce that you will select the activity with the highest number of votes, breaking ties alphabetically.
C - Markov Decision Problems (MDPs)
We briefly review the main ingredients of Markov Decision Problems or MDPs, which, as we discuss in Chapter 6, can be viewed as single-agent stochastic games. The literature on MDPs is rich, and the reader is referred to the many textbooks on the subject for further reading.
An MDP is a model for decision making in an uncertain, dynamic world. The (single) agent starts out in some state, takes an action, and receives some immediate rewards. The state then transitions probabilistically to some other state and the process repeats. Formally speaking, an MDP is a tuple (S,A,p,R). S is a set of states and A is a set of actions. The function p : S × A × S ↦ ℝ specifies the transition probability among states: p(s, a, s′) is the probability of ending in state s′ when taking action a in state s. Finally, the function R : S × A ↦ ℝ returns the reward for each state-action pair.
12 - Teams of Selfish Agents: An Introduction to Coalitional Game Theory
In Chapters 1 and 2 we looked at how teams of cooperative agents can accomplish more together than they can achieve in isolation. Then, in Chapter 3 and many of the chapters that followed, we looked at how self-interested agents make individual choices. In this chapter we interpolate between these two extremes, asking how self-interested agents can combine to form effective teams. As the title of the chapter suggests, this chapter is essentially a crash course in coalitional game theory, also known as cooperative game theory. As was mentioned at the beginning of Chapter 3, when we introduced noncooperative game theory, the term "cooperative" can be misleading. It does not mean that, as in Chapters 1 and 2, each agent is agreeable and will follow arbitrary instructions. Rather, it means that the basic modeling unit is the group rather than the individual agent. More precisely, in coalitional game theory we still model the individual preference of agents, but not their possible actions. Instead, we have a coarser model of the capabilities of different groups.
We proceed as follows. First, we define the most widely studied model of coalitional games, give examples of situations that can be modeled in this way, and discuss a series of refinements to the model. Then we consider how such games can be analyzed. The main solution concepts we discuss here are the Shapley value, the core, and the nucleolus.
Appendices: Technical Background
6 - Richer Representations: Beyond the Normal and Extensive Forms
In this chapter we will go beyond the normal and extensive forms by considering a variety of richer game representations. These further representations are important because the normal and extensive forms are not always suitable for modeling large or realistic game-theoretic settings.
First, we may be interested in games that are not finite and that therefore cannot be represented in normal or extensive form. For example, we may want to consider what happens when a simple normal-form game such as the Prisoner's Dilemma is repeated infinitely. We might want to consider a game played by an uncountably infinite set of agents. Or we may want to use an interval of the real numbers as each player's action space.
Second, both of the representations we have studied so far presume that agents have perfect knowledge of everyone's payoffs. This seems like a poor model of many realistic situations, where, for example, agents might have private information that affects their own payoffs and other agents might have only probabilistic information about each others' private information. An elaboration like this can have a big impact, because one agent's actions can depend on what he knows about another agent's payoffs.
Finally, as the numbers of players and actions in a game grow—even if they remain finite—games can quickly become far too large to reason about or even to write down using the representations we have studied so far.
2 - Distributed Optimization
In the previous chapter we looked at distributed ways of meeting global constraints. Here we up the ante; we ask how agents can, in a distributed fashion, optimize a global objective function. Specifically, we consider four families of techniques and associated sample problems. They are, in order:
distributed dynamic programming (as applied to path-planning problems);
distributed solutions to Markov Decision Problems (MDPs);
optimization algorithms with an economic flavor (as applied to matching and scheduling problems); and
coordination via social laws and conventions, and the example of traffic rules.
Distributed dynamic programming for path planning
Like graph coloring, path planning constitutes another common abstract problemsolving framework. A path-planning problem consists of a weighted directed graph with a set of n nodes N, directed links L, a weight function w : L ↦ ℝ+, and two nodes s, t ∈ N. The goal is to find a directed path from s to t having minimal total weight. More generally, we consider a set of goal nodes T ⊂ N, and are interested in the shortest path from s to any of the goal nodes t ∈ T.
This abstract framework applies in many domains. Certainly it applies when there is some concrete network at hand (e.g., a transportation or telecommunication network). But it also applies in more roundabout ways.
8 - Communication
Agents communicate; this is one of the defining characteristics of a multiagent system. In traditional linguistic analysis, the communication is taken to have a certain form (syntax), to carry a certain meaning (semantics), and to be influenced by various circumstances of the communication (pragmatics). As we shall see, a closer look at communication adds to the complexity of the story. We can distinguish between purely informational theories of communication and motivational ones. In informational communication, agents simply inform each other of different facts. The theories of belief change, introduced in Chapter 14, look at ways in which beliefs change in the face of new information—depending on whether the beliefs are logical or probabilistic, consistent with prior beliefs or not. In this chapter we broaden the discussion and consider motivational theories of communication, involving agents with individual motivations and possible courses of actions.
We divide the discussion into three parts. The first concerns cheap talk and describes a situation in which self-motivated agents can engage in costless communication before taking action. As we see, in some situations this talk influences future behavior, and in some it does not. Cheap talk can be viewed as "doing by talking"; in contrast, signaling games can be viewed as "talking by doing." In signaling games an agent can take actions that, by virtue of the underlying incentives, communicate to the other agent something new.
4 - Computing Solution Concepts of Normal-Form Games
Print publication: 15 December 2008, pp 87-112
The discussion of strategies and solution concepts in Chapter 3 largely ignored issues of computation. We start by asking the most basic question: How hard is it to compute the Nash equilibria of a game? The answer turns out to be quite subtle, and to depend on the class of games being considered.
We have already seen how to compute the Nash equilibria of simple games. These calculations were deceptively easy, partly because there were only two players and partly because each player had only two actions. In this chapter we discuss several different classes of games, starting with the simple two-player, zero-sum normal-form game. Dropping only the zero-sum restriction yields a problem of different complexity—while it is generally believed that any algorithm that guarantees a solution must have an exponential worst case complexity, it is also believed that a proof to this effect may not emerge for some time. We also consider procedures for n-player games. In each case, we describe how to formulate the problem, the algorithm (or algorithms) commonly used to solve them, and the complexity of the problem. While we focus on the problem of finding a sample Nash equilibrium, we will briefly discuss the problem of finding all Nash equilibria and finding equilibria with specific properties. Along the way we also discuss the computation of other game-theoretic solution concepts: maxmin and minmax strategies, strategies that survive iterated removal of dominated strategies, and correlated equilibria.
Multiagent Systems
Algorithmic, Game-Theoretic, and Logical Foundations
Yoav Shoham, Kevin Leyton-Brown
Print publication: 15 December 2008
Buy the print book
Multiagent systems combine multiple autonomous entities, each having diverging interests or different information. This overview of the field offers a computer science perspective, but also draws on ideas from game theory, economics, operations research, logic, philosophy and linguistics. It will serve as a reference for researchers in each of these fields, and be used as a text for advanced undergraduate or graduate courses. The authors emphasize foundations to create a broad and rigorous treatment of their subject, with thorough presentations of distributed problem solving, game theory, multiagent communication and learning, social choice, mechanism design, auctions, cooperative game theory, and modal logics of knowledge and belief. For each topic, basic concepts are introduced, examples are given, proofs of key results are offered, and algorithmic considerations are examined. An appendix covers background material in probability theory, classical logic, Markov decision processes and mathematical programming.
Print publication: 15 December 2008, pp vii-xiv
A - Probability Theory
Probability theory provides a formal framework for the discussion of chance or uncertainty. This appendix reviews some key concepts of the theory and establishes notation. However, it glosses over some details (e.g., pertaining to measure theory). Therefore, the interested reader is encouraged to consult a textbook on the topic for a more comprehensive picture.
Probabilistic models
A probabilistic model is defined as a tuple (Ω, F, P), where:
Ω is the sample space, also called the event space;
F is a σ-algebra over Ω; that is, F ⊆ 2Ω and is closed under intersection and countable union; and
P : F ↦ [0, 1] is the probability density function (PDF).
Intuitively, the sample space is a set of things that can happen in the world according to our model. For example, in a model of a six-sided die, we might have Ω = {1, 2, 3, 4, 5, 6}. The σ-field F is a collection of measurable events. F is required because some outcomes in Ω may not be measurable; thus, we must define our probability density function P over F rather than over Ω. However, in many cases, such as the six-sided die example, all outcomes are measurable. In those cases we can equate F with 2Ω and view the probability space as the pair (Ω, P) and P as P : 2Ω ↦ [0, 1]. We assume this in the following.