Truthful Matching with Online Items and Offline Agents

Michal Feldman, Federico Fusco, Simon Mauras, Rebecca Reiffenhäuser

Abstract

We study truthful mechanisms for welfare maximization in online bipartite matching. In our (multi-parameter) setting, every buyer is associated with a (possibly private) desired set of items, and has a private value for being assigned an item in her desired set. Unlike most online matching settings, where agents arrive online, in our setting the items arrive online in an adversarial order while the buyers are present for the entire duration of the process. This poses a significant challenge to the design of truthful mechanisms, due to the ability of buyers to strategize over future rounds. We provide an almost full picture of the competitive ratios in different scenarios, including myopic vs. non-myopic agents, tardy vs. prompt payments, and private vs. public desired sets. Among other results, we identify the frontier up to which the celebrated $e/(e-1)$ competitive ratio for the vertex-weighted online matching of Karp, Vazirani and Vazirani extends to truthful agents and online items.

Introduction

Classic online bipartite matching typically involves agents arriving sequentially to be matched with static resources. This paper explores the inverse: offline agents and online items. In this scenario, items arrive one-by-one in an adversarial order, while buyers remain present throughout. This setup is highly relevant to modern digital markets, such as ad auctions where advertisers are persistent but ad slots appear dynamically.

The core challenge lies in the strategic nature of the buyers. Since they are present for the entire process, they can be strategic. A buyer might lie about their value or interest in a current item to "save" themselves for a potentially better item arriving later. The goal is to design truthful mechanisms—where the best strategy for every buyer is to report their true value—while still maximizing social welfare (the sum of the values of all matched pairs).

Methodology and Dimensions of Analysis

The research categorizes the problem along three critical dimensions:

  1. Agent Behavior: Myopic agents consider only the current round, whereas non-myopic agents strategize over the entire sequence.
  2. Payment Timing: Prompt mechanisms require immediate payment upon allocation, while tardy mechanisms delay payment until the end.
  3. Information Privacy: In some cases, only the buyer's value is private; in others, the set of items they are interested in (the graph edges) is also private.

The authors utilize Myerson’s Lemma, a cornerstone of auction theory, to determine the exact payments needed to keep agents honest. They adapt classic matching algorithms like Greedy and Ranking (specifically the vertex-weighted version called Perturbed-Greedy). For the most difficult case (non-myopic agents with private interests), they introduce a new Explore-Exploit Mechanism that randomly decides whether to use an item to "probe" buyer values or to actually "sell" it to maximize welfare.

Bipartite matching construction used to establish lower bounds on competitive ratios.

Key Insights: The Truthfulness Tax

A primary finding is the "Truthfulness Tax." For myopic agents, truthfulness is essentially "free"—we can achieve the same $e/(e-1) \approx 1.58$ competitive ratio as non-strategic settings. However, for strategic (non-myopic) agents, requiring "prompt" payments forces prices to be non-decreasing over time to prevent manipulation. This restriction is what kills efficiency.

The authors identify a Critical Item Property: any deterministic, prompt, truthful mechanism for non-myopic agents effectively treats each buyer as if they only want one specific "critical" item. If that item doesn't show up or someone else gets it, the buyer gets nothing. This insight is used to prove a harsh lower bound on performance. While deterministic prompt mechanisms are stuck with a terrible linear competitive ratio ($\nu$), randomized mechanisms can use an "explore-exploit" strategy to achieve a logarithmic ratio ($O(\log \nu)$).

Key Results

The study provides a comprehensive map of competitive ratios across various scenarios, where $\nu = \min(\text{items, agents})$. The jump from a constant ratio (like 1.58) to a logarithmic or linear one highlights exactly how much harder the problem becomes when agents are both strategic and forward-looking.

Summary of competitive ratios for different agent behaviors and information settings.
Scenario Deterministic Randomized
Myopic Agents 2 $e/(e-1)$
Non-myopic (Public Edges, Tardy) 2 $e/(e-1)$
Non-myopic (Public Edges, Prompt) $\ge \nu$ $\Omega(\frac{\log \nu}{\log \log \nu})$
Non-myopic (Private Edges, Prompt) $\le \nu$ $O(\log \nu)$

Conclusion and Future Work

This work delineates the boundaries of efficiency in truthful online matching. While "tardy" payments allow for high efficiency, the practical requirement of "prompt" payments in strategic environments introduces substantial welfare losses.

Several avenues for future work remain:

  • Adversarial Order: The results assume the worst possible arrival order. A "random arrival order" model might yield more optimistic results.
  • Unit Demand: The study is limited to buyers who only want a single item. Real-world scenarios often involve buyers wanting bundles of items.
  • Ex-ante Truthfulness: The authors briefly touch on "ex-ante" truthfulness (being truthful on average), leaving the exact bounds for this looser requirement as an open question.

Summary updated

Abstract

We study truthful mechanisms for welfare maximization in online bipartite matching. In our (multi-parameter) setting, every buyer is associated with a (possibly private) desired set of items, and has a private value for being assigned an item in her desired set. Unlike most online matching settings, where agents arrive online, in our setting the items arrive online in an adversarial order while the buyers are present for the entire duration of the process. This poses a significant challenge to the design of truthful mechanisms, due to the ability of buyers to strategize over future rounds. We provide an almost full picture of the competitive ratios in different scenarios, including myopic vs. non-myopic agents, tardy vs. prompt payments, and private vs. public desired sets. Among other results, we identify the frontier up to which the celebrated e/(e-1) competitive ratio for the vertex-weighted online matching of Karp, Vazirani and Vazirani extends to truthful agents and online items.
BibTeX
@article{feldman2024truthful,
  author = {Michal Feldman and Federico Fusco and Simon Mauras and Rebecca Reiffenhäuser},
  title = {{Truthful Matching with Online Items and Offline Agents}},
  journal = {Algorithmica},
  year = {2024},
  doi = {10.1007/s00453-023-01202-3},
}
Figure