Optimal Stopping with Interdependent Values

Simon Mauras, Divyarthi Mohan, Rebecca Reiffenhäuser

Introduction

In algorithmic game theory, online selection problems like the Prophet Inequality and the Secretary Problem serve as fundamental models for decision-making under uncertainty. Traditionally, these models assume that an agent's value for an item is independent of others. However, real-world scenarios—such as real estate auctions or hiring processes—often involve Interdependent Values (IDV). In these cases, an agent's true value depends not only on their private information (signal) but also on the signals of others.

This paper, presented by Simon Mauras, Divyarthi Mohan, and Rebecca Reiffenhäuser, investigates how to design approximation algorithms and truthful mechanisms for online selection in the IDV model.

The Interdependent Value Model

In the IDV framework, each agent $i$ has a private signal $s_i$. The value of the item to agent $i$ is a function $v_i(s_1, \dots, s_n)$ of all agents' signals. This introduces two primary difficulties for online algorithms:

  1. Information Gap: At the time agent $i$ arrives, the algorithm only knows signals $s_1, \dots, s_i$. Future signals $s_{i+1}, \dots, s_n$ are unknown, yet they influence $v_i$.
  2. Irrevocability: Decisions must be made immediately. A signal arriving later might reveal that a previously rejected agent was actually the best choice, or that an accepted agent is less valuable than initially thought.

To make the problem tractable, the authors assume valuation functions are subadditive over signals. This means the combined value of two sets of information is at most the sum of their individual values, preventing exponential value explosions.

Algorithmic Approaches and Agent Types

The paper distinguishes between two types of agents:

  • Myopic Agents: Their value depends only on signals that have already arrived ($s_1, \dots, s_i$).
  • Farsighted Agents: Their value depends on all signals, including those of agents who haven't arrived yet.

For the Prophet Inequality setting (where signal distributions are known), the authors show that farsightedness is a "Prophet-Killer." If an agent's value depends heavily on future signals, no constant-factor approximation is possible ($\\Omega(n)$ impossibility). However, for myopic agents, they achieve a 4-approximation using a modified threshold policy that compares the current agent against potential future signals.

In the Secretary Problem (where agents arrive in random order), the model is more robust. The random arrival order allows for a constant-factor approximation ($2e$) even for farsighted agents. The algorithm uses a sampling phase to estimate the optimal value before making selections.

Truthful Mechanisms

Beyond pure algorithms, the authors design truthful mechanisms to ensure agents report their signals honestly. By incorporating randomization—such as flipping a coin to decide whether to accept an agent who meets the threshold—they provide mechanisms with constant-factor guarantees (e.g., an 8-approximation for myopic Prophets and a $4e$-approximation for Secretaries).

Summary of Results

The following table summarizes the approximation ratios achieved across different settings and agent types, highlighting the distinction between algorithmic bounds and truthful mechanism constraints.

Summary of approximation ratios for Prophet and Secretary problems under different agent behaviors.

Conclusion and Future Work

This work establishes subadditivity as a natural boundary for constant-factor approximations in interdependent value settings. While the paper provides a comprehensive map of the problem space, several avenues for future research remain. These include tightening the approximation constants to match classic independent-value results (2 and $e$), exploring settings where valuation functions themselves are private, and extending the model to combinatorial constraints like matroid selection.

Summary updated

BibTeX
@inproceedings{mauras2024optimal,
  author = {Simon Mauras and Divyarthi Mohan and Rebecca Reiffenhäuser},
  title = {{Optimal Stopping with Interdependent Values}},
  booktitle = {EC},
  year = {2024},
  doi = {10.1145/3670865.3673628},
}
Figure