technical paper

AAMAS 2020

May 11, 2020

Live on Underline

Convexity of Hypergraph Matching Game

DOI: 10.48448/v3ez-9023

The hypergraph matching game is a cooperative game defined on a hypergraph such that the vertices are the players, and the characteristic function is the value of a maximum hypergraph matching on a hypergraph induced by a coalition. In this talk, we study a computationally tractable condition of the hypergraph matching game, called the convexity. First, we prove that the problem of checking whether a given hypergraph matching game is convex or not is solvable in polynomial time. Second, we prove that the Shapley value of a given convex hypergraph matching game is exactly computable in polynomial time. Finally, we consider the fractional hypergraph matching game and prove that if the fractional hypergraph matching game is convex, then its characteristic function coincides with the characteristic function of the corresponding (integral) hypergraph matching game.

Downloads

Slides

Next from AAMAS 2020

technical paper

Optimal Control in Partially Observable Complex Social Systems

AAMAS 2020

Fan Yang and 2 other authors

11 May 2020

Similar lecture

technical paper

Distance Hedonic Games

AAMAS 2020

+1
Michaela Strinzel and 3 other authors

11 May 2020

Stay up to date with the latest Underline news!

PRESENTATIONS

  • All Lectures
  • For Librarians
  • Resource Center
  • Free Trial
Underline Science, Inc.
1216 Broadway, 2nd Floor, New York, NY 10001, USA

© 2023 Underline - All rights reserved