Multi-weighted (sample)-prophet and secretary matching problems.

Abstract: A k-graph is a hypergraph whose edges have size k. Consider a k-graph G and a collection of m agents. Agent i has a weight function w_i over all edges. Our task is to assign at most one edge e to each agent i (receiving a profit of w_i(e)) in such a way that no edge is assigned twice, that the set of assigned edges form a matching while maximizing total profit.

We tackle online and stochastic variants of this problem and generalizations to other independence systems. In these versions, agents arrive one by one revealing their weight function and the decision maker must assign edges (or skip the agent) on the fly.

In the prophet version of the problem, agent i selects its weight function independently from a distribution D_i known to the algorithm. For this version, Correa et al. (2022) get a 1/(k+1)-approximation using posted price mechanisms. This is currently the best factor even if the agents arrive in random order (this is known as the prophet-secretary version).

We consider the case in which the algorithm does not have full knowledge of the distribution but it has access to a single sample from each D_i. For the random order case, we give a very simple polynomial time algorithm that achieves a factor of 1/(k+1) with a single sample. We also give an algorithm achieving a competitive ratio of k^{-k/(k-1)} for the secretary version (zero knowledge, random order). Our algorithms work for other  independence systems such as intersections of graphic matroids.  Finally we give close to optimal upper bounds, in particular we show that even if the agents’ distributions are IID and known, no algorithm can achieve a competitive ratio larger than log k/ k.

Posted on Jun 5, 2023 in ACGO, Seminars