Haifeng Xu

Stephanie Schoch, Haifeng Xu, Yangfeng Ji

Data valuation, or the valuation of individual datum contributions, has seen growing interest in machine learning due to its demonstrable efficacy for tasks such as noisy label detection. In particular, due to the desirable axiomatic properties, several Shapley value approximation methods have been proposed. In these methods, the value function is typically defined as the predictive accuracy over the entire development set. However, this limits the ability to differentiate between training instances that are helpful or harmful to their own classes. Intuitively, instances that harm their own classes may be noisy or mislabeled and should receive a lower valuation than helpful instances. In this work, we propose CS-Shapley, a Shapley value with a new value function that discriminates between training instances' in-class and out-of-class contributions. Our theoretical analysis shows the proposed value function is (essentially) the unique function that satisfies two desirable properties for evaluating data values in classification. Further, our experiments on two benchmark evaluation tasks (data removal and noisy label detection) and four classifiers demonstrate the effectiveness of CS-Shapley over existing methods. Lastly, we evaluate the "transferability" of data values estimated from one classifier to others, and our results suggest Shapley-based data valuation is transferable for application across different models.

Krishnamurthy Iyer, Alec Sun, Haifeng Xu et al.

Motivated by the recent popularity of machine learning training services, we introduce a contract design problem in which a provider sells a service that results in an outcome of uncertain quality for the buyer. The seller has a set of actions that lead to different distributions over outcomes. We focus on a setting in which the seller has the ability to commit to an action and the buyer is free to accept or reject the outcome after seeing its realized quality. We propose a two-stage payment scheme where the seller designs a menu of contracts, each of which specifies an action, an upfront price and a vector of outcome-dependent usage prices. Upon selecting a contract, the buyer pays the upfront price, and after observing the realized outcome, the buyer either accepts and pays the corresponding usage price, or rejects and is exempt from further payment. We show that this two-stage payment structure is necessary to maximize profit: only upfront prices or only usage prices is insufficient. We then study the computational complexity of computing a profit-maximizing menu in our model. While computing the exact maximum seller profit is NP-hard even for two buyer types, we derive a fully-polynomial time approximation scheme (FPTAS) for the maximum profit for a constant number of buyer types. Finally, we prove that in the single-parameter setting in which buyers' valuations are parametrized by a single real number that seller revenue can be maximized using a menu consisting of a single contract.

Nir Rosenfeld, Haifeng Xu

Decades of research in machine learning have given us powerful tools for making accurate predictions. This has made such tools appealing for use in social settings and on human inputs. Yet despite a lack of justification for why the generic approach of accuracy maximization can or should improve our collective well-being -- and mounting evidence of likely adverse outcomes -- it remains the widespread default. This position paper asserts that for machine learning to become socially beneficial, it must be embedded within a broader economic framework that explicitly aims to maximize social welfare. The field of welfare economics asks: how should we allocate limited resources among self-interested agents to maximize overall benefits? We contend that this perspective applies to many contemporary applications of machine learning in social contexts, and advocate for its adoption. Rather than disposing of prediction, we propose to leverage this forte of machine learning towards welfare maximization. We demonstrate this idea by portraying a conceptual framework that gradually transitions from accuracy maximization (with awareness to welfare) to welfare maximization (via accurate prediction). We detail applications and use-cases for which this framework can be effective, identify technical challenges and practical opportunities, and highlight future avenues worth pursuing.

Seyed A. Esmaeili, Kevin Lim, Kshipra Bhawalkar et al.

Generative AI (GenAI) will have significant impact on content creation platforms. In this paper, we study the dynamic competition between a GenAI and a human contributor. Unlike the human, the GenAI's content only improves when more contents are created by the human over time; however, GenAI has the advantage of generating content at a lower cost. We study the algorithmic problem in this dynamic competition model about how the human contributor can maximize her utility when competing against the GenAI for content generation over a set of topics. In time-sensitive content domains (e.g., news or pop music creation) where contents' value diminishes over time, we show that there is no polynomial time algorithm for finding the human's optimal (dynamic) strategy, unless the randomized exponential time hypothesis is false. Fortunately, we are able to design a polynomial time algorithm that naturally cycles between myopically optimizing over a short time window and pausing and provably guarantees an approximation ratio of $\frac{1}{2}$. We then turn to time-insensitive content domains where contents do not lose their value (e.g., contents on history facts). Interestingly, we show that this setting permits a polynomial time algorithm that maximizes the human's utility in the long run. Finally, we conduct simulations that demonstrate the advantage of our algorithms in comparison to a collection of baselines.