Fairness Maximization among Offline Agents in Online-Matching Markets

2021-09-18 · Will Ma, Pan Xu, Yifan Xu

Matching markets involve heterogeneous agents (typically from two parties) who are paired for mutual benefit. During the last decade, matching markets have emerged and grown rapidly through the medium of the Internet. They have evolved into a new format, called Online Matching Markets (OMMs), with examples ranging from crowdsourcing to online recommendations to ridesharing. There are two features distinguishing OMMs from traditional matching markets. One is the dynamic arrival of one side of the market: we refer to these as online agents while the rest are offline agents. Examples of online and offline agents include keywords (online) and sponsors (offline) in Google Advertising; workers (online) and tasks (offline) in Amazon Mechanical Turk (AMT); riders (online) and drivers (offline when restricted to a short time window) in ridesharing. The second distinguishing feature of OMMs is the real-time decision-making element. However, studies have shown that the algorithms making decisions in these OMMs leave disparities in the match rates of offline agents. For example, tasks in neighborhoods of low socioeconomic status rarely get matched to gig workers, and drivers of certain races/genders get discriminated against in matchmaking. In this paper, we propose online matching algorithms which optimize for either individual or group-level fairness among offline agents in OMMs. We present two linear-programming (LP) based sampling algorithms, which achieve online competitive ratios at least 0.725 for individual fairness maximization (IFM) and 0.719 for group fairness maximization (GFM), respectively. We conduct extensive numerical experiments and results show that our boosted version of sampling algorithms are not only conceptually easy to implement but also highly effective in practical instances of fairness-maximization-related models.

📄 PDF Abstract BibTeX arXiv:2109.08934

Code (0)

등록된 구현이 없습니다.

Tasks

Decision Making Fairness

Fair Online Resource Allocation

2026-06-17 · Christopher En, Yuri Faenza, Andrea Lodi, Gonzalo Muñoz arxiv

We study the problem of fair online resource allocation, motivated by applications such as refugee resettlement and airline scheduling, where agents arrive sequentially and must be assigned to facilities with limited cap…

FairDICE: Fairness-Driven Offline Multi-Objective Reinforcement Learning

2025-06-09 · Woosung Kim, Jinho Lee, Jongmin Lee, Byung-Jun Lee

Multi-objective reinforcement learning (MORL) aims to optimize policies in the presence of conflicting objectives, where linear scalarization is commonly used to reduce vector-valued returns into scalar signals. While ef…

Fairness Multi-Objective Reinforcement Learning reinforcement-learning Reinforcement Learning

Reinforcement Learning with Ex-Post Max-Min Fairness

2021-09-29 · Wang Chi Cheung, Zi Yi Ewe

We consider reinforcement learning with vectorial rewards, where the agent receives a vector of $K\geq 2$ different types of rewards at each time step. The agent aims to maximize the minimum total reward among the $K$ re…

Fairness reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Online Fair Revenue Maximizing Cake Division with Non-Contiguous Pieces in Adversarial Bandits

2021-11-29 · Mohammad Ghodsi, Amirmahdi Mirfakhar

The classic cake-cutting problem provides a model for addressing the fair and efficient allocation of a divisible, heterogeneous resource among agents with distinct preferences. Focusing on a standard formulation of cake…

Fairness Multi-Armed Bandits

The Leximin Approach for a Sequence of Collective Decisions

2023-05-29 · Ido Kahana, Noam Hazon

In many situations, several agents need to make a sequence of decisions. For example, a group of workers that needs to decide where their weekly meeting should take place. In such situations, a decision-making mechanism …