Myersonian Regression

We study a variant of linear regression with a dis-continuous loss function that we term Myersonianregression. In this variant, we wish to find a linearfunctionf:Rd→Rthat well approximates a setof points(xi,vi)∈Rd×[0,1]in the followingsense: we receive a loss ofviwhenf(xi)> viand a loss ofvi−f(xi)whenf(xi)≤vi. Thisarises naturally in the economic application ofdesigning a pricing policy for differentiated items(where the loss is the gap between the perfor-mance of our policy and the optimal Myersonprices).We show that Myersonian regression is NP-hardto solve exactly and furthermore that no fullypolynomial-time approximation scheme exists forMyersonian regression conditioned on the Expo-nential Time Hypothesis being true. In contrast tothis, we demonstrate a polynomial-time approx-imation scheme for Myersonian regression thatobtains anmadditive approximation to the op-timal possible revenue and can be computed intimeO(exp(poly(1/))poly(m,n)). We showthat this algorithm is stable and generalizes wellover distributions of samples

• Algorithms and Theory

• Economics and Electronic Commerce