A Polynomial-Time Algorithm for EFX Orientations of Chores

• URL: http://arxiv.org/abs/2501.13481v1
• Date: Thu, 23 Jan 2025 08:53:18 GMT
• Title: A Polynomial-Time Algorithm for EFX Orientations of Chores
• Authors: Kevin Hsu, Valerie King,
• Abstract summary: We show a surprising separation between the case of goods and the case of chores. We also show the analogous decision problem for multigraphs to be NP-complete.
• Score: 0.0
• License:
• Abstract: This paper addresses the problem of finding EFX orientations of graphs of chores, in which each vertex corresponds to an agent, each edge corresponds to a chore, and a chore has zero marginal utility to an agent if its corresponding edge is not incident to the vertex corresponding to the agent. Recently, Zhou~et~al.~(IJCAI,~2024) analyzed the complexity of deciding whether graphs containing a mixture of goods and chores admit EFX orientations, and conjectured that deciding whether graphs containing only chores admit EFX orientations is NP-complete. In this paper, we resolve this conjecture by exhibiting a polynomial-time algorithm that finds an EFX orientation of a graph containing only chores if one exists, even if the graph contains self-loops. Remarkably, our first result demonstrates a surprising separation between the case of goods and the case of chores, because deciding whether graphs containing only goods admit EFX orientations of goods was shown to be NP-complete by Christodoulou et al.~(EC,~2023). In addition, we show the analogous decision problem for multigraphs to be NP-complete.

Related papers

• Testing Dependency of Weighted Random Graphs [4.0554893636822]
  We study the task of detecting the edge dependency between two random graphs. For general edge-weight distributions, we establish thresholds at which optimal testing becomes information-theoretically possible or impossible.
  arXiv  Detail & Related papers  (2024-09-23T10:07:41Z)
• Fine-grained Graph Rationalization [51.293401030058085]
  We propose fine-grained graph rationalization (FIG) for graph machine learning. Our idea is driven by the self-attention mechanism, which provides rich interactions between input nodes. Our experiments involve 7 real-world datasets, and the proposed FIG shows significant performance advantages compared to 13 baseline methods.
  arXiv  Detail & Related papers  (2023-12-13T02:56:26Z)
• The Complexity of Envy-Free Graph Cutting [44.58084909019557]
  We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, and every agent must be assigned a connected piece of this graph. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents and the number of edges in the graph.
  arXiv  Detail & Related papers  (2023-12-12T07:54:30Z)
• Towards Self-Interpretable Graph-Level Anomaly Detection [73.1152604947837]
  Graph-level anomaly detection (GLAD) aims to identify graphs that exhibit notable dissimilarity compared to the majority in a collection. We propose a Self-Interpretable Graph aNomaly dETection model ( SIGNET) that detects anomalous graphs as well as generates informative explanations simultaneously.
  arXiv  Detail & Related papers  (2023-10-25T10:10:07Z)
• ALEX: Towards Effective Graph Transfer Learning with Noisy Labels [11.115297917940829]
  We introduce a novel technique termed Balance Alignment and Information-aware Examination (ALEX) to address the problem of graph transfer learning. ALEX first employs singular value decomposition to generate different views with crucial structural semantics, which help provide robust node representations. Building on this foundation, an adversarial domain discriminator is incorporated for the implicit domain alignment of complex multi-modal distributions.
  arXiv  Detail & Related papers  (2023-09-26T04:59:49Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• Towards Explanation for Unsupervised Graph-Level Representation Learning [108.31036962735911]
  Existing explanation methods focus on the supervised settings, eg, node classification and graph classification, while the explanation for unsupervised graph-level representation learning is still unexplored. In this paper, we advance the Information Bottleneck principle (IB) to tackle the proposed explanation problem for unsupervised graph representations, which leads to a novel principle, textitUnsupervised Subgraph Information Bottleneck (USIB) We also theoretically analyze the connection between graph representations and explanatory subgraphs on the label space, which reveals that the robustness of representations benefit the fidelity of explanatory subgraphs.
  arXiv  Detail & Related papers  (2022-05-20T02:50:15Z)
• Graph-wise Common Latent Factor Extraction for Unsupervised Graph Representation Learning [40.70562886682939]
  We propose a new principle for unsupervised graph representation learning: Graph-wise Common latent Factor EXtraction (GCFX) GCFX explicitly extract common latent factors from an input graph and achieve improved results on downstream tasks to the current state-of-the-art. Through extensive experiments and analysis, we demonstrate that GCFX is beneficial for graph-level tasks to alleviate distractions caused by local variations of individual nodes or local neighbourhoods.
  arXiv  Detail & Related papers  (2021-12-16T12:22:49Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  We tackle the problem of exactly recovering an unknown ground-truth binary labeling of the nodes from a single corrupted observation of each edge. We apply a hierarchy of relaxations known as the sum-of-squares hierarchy, to the problem. We show that the solution of the dual of the relaxed problem is related to finding edge weights of the Johnson and Kneser graphs.
  arXiv  Detail & Related papers  (2021-02-16T08:36:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.