טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentWahrmann Lyron
SubjectPrediction Games
DepartmentDepartment of Applied Mathematics
Supervisor Mr. Amir Ronen


Abstract

The usage of input provided by many agents often enables accurate forecasting of future events. A major difficulty in performing such predictions is that the agents are required to invest a costly effort for providing their input.

We introduce a new class of mechanism design problems called Prediction Games. During the game, agents' inputs are gathered to produce a future event prediction. Paying agents is allowed in order to encourage them to compute their inputs.

 

Preliminaries: There are n agents; each has a private Boolean input xi and a cost of accessing it c. Given are a Binary Prediction Function f(x1,...,xn) and an IID distribution on the inputs (q=Pr[xi=1]). The (conditional) influence Ii is defined as the probability that agent i's input determines f(.).

The goal is to design a mechanism M which in truthful equilibrium predicts f(.) and pays in expectation as little as possible i.e. a truthful implementation.

Exact Predictions:

Definition: Let M approach agent i with message m.

The canonical payment scheme is defined by:

vi(m) =             viT=c/[(1 - qM)Ii(m)]     f(.) is correct

                        viF=0                            otherwise

Definition: A canonical mechanism is a truthful implementation with the following properties:

  • Approaches the agents serially.
  • Do not reveal them any information.
  • Stop when the prediction is determined.
  • Pay according to the canonical payment scheme.

Theorem: For every prediction problem there exists a canonical implementation with an expected payment which is optimal among all other implementations.

Theorem:  If f(.) is anonymous, a canonical mechanism which approaches the agents according to a random order is an optimal implementation of it.

Theorem: Let f(.) be a weighted threshold function. fw,q(x) =1 iff ∑i=1n wixiq.

A canonical mechanism which approaches the agents by a decreasing weight fixed order dominates every other fixed order mechanism.

Theorem: Every f(.) can be implemented with an expected payment of

B(M) = O(c/[qM (1-qM)n])

Theorem: Every anonymous f(.) can be implemented with an expected payment of

B(M)=O((cn2)/[(1-qM)2min(p,1-p)log(n)]) where p=Pr[f(x) = 1].

 

Approximate Predictions:

Exact predictions may require high payments. Allowing a small probability of error might result in a much cheaper implementation.

Definition: An e-approximation of a prediction problem is a truthful implementation such that f(.) is correct with probability ≥ (1-e).

Theorem: Let 0 < e < ½. Every f(.) can be (1-e)-approximated with an expected payment: B(M) £ O(n2c/[e(1 - e)]).