Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Maximizing Nash Social Welfare in 2-Value Instances: The Half-Integer Case

Akrami, H., Ray Chaudhury, B., Hoefer, M., Mehlhorn, K., Schmalhofer, M., Shahkarami, G., et al. (2022). Maximizing Nash Social Welfare in 2-Value Instances: The Half-Integer Case. Retrieved from https://arxiv.org/abs/2207.10949.

Item is

Basisdaten

einblenden: ausblenden:
Genre: Forschungspapier

Dateien

einblenden: Dateien
ausblenden: Dateien
:
arXiv:2207.10949.pdf (Preprint), 306KB
Name:
arXiv:2207.10949.pdf
Beschreibung:
File downloaded from arXiv at 2023-01-04 15:19
OA-Status:
Grün
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Akrami, Hannaneh1, Autor           
Ray Chaudhury, Bhaskar2, Autor           
Hoefer, Martin2, Autor           
Mehlhorn, Kurt1, Autor                 
Schmalhofer, Marco2, Autor
Shahkarami, Golnoosh1, Autor           
Varricchio, Giovanna2, Autor
Vermande, Quentin2, Autor
van Wijland, Ernest2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: Computer Science, Computer Science and Game Theory, cs.GT
 Zusammenfassung: We consider the problem of maximizing the Nash social welfare when allocating
a set $G$ of indivisible goods to a set $N$ of agents. We study instances, in
which all agents have 2-value additive valuations: The value of a good $g \in
G$ for an agent $i \in N$ is either $1$ or $s$, where $s$ is an odd multiple of
$\frac{1}{2}$ larger than one. We show that the problem is solvable in
polynomial time. Akrami et at. showed that this problem is solvable in
polynomial time if $s$ is integral and is NP-hard whenever $s = \frac{p}{q}$,
$p \in \mathbb{N}$ and $q\in \mathbb{N}$ are co-prime and $p > q \ge 3$. For
the latter situation, an approximation algorithm was also given. It obtains an
approximation ratio of at most $1.0345$. Moreover, the problem is APX-hard,
with a lower bound of $1.000015$ achieved at $\frac{p}{q} = \frac{5}{4}$. The
case $q = 2$ and odd $p$ was left open.
In the case of integral $s$, the problem is separable in the sense that the
optimal allocation of the heavy goods (= value $s$ for some agent) is
independent of the number of light goods (= value $1$ for all agents). This
leads to an algorithm that first computes an optimal allocation of the heavy
goods and then adds the light goods greedily. This separation no longer holds
for $s = \frac{3}{2}$; a simple example is given in the introduction. Thus an
algorithm has to consider heavy and light goods together. This complicates
matters considerably. Our algorithm is based on a collection of improvement
rules that transfers any allocation into an optimal allocation and exploits a
connection to matchings with parity constraints.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2022-07-222022-08-032022
 Publikationsstatus: Online veröffentlicht
 Seiten: 30 p.
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: arXiv: 2207.10949
BibTex Citekey: Akrami2207.10949
URI: https://arxiv.org/abs/2207.10949
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: