Introduces IC-Envy metric for auction incentive compatibility that satisfies IC-Envy ≥ IC-Regret in position auctions and ad types, bounds social welfare loss from misreports, and improves ML prediction of regret over price/value features.
Note on VCG vs. Price Raising for Matching Markets
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
In \cite{EK10} the use of VCG in matching markets is motivated by saying that in order to compute market clearing prices in a matching market, the auctioneer needs to know the true valuations of the bidders. Hence VCG and corresponding personalized prices are proposed as an incentive compatible mechanism. The same line of argument pops up in several lecture sheets and other documents related to courses based on Easley and Kleinberg's book, seeming to suggest that computing market clearing prices and corresponding assignments were \emph{not} incentive compatible. Main purpose of our note is to observe that, in contrast, assignments based on buyer optimal market clearing prices are indeed incentive compatible.
fields
cs.GT 2years
2019 2verdicts
UNVERDICTED 2representative citing papers
Faster O(n²(k + log n)) algorithm for ad-types assignment without gap rules, inapproximability within k^{1-ε} with gap rules, and O(k n^{2k+1}) DP for exact solution with discounts.
citing papers explorer
-
Envy, Regret, and Social Welfare Loss
Introduces IC-Envy metric for auction incentive compatibility that satisfies IC-Envy ≥ IC-Regret in position auctions and ad types, bounds social welfare loss from misreports, and improves ML prediction of regret over price/value features.
-
The Ad Types Problem
Faster O(n²(k + log n)) algorithm for ad-types assignment without gap rules, inapproximability within k^{1-ε} with gap rules, and O(k n^{2k+1}) DP for exact solution with discounts.