Two-Sided Capacitated Submodular Maximization in Gig Platforms

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this paper, we propose three generic models of capacitated coverage and, more generally, submodular maximization to study task-worker assignment problems that arise in a wide range of gig economy platforms. Our models incorporate the following features: (1) Each task and worker can have an arbitrary matching capacity, which captures the limited number of copies or finite budget for the task and the working capacity of the worker; (2) Each task is associated with a coverage or, more generally, a monotone submodular utility function. Our objective is to design an allocation policy that maximizes the sum of all tasks’ utilities, subject to capacity constraints on tasks and workers. We consider two settings: offline, where all tasks and workers are static, and online, where tasks are static while workers arrive dynamically. We present three LP-based rounding algorithms that achieve optimal approximation ratios of 1 - 1 / e∼ 0.632 for offline coverage maximization, competitive ratios of (19 - 67 / e3) / 27 ∼ 0.580 and 0.436 for online coverage and online monotone submodular maximization, respectively.

Original languageEnglish (US)
Title of host publicationWeb and Internet Economics - 19th International Conference, WINE 2023, Proceedings
EditorsJugal Garg, Max Klimm, Yuqing Kong
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages18
ISBN (Print)9783031489730
StatePublished - 2024
Event19th InternationalConference on Web and Internet Economics, WINE 2023 - Shanghai, China
Duration: Dec 4 2023Dec 8 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14413 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference19th InternationalConference on Web and Internet Economics, WINE 2023

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Two-Sided Capacitated Submodular Maximization in Gig Platforms'. Together they form a unique fingerprint.

Cite this