More Like this

1. The Dichotomous Affiliate Stable Matching Problem: Approval-Based Matching with Applicant-Employer Relations

   Knittel, Marina ; Dooley, Samuel ; Dickerson, John P. ( July 2022 , Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence)

   While the stable marriage problem and its variants model a vast range of matching markets, they fail to capture complex agent relationships, such as the affiliation of applicants and employers in an interview marketplace. To model this problem, the existing literature on matching with externalities permits agents to provide complete and total rankings over matchings based off of both their own and their affiliates' matches. This complete ordering restriction is unrealistic, and further the model may have an empty core. To address this, we introduce the Dichotomous Affiliate Stable Matching (DASM) Problem, where agents' preferences indicate dichotomous acceptance or rejection of another agent in the marketplace, both for themselves and their affiliates. We also assume the agent's preferences over entire matchings are determined by a general weighted valuation function of their (and their affiliates') matches. Our results are threefold: (1) we use a human study to show that real-world matching rankings follow our assumed valuation function; (2) we prove that there always exists a stable solution by providing an efficient, easily-implementable algorithm that finds such a solution; and (3) we experimentally validate the efficiency of our algorithm versus a linear-programming-based approach. 

   more » « less
2. Bilu-Linial Stability, Certified Algorithms and the Independent Set Problem

   Angelidakis, H ; Awasthi, P. ; Blum, A. ; Chatziafratis, V. ; Dan, C. ( September 2019 , 27th Annual European Symposium on Algorithms (ESA 2019))

   We study the classic Maximum Independent Set problem under the notion of stability introduced by Bilu and Linial (2010): a weighted instance of Independent Set is γ-stable if it has a unique optimal solution that remains the unique optimal solution under multiplicative perturbations of the weights by a factor of at most γ ≥ 1. The goal then is to efficiently recover this “pronounced” optimal solution exactly. In this work, we solve stable instances of Independent Set on several classes of graphs: we improve upon previous results by solving \tilde{O}(∆/sqrt(log ∆))-stable instances on graphs of maximum degree ∆, (k − 1)-stable instances on k-colorable graphs and (1 + ε)-stable instances on planar graphs (for any fixed ε > 0), using both combinatorial techniques as well as LPs and the Sherali-Adams hierarchy. For general graphs, we give an algorithm for (εn)-stable instances, for any fixed ε > 0, and lower bounds based on the planted clique conjecture. As a by-product of our techniques, we give algorithms as well as lower bounds for stable instances of Node Multiway Cut (a generalization of Edge Multiway Cut), by exploiting its connections to Vertex Cover. Furthermore, we prove a general structural result showing that the integrality gap of convex relaxations of several maximization problems reduces dramatically on stable instances. Moreover, we initiate the study of certified algorithms for Independent Set. The notion of a γ-certified algorithm was introduced very recently by Makarychev and Makarychev (2018) and it is a class of γ-approximation algorithms that satisfy one crucial property: the solution returned is optimal for a perturbation of the original instance, where perturbations are again multiplicative up to a factor of γ ≥ 1 (hence, such algorithms not only solve γ-stable instances optimally, but also have guarantees even on unstable instances). Here, we obtain ∆-certified algorithms for Independent Set on graphs of maximum degree ∆, and (1 + ε)-certified algorithms on planar graphs. Finally, we analyze the algorithm of Berman and Fürer (1994) and prove that it is a ((∆+1)/3 + ε)-certified algorithm for Independent Set on graphs of maximum degree ∆ where all weights are equal to 1. 

   more » « less
3. UNSUPERVISED DOMAIN ADAPTATION USING REGULARIZED HYPER-GRAPH MATCHING

   https://doi.org/https://doi.org/10.1109/ICIP.2018.8451152  

   Das, Debasmit ; Lee, C.S. George ( October 2018 , Proceedings - International Conference on Image Processing)

   Domain adaptation (DA) addresses the real-world image classification problem of discrepancy between training (source) and testing (target) data distributions. We propose an unsupervised DA method that considers the presence of only unlabelled data in the target do- main. Our approach centers on finding matches between samples of the source and target domains. The matches are obtained by treating the source and target domains as hyper-graphs and carrying out a class-regularized hyper-graph matching using first-, second- and third-order similarities between the graphs. We have also developed a computationally efficient algorithm by initially selecting a subset of the samples to construct a graph and then developing a customized optimization routine for graph-matching based on Conditional Gradient and Alternating Direction Multiplier Method. This allows the proposed method to be used widely. We also performed a set of experiments on standard object recognition datasets to validate the effectiveness of our framework over previous approaches. 

   more » « less
4. Age and Sex as Determinants of Acute Domoic Acid Toxicity in a Mouse Model

   https://doi.org/10.3390/toxins15040259  

   Hendrix, Alicia M. ; Lefebvre, Kathi A. ; Bowers, Emily K. ; Stuppard, Rudolph ; Burbacher, Thomas ; Marcinek, David J. ( April 2023 , Toxins)

   The excitatory neurotoxin domoic acid (DA) consistently contaminates food webs in coastal regions around the world. Acute exposure to the toxin causes Amnesic Shellfish Poisoning, a potentially lethal syndrome of gastrointestinal- and seizure-related outcomes. Both advanced age and male sex have been suggested to contribute to interindividual DA susceptibility. To test this, we administered DA doses between 0.5 and 2.5 mg/kg body weight to female and male C57Bl/6 mice at adult (7–9-month-old) and aged (25–28-month-old) life stages and observed seizure-related activity for 90 min, at which point we euthanized the mice and collected serum, cortical, and kidney samples. We observed severe clonic–tonic convulsions in some aged individuals, but not in younger adults. We also saw an association between advanced age and the incidence of a moderately severe seizure-related outcome, hindlimb tremors, and between advanced age and overall symptom severity and persistence. Surprisingly, we additionally report that female mice, particularly aged female mice, demonstrated more severe neurotoxic symptoms following acute exposure to DA than males. Both age and sex patterns were reflected in tissue DA concentrations as well: aged mice and females had generally higher concentrations of DA in their tissues at 90 min post-exposure. This study contributes to the body of work that can inform intelligent, evidence-based public health protections for communities threatened by more frequent and extensive DA-producing algal blooms. 

   more » « less
5. Class Fairness in Online Matching

   https://doi.org/10.1609/aaai.v37i5.25704  

   Hosseini, Hadi ; Huang, Zhiyi ; Igarashi, Ayumi ; Shah, Nisarg ( June 2023 , Proceedings of the AAAI Conference on Artificial Intelligence)

   We initiate the study of fairness among classes of agents in online bipartite matching where there is a given set of offline vertices (aka agents) and another set of vertices (aka items) that arrive online and must be matched irrevocably upon arrival. In this setting, agents are partitioned into a set of classes and the matching is required to be fair with respect to the classes. We adopt popular fairness notions (e.g. envy-freeness, proportionality, and maximin share) and their relaxations to this setting and study deterministic and randomized algorithms for matching indivisible items (leading to integral matchings) and for matching divisible items (leading to fractional matchings).For matching indivisible items, we propose an adaptive-priority-based algorithm, MATCH-AND-SHIFT, prove that it achieves (1/2)-approximation of both class envy-freeness up to one item and class maximin share fairness, and show that each guarantee is tight. For matching divisible items, we design a water-filling-based algorithm, EQUAL-FILLING, that achieves (1-1/e)-approximation of class envy-freeness and class proportionality; we prove (1-1/e) to be tight for class proportionality and establish a 3/4 upper bound on class envy-freeness. 

   more » « less