Algorithmic Pricing for the Partial Assignment

摘要: A seller has an items set \(M=\left\{ 1,2,\dots ,m\right\} \) and the amount of each item is 1. In buyer \(N=\{1, 2, ..., n\}\), i interested bundle \(B_i\subseteq M\), a valuation \(v_i\) on \(B_i\), budgets \(e_{ij}\) j. The knows whole information buyers decides price for so as to maximize social welfare. Buyers come in arbitrary order. When comes, can be only sold integrally. previous works, if buyer’s does not exist, he will buy nothing cannot satisfied. this paper, we consider partially If some \(B_i\) are out arrival i, might satisfied by buying subset without violating budget condition. We first show that new model, achieving maximum welfare NP-hard. Moreover, optimal assignment oracle used achieve then analyze two pricing schemes approximate trade-off scheme, O(k)-approximation algorithm achieved considering bundle, where k maximal cardinality assigned among all buyers. item-set when \(d=\dfrac{1}{2}|x_{iB}^*|\), approximated within factor moreover, compared with traditional (non-partial assignment) setting, increased at least \(\sum _{S_{i}}\dfrac{d}{\left| x_{iB}^*\right| }\sum _{j\in S_{i}}e_{ij}^{'}\), \(S_i\) containing j, \(x_{iB}^*\) represents ith subset’s complete set, i.e, one \(B_{i}\)’s subset, \(x_{iB}^*=B_{i}\), \(x_{iB}\) intersection \(B_{i}\) S, d minimum \(\left| x_{iB}\right| -\left| \), \(e_{ij}^{'}\) item’s budget.