EconCS: Origins
Bo Waggoner
Harvard Summer Student Colloquium
2014.06.26
prediction markets
networks
multi-agent systems
data mining
mechanism design
optimization
algorithmic game theory
utility models
human computation
information aggregation
matching
coalitional games
revenue maximization
approximation in mechanism design
voting equilibria
bandit algorithms
incentives and markets
online task assignment
information elicitation
crowdsourcing
online experiments
social computing
statistical
machine learning
badge design
budget-feasible mechanisms
What is EconCS?
What is EconCS?
What is Computer Science?
What is EconCS?
What is Computer Science?
What is Science?
Bo’s Philosophy of (Computer) Science
maths
engineering
Fig. 1: Science
natural
sciences
Bo’s Philosophy of (Computer) Science
“proving facts”
“building stuff”
Fig. 1: Science
“studying
phenomena”
Bo’s Philosophy of (Computer) Science
Science + Algorithms = Computer Science
Bo’s Philosophy of (Computer) Science
Science + Algorithms = Computer Science
maths + algorithms
engineering
+ algorithms
Fig. 2: Computer Science
natural
sciences
+ algorithms
Bo’s Philosophy of (Computer) Science
Science + Algorithms = Computer Science
“proving facts about algorithms”
“using algorithms to prove facts”
“building algorithms”
“using algorithms to build stuff”
Fig. 2: Computer Science
“studying algorithmic phenomena”
“using algorithms to study phenomena”
Bo’s Philosophy of (Computer) Science
Scientific Study of Algorithms
“proving facts about algorithms”
“building algorithms”
“studying algorithmic phenomena”
Fig. 3: The dual relationship of science and CS
Algorithmic Study of Science
“using algorithms to prove facts”
“using algorithms to build stuff”
“using algorithms
to study phenomena”
What is EconCS?
(according to Bo)
What is EconCS?
(according to Bo)
Mostly,
the algorithmic study of systems of goal-directed agents
the study of algorithms arising in such systems.
and
“goal-directed agents”
“goal-directed agents”
A
B
C
“goal-directed agents”
A
B
C
“goal-directed agents”
“microeconomics”
A
B
C
Themes in EconCS
Themes in EconCS
1. how to play at games
Agenda:
3. how to get data
2. how google makes $$
Recall:
1. how to play at games
A
B
C
goal-directed → utility for outcomes
Action
“Utility”
A
B
C
6
10
7
goal-directed → utility for outcomes
Action
“Utility”
A
B
C
6
10
7
Game Theory: interacting goal-directed agents
A
B
C
6, 8
10, 7
7, 4
A
B
C
2, 8
7, 5
8, 7
7, 4
2, 9
4, 7
Game Theory: interacting goal-directed agents
A
B
C
6, 8
10, 7
7, 4
A
B
C
2, 8
7, 5
8, 7
7, 4
2, 9
4, 7
How do/should agents act?
Key idea: equilibrium.
Each player’s (randomized) strategy
is an optimal response
to all other players’ (randomized) strategies.
Algorithmic questions on equilibria
Another algorithmic question
Themes in EconCS
1. how to play at games
Agenda:
3. how to get data
2. how google makes $$
2. how google makes $$
2. how google makes $$
$10
$9
$8
$10
$9
$8
$10
$9
$8
2. how google makes $$
$9
$8
$10
2. how google makes $$
utility: 0
utility: 0
utility: 1
$9
Mechanism Design: building games
A
B
C
6, 8
10, 7
7, 4
A
B
C
2, 8
7, 5
8, 7
7, 4
2, 9
4, 7
Mechanism Design: building games
A
B
C
6, 8
10, 7
7, 4
A
B
C
2, 8
7, 5
8, 7
7, 4
2, 9
4, 7
How to construct algorithms involving strategic agents?
Key idea: Build games with “good” equilibria.
Players locally optimize → good global outcome.
Algorithmic questions in MD: Auctions!
How to optimize and analyze auctions:
Mechanism design without money
Themes in EconCS
1. how to play at games
Agenda:
3. how to get data
2. how google makes $$
3. how to get data
OTHER
Who will win?
3. how to get data
OTHER
prediction
prediction
prediction
3. how to get data
OTHER
Prediction market:
Hot at Harvard: “crowdsourcing”
cf “human computation”, “social computing”, “information elicitation”, …
“Buying Data Access for Learning”
“We buy data”
“Buying Data Access for Learning”
“Buying Data Access for Learning”
$6
1) agent arrives, i.i.d.
“Buying Data Access for Learning”
$6
1) agent arrives, i.i.d.
X,Y LABEL PRICE
3,4 $8
3,4 $2
1,1 $4
1,1 $6
...
2) we offer menu of prices
“Buying Data Access for Learning”
X,Y LABEL PRICE
3,4 $8
3,4 $2
1,1 $4
1,1 $6
...
$6
1) agent arrives, i.i.d.
2) we offer menu of prices
3) agent decides whether
to accept offer for her data
“Buying Data Access for Learning”
$6
1) agent arrives, i.i.d.
2) we offer menu of prices
3) agent decides whether
to accept offer for her data
$8
3,4:
4) If so, we get the data and pay
the price we posted for it
“Buying Data Access for Learning”
$6
1) agent arrives, i.i.d.
2) we offer menu of prices
3) agent decides whether
to accept offer for her data
$8
3,4:
4) If so, we get the data and pay
the price we posted for it
How to price data?
Key idea: Use machine learning to assess value of potential data points.
Objective: Learn a good hypothesis with a small budget.
Recap
the algorithmic study of systems of goal-directed agents
the study of algorithms arising in such systems.
the algorithmic study of systems of goal-directed agents
the study of algorithms arising in such systems.
→ game theory, equilibrium
→ mechanism design, auctions, MD without money
→ prediction markets, crowdsourcing, …
End
Open questions: