I am interested in mechanism design. In the paper On Profit-Maximizing Envy-free Pricing, SODA, 2005, the authors provided a truthful competitive posted-price mechanism with $4\log h$ guarantee of revenue in the unit demand setting (see Theorem 4.1 in section 4). If I understood correctly, this mechanism does NOT have guarantee on social welfare.

Is that possible to derive a truthful (a.k.a. incentive-compatible) posted-price mechanism with (approximate) efficiency (a.k.a. social welfare guarantee) for some envy-free pricing problem? I am aware of some frameworks based on VCG or non-VCG (e.g. critical-payment by Nisan). However, I do not find any of them a good fit for this problem.

P.S. "posted-price" means that the price of any bundle $S$ is the sum of prices of items in $S$, i.e. $p(S)=\sum_{i\in S} p_i$ where $p_i$ is the price of one copy of item $i$. The utility of buyer $j$ when he receives bundle $S$ can be formulated as: $u_j(S)=v_j(S)-p(S)$ where $v_j(S)$ is the valuation of $j$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.