Research map / Multi-agent systems and games / Games and equilibria
Learning NP-Hard Multi-Agent Assignment Planning using GNN: Inference on a Random Graph and Provable Auction-Fitted Q-learning
HYUNWOOK KANG, Taehwan Kwon, Jinkyoo Park, James R. Morrison
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| compare against Gurobi optimal on linear deterministic MRRC | OTAP + AFQI · MRRC linear deterministic | reward ratio rho (%): 95.35 to 98.31 of optimal (range over sizes) | Hurt |
| zero-shot transfer to larger problems (train 2R/20T, test 8R/50T) | OTAP + AFQI · MRRC linear deterministic | reward ratio rho (%): 96.85 -> 93.44 | Hurt |
| zero-shot transfer to smaller problems (train 8R/50T, test 3R/30T) | OTAP + AFQI · MRRC linear deterministic | reward ratio rho (%): 97.35 | No clear effect |
| use stochastic instead of deterministic travel times | OTAP + AFQI · MRRC linear, 2R/20T vs SGA | reward ratio rho (%): 137.3 -> 130.9 | No clear effect |
| use nonlinear instead of linear decaying rewards | OTAP + AFQI · MRRC deterministic, 2R/20T vs SGA | reward ratio rho (%): 137.3 -> 111.5 | Mixed |
| OTAP + AFQI instead of Ekici et al. heuristic | OTAP + AFQI · MRRC linear deterministic | reward ratio rho (%): 99.86 -> 118.33 | Mixed |
| OTAP + AFQI instead of SGA | OTAP + AFQI · MRRC linear deterministic, 8R/50T | reward ratio rho (%): 119.8 | Improved |
| increase problem size (tasks/robots) during training | AFQI · MRRC linear deterministic | training time to 93% optimality: 19261.2 -> 99032.7 | No clear effect |
| increase number of tasks in IPMS from 50 to 100 (3 machines) | Ours · IPMS | makespan ratio vs OR-Tools: 106.7% -> 100.7% | Improved |
| increase machines from 3 to 10 at 100 tasks in IPMS | Ours · IPMS | makespan ratio vs OR-Tools: 100.7% -> 109.0% | Hurt |
| compare with Google OR-Tools on minimax mTSP | Ours · minimax mTSP | average ratio to CPLEX: 1.0180 -> 1.0268 | Hurt |
| use random-graph structure2vec with OTAP instead of exact argmax in FQI | AFQI · theory | performance guarantee: 1-1/e | Improved |
Closest papers by meaning
- Efficient Reinforcement Learning in Probabilistic Reward Machines (AAAI 2025 · similarity 0.84)
- Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems (AAAI 2025 · similarity 0.84)
- Divide, Harmonize, Then Conquer It: Shooting Multi-Commodity Flow Problems with Multimodal Language Models (ICLR 2026 · similarity 0.84)
- Preference Optimization for Combinatorial Optimization Problems (ICML 2025 · similarity 0.84)
- Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs (AAAI 2024 · similarity 0.83)
- GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
