Informational Substitutes

We propose definitions of substitutes and complements for pieces of information ("signals") in the context of a decision or optimization problem, with game-theoretic and algorithmic applications. In a game-theoretic context, substitutes capture diminishing marginal value of information to a rational decision maker. There, we address the main open problem in a fundamental strategic-information-revelation setting, prediction markets. We show that substitutes characterize "best-possible" equilibria with immediate information aggregation, while complements characterize "worst-possible", delayed aggregation. Game-theoretic applications also include settings such as crowdsourcing contests and question-and-answer forums. In an algorithmic context, where substitutes capture diminishing marginal improvement of information to an optimization problem, substitutes imply efficient approximation algorithms for a very general class of (adaptive) information acquisition problems. In tandem with these broad applications, we examine the structure and design of informational substitutes and complements. They have equivalent, intuitive definitions from disparate perspectives: submodularity, geometry, and information theory. We also consider the design of scoring rules or optimization problems so as to encourage substitutability or complementarity, with positive and negative results. Taken as a whole, the results give some evidence that, in parallel with substitutable items, informational substitutes play a natural conceptual and formal role in game theory and algorithms.

Authors

• Yiling Chen 0001
• Bo Waggoner

Keywords

• Lattices
• Context
• Optimization
• Algorithm design and analysis
• Approximation algorithms
• Prediction algorithms
• Rain
• Valuable Information
• Optimization Problem
• Pieces Of Information
• Estimation Algorithm
• Decision Problem
• Information Aggregation
• Marginal Value
• Scoring Rules
• Structural Information
• Contributions Of This Paper
• General Condition
• Resource Constraints
• Conditional Independence
• Kullback-Leibler
• Partial Information
• Convex Function
• Independent Signals
• Partial Order
• Dew Point
• Information Units
• Pair Of Signals
• Basic Example
• value of information
• decision problems
• substitutes
• complements
• prediction markets
• information acquisition
• submodularity