Name
Abstract | ||
|---|---|---|
Proper scoring rules are crucial tools to elicit truthful information from experts. A scoring rule maps X, an expert-provided distribution over the set of all possible states of the world, and ω, a realized state of the world, to a real number representing the expert’s reward for his provided information. To compute this reward, a scoring rule queries the distribution X at various states. The number of these queries is thus a natural measure of the complexity of the scoring rule. We prove that any bounded and strictly proper scoring rule that is deterministic must make a number of queries to its input distribution that is a quarter of the number of states of the world. When the state space is very large, this makes the computation of such scoring rules impractical. We also show a new stochastic scoring rule that is bounded, strictly proper, and which makes only two queries to its input distribution. Thus, using randomness allows us to have significant savings when computing scoring rules. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2632228 | ACM Trans. Economics and Comput. |
Keywords | Field | DocType |
algorithms,congestion games,price of anarchy,selfish routing,theory,electronic commerce,economics | Scoring rule,Mathematical optimization,Computer science,Price of anarchy,Artificial intelligence,Real number,State space,Machine learning,Randomness,Bounded function,Computation | Journal |
Volume | Issue | Citations |
2 | 3 | 0 |
PageRank | References | Authors |
0.34 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pablo Daniel Azar | 1 | 36 | 4.34 |
| Silvio Micali | 2 | 11434 | 2581.31 |
| AzarPablo Daniel | 3 | 0 | 0.34 |