Abstract:
Fairness is an increasingly research subject within various computer science sub-disciplines such as machine learning and market design. In this presentation we will discuss two possible fairness challenges: the data-set valuation problem and the price of fairness in bipartite matching markets.
The data-set valuation problem addresses measuring the contributions of agents when collaborating on machine learning tasks. By employing tools from both machine learning and game theory, we model this as a cooperative game and present an approach to approximate the Shapley value of players. The method demonstrates superior performance compared to Monte-Carlo state-of-the-art techniques, supported by theoretical guarantees.
The price of fairness (PoF) quantifies the optimality loss when applying fairness constraints to a problem. Examining the egalitarian PoF in bipartite matching markets, where agents belong to distinct groups, we exploit matroid and geometric tools to characterize fair matchings, optimal matchings, and their intersection. An adversarial analysis reveals that a PoF of 1 is always achievable for two groups, while for a greater number of groups, the PoF can be arbitrarily large.