procaccia07

Incentive Compatible Regression Learning: 

Incentive Compatible Regression Learning Ofer Dekel, Felix A. Fischer and Ariel D. Procaccia

Lecture Outline: 

Lecture Outline Until now: applications of learning to game theory. Now: merge. The model: Motivation The learning game Three levels of generality: Distributions which are degenerate at one point Uniform distributions The general setting Model Degenerate Uniform General

Motivation: 

Motivation Internet search company: improve performance by learning ranking function from examples. Ranking function assigns real value to every (query,answer). Employ experts to evaluate examples. Different experts may have diff. interests and diff. ideas of good output. Conflict  Manipulation  Bias in training set. Model Degenerate Uniform General

Jaguar vs. Panthera Onca: 

Jaguar vs. Panthera Onca (“Jaguar”, jaguar.com) Model Degenerate Uniform General

Regression Learning: 

Regression Learning Input space X=Rk ((query,answer) pairs). Function class F:XR (ranking functions). Target function o:XR. Distribution  over X. Loss function l (a,b). Abs. loss: l (a,b)=|a-b|. Squared loss: l (a,b)=(a-b)2. Learning process: Given: Training set S={(xi,o(xi))}, i=1,...,m, xi sampled from . R(h)=Ex[l (h(x),o(x))]. Find: hF to minimize R(h). Model Degenerate Uniform General

Our Setting: 

Our Setting Input space X=Rk ((query,answer) pairs). Function class F (ranking functions). Set of players N={1,...,n} (experts). Target functions oi:XR. Distributions i over X. Training set? Model Degenerate Uniform General

The Learning Game: 

The Learning Game i: controls xij, j=1,...,m, sampled w.r.t. i (common knowledge). Private info of i: oi(xij)=yij, j=1,...,m. Strategies of i: y’ij, j=1,...,m. h is obtained by learning S={(xij,y’ij)} Cost of i: Ri(h)=Exi [l (h(x),oi(x))]. Goal: Social Welfare (please avg. player). Model Degenerate Uniform General

Example: The learning game with ERM: 

Example: The learning game with ERM Parameters: X=R, F=Constant Functions, l (a,b)=|a-b|, N={1,2}, o1(x)=1, o2(x)=2, 1=2=uniform dist on [0,1000]. Learning algorithm: Empirical Risk Minimization (ERM) Minimize R’(h,S)=1/|S|  (x,y)Sl (h(x),y). 1 2 Model Degenerate Uniform General

Degenerate Distributions: ERM with abs. loss: 

Degenerate Distributions: ERM with abs. loss The Game: Players: N={1,...n} i: degenerate at xi. i: controls xi. Private info of i: oi(xi)=yi. Strategies of i: y’i. Cost of i: Ri(h)= l (h(xi),yi). Theorem: If l = absolute loss and F is convex. Then ERM is group incentive compatible. Model Degenerate Uniform General

ERM with superlinear loss : 

ERM with superlinear loss Theorem: l is “superlinear”, F is convex, |F|2, F is not “full” on x1,...,xn. Then y1,...,yn such that there is incentive to lie. Example: X=R, F=Constant Functions, l (a,b)=(a-b)2, N={1,2}. Model Degenerate Uniform General

Uniform dist. over samples: 

Uniform dist. over samples The Game: Players: N={1,...n} i: Discrete uniform on {xi1,...,xim} i: controls xij, j=1,...,m Private info of i: oi(xij)=yij. Strategies of i: y’ij, j=1,...,m. Cost of i: Ri(h)= R’i(h,S)= 1/mjl (h(xij),yij). Model Degenerate Uniform General

ERM with abs. loss is not IC: 

ERM with abs. loss is not IC Model Degenerate Uniform General 1 0

VCG to the Rescue: 

VCG to the Rescue Use ERM. Each player pays jiR’j(h,S). Each player’s total cost is R’i(h,S)+jiRj’(h,S) = jR’j(h,S). Truthful for any loss function. VCG has many faults: Not group incentive compatible. Payments problematic in practice. Would like (group) IC mechanisms w/o payments. Model Degenerate Uniform General

Mechanisms w/o Payments : 

Mechanisms w/o Payments Absolute loss. -approximation mechanism: gives an -approximation of the social welfare. Theorem (upper bound): There exists a group IC 3-approx mechanism for constant functions over Rk and homogeneous linear functions over R. Theorem (lower bound): There is no IC (3-)-approx mechanism for constant/hom. lin. functions over Rk. Conjecture: There is no IC mechanism with bounded approx. ratio for hom. lin. functions over Rk, k2. Model Degenerate Uniform General

Proof of Lower Bound: 

Proof of Lower Bound Model Degenerate Uniform General 3 2 1 0 2- 3- 1-

Proof of Lower Bound: 

Proof of Lower Bound k k-1 k k-1 Model Degenerate Uniform General 3 2 1 0 2- 3- 1-

Generalization: 

Generalization Theorem: If f, (1) i, |R’i(f,S)-Ri(f)|  /2 (2) |R’(f,S)-1/ni Ri(f)|  /2 Then: (Group) IC in uniform  -(group) IC in general. -approx in uniform  -approx up to additive  in general. If F has bounded complexity, m=(log(1/)/), then cond. (1) holds with prob. 1-. Cond. (2) is obtained if (1) occurs for all i. Taking /n adds factor of logn. Model Degenerate Uniform General

Discussion: 

Discussion Given m large enough, with prob. 1- VCG is -truthful. This holds for any loss function. Given m large enough, abs loss, mechanism w/o payments which is -group IC and 3-approx for constant functions and hom. lin. functions. Most important direction for future work: extending to other models of learning, such as classification. Model Degenerate Uniform General