One of the classic problems in online decision-making is the secretary problem, where the goal is to hire the best secretary out of n rankable applicants or, in a natural extension, to maximize the probability of selecting the largest number from a sequence arriving in random order. Many works have considered generalizations of this problem where one can accept multiple values subject to a combinatorial constraint. The seminal work of Babaioff, Immorlica, Kempe, and Kleinberg (SODA'07, JACM'18) proposed the matroid secretary conjecture, suggesting that there exists an O(1)-competitive algorithm for the matroid constraint, and many works since have attempted to obtain algorithms for both general matroids and specific classes of matroids. The ultimate goal of these results is to obtain an e-competitive algorithm, and the strong matroid secretary conjecture states that this is possible for general matroids. One of the most important classes of matroids is the graphic matroid, where a set of edges in a graph is deemed independent if it contains no cycle. Given the rich combinatorial structure of graphs, obtaining algorithms for these matroids is often seen as a good first step towards solving the problem for general matroids. For matroid secretary, Babaioff et al. (SODA'07, JACM'18) first studied graphic matroid case and obtained a 16-competitive algorithm. Subsequent works have improved the competitive ratio, most recently to 4 by Soto, Turkieltaub, and Verdugo (SODA'18). In this paper, we break the 4-competitive barrier for the problem, obtaining a new algorithm with a competitive ratio of 3.95. For the special case of simple graphs (i.e., graphs that do not contain parallel edges) we further improve this to 3.77. Intuitively, solving the problem for simple graphs is easier as they do not contain cycles of length two. A natural question that arises is whether we can obtain a ratio arbitrarily close to e by assuming the graph has a large enough girth. We answer this question affirmatively, proving that one can obtain a competitive ratio arbitrarily close to e even for constant values of girth, providing further evidence for the strong matroid secretary conjecture. We further show that this bound is tight: for any constant g, one cannot obtain a competitive ratio better than e even if we assume that the input graph has girth at least g. To our knowledge, such a bound was not previously known even for simple graphs.

We investigate the problem of sequentially selecting elements of an unknown matroid in an online manner to form an independent set, with the goal of maximizing the minimum probability of acceptance across all elements, a property we define as $f$-fairness. Under adversarial arrival orders, we design an $\alpha(\ln(k)+1)$-fair algorithm, where $\alpha$ is the arboricity of the matroid and $k$ is the rank, a result that is nearly optimal. For laminar matroids, we develop an $(2\alpha-1)$-fair algorithm, which is optimal up to constant factors, achieved through a novel online coloring scheme. In the random arrival order setting, we achieve a $(4+o(1))\alpha$-fair algorithm for graphic matroids, matching the optimal result up to constant factors, relying on a novel technique for learning a degeneracy ordering using a sampled subset of edges. We further generalize our result to $p$-matchoids, obtaining a $\beta(p\ln k+1)$-fair algorithm for the adversarial arrival model, where $\beta$ is the optimal offline fairness. Notably, all our results can be extended to a setting with no prior knowledge of the matroid with only a logarithmic increase in the fairness factor.

Understanding the formation of opinions on multiple interconnected topics within social networks is of significant importance. It offers insights into collective behavior and decision-making processes, with applications in Graph Neural Networks. Existing models propose that individuals form opinions based on a weighted average of their peers' opinions and potentially their own beliefs. This averaging process, when viewed as a best-response game, can be seen as an individual minimizing disagreements with peers, defined by a quadratic penalty, leading to an equilibrium. Bindel, Kleinberg, and Oren (FOCS 2011) provided tight bounds on the "price of anarchy," which is defined as the maximum level of overall disagreement at equilibrium relative to a social optimum. Bhawalkar, Gollapudi, and Munagala (STOC 2013) generalized the penalty function to consider non-quadratic penalties and provided tight bounds on the price of anarchy of these functions.