Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

04.09.2018

Strategy-proof mechanisms for obnoxious facility game with bounded service range

Zeitschrift:
Journal of Combinatorial Optimization
Autoren:
Yukun Cheng, Qiaoming Han, Wei Yu, Guochuan Zhang
Wichtige Hinweise
A preliminary version of this paper appeared in the Proceedings of the 10th International Conference of Theory and Applications of Models of Computation (TAMC), HongKong.
This research was partially supported by the National Nature Science Foundation of China (Nos. 11871366, 61803279, 11771386, 11728104) and the Fundamental Research Fund for the Central Universities under Grant Number 22220184028.

Abstract

In this paper, we study the obnoxious facility game with a limited service capacity on a line network, in which all facilities are undesirable and necessary for agents, such as the garbage dumps. The limited service capacity restricts each facility only to serve the agents in its service radius \(r> 0\). All agents prefer to be far away from facilities, but still to be served by a facility. Namely, the distance between an agent and her nearest facility is at most r. In a deterministic or randomized mechanism, based on the addresses reported by the selfish agents, the locations or the location distributions of facilities are determined. The aim of the mechanisms is to maximize the obnoxious social welfare, the total distance between all agents and the facilities, on the premise of each agent being served. On the other hand, each agent tries to maximize her own utility, i.e., the distance from the facility, and she may lie if, by doing so, to get strictly more benefit. We are interested in mechanisms without money to elicit the true location profile (strategy-proofness or group strategy-proofness) and maximize the obnoxious social welfare as much as possible. In this paper, we give the first attempt for this game on a closed interval [0, 1], to design group strategy-proof deterministic and randomized mechanisms for the case of \(\frac{1}{2}\le r\le 1\). The approximation ratios, depending on the radius r, of different mechanisms are explored. We also provide the lower bounds on approximation ratios of deterministic strategy-proof mechanisms.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit dem Kombi-Abo erhalten Sie vollen Zugriff auf über 1,8 Mio. Dokumente aus mehr als 61.000 Fachbüchern und rund 500 Fachzeitschriften aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit dem Wirtschafts-Abo erhalten Sie Zugriff auf über 1 Mio. Dokumente aus mehr als 45.000 Fachbüchern und 300 Fachzeitschriften aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit dem Technik-Abo erhalten Sie Zugriff auf über 1 Mio. Dokumente aus mehr als 40.000 Fachbüchern und 300 Fachzeitschriften aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Premium Partner

Neuer Inhalt

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise