Se les invita para este Miércoles 07 de Junio del 2023 a contar de las 15:00 hrs, al AGCO Seminar, el cual se realizará en la Sala de Seminarios CMM, John Von Neumann, séptimo piso, Torre Norte, Beauchef 851.
Speaker: José Soto, DIM, U Chile.
Title: 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.
This is joint work with Victor Verdugo, Javier Marinkovic and Santiago Rebolledo.