Optimization problems in network mechanism design

Abstract

We study approximation algorithms and design truthful mechanisms for optimization problems in networks that have direct applications in smart cities and urban planning. We present new models and new techniques which could be of independent interest. More specifically, in Chapter 2 we introduce a new model for pollution control and propose two applications of this model. This is the first time this problem is studied from the computational perspective. The network is represented by a graph where nodes are the pollutants and edges between pollutants represent the effect of spread of pollution. The government sets bounds on the levels of emitted pollution in both local areas and the whole network. We mainly study the classes of planar graphs and trees which model air and water pollution and design truthful approximate mechanisms. In Chapter 3 we introduce a new mechanism design model for a new model for the budgeted maximum lifetime coverage (BMLC) in wireless sensor networks (wsns). BMLC generalizes the known maximum lifetime coverage problem to the case where sensors are owned by selfish agents, where each agent has a private cost per unit time of how much to be paid for deploying his sensor. We introduce a random instances model for BMLC and design a novel approximate mechanism by reducing BMLC to the fractional knapsack which is truthful under some technical assumptions. For a closely related minimum coverage problem in wsns on unit disk graphs, we generalize a recent PTAS for this problem to obtain a truthful PTAS for the problem where sensors' costs are agents' private data. In Chapter 4 we study approximation algorithms which are based on the primal dual method for network connectivity problems. We then prove that these algorithms are monotone and thus can lead to truthful mechanisms. Finally in Chapter 5 we study the problem of facility location on the real line under non utilitarian objective functions. We extend previous models and derive inapproximability bounds for deterministic and randomized truthful mechanisms. As a byproduct we show that the same approximation guarantees hold for the social utility objective.

Μελετάμε προσεγγιστικούς αλγόριθμους και σχεδιάζουμε φιλαλήθεις μηχανισμούς για προβλήματα βελτιστοποίησης σε δίκτυα που έχουν άμεσες εφαρμογές σε έξυπνες πόλεις και πολεοδομικό σχεδιασμό. Παρουσιάζουμε νέα μοντέλα και νέες τεχνικές που θα μπορούσαν να έχουν ανεξάρτητο ενδιαφέρον. Πιο συγκεκριμένα, στο Κεφάλαιο 2 εισάγουμε ένα νέο μοντέλο ελέγχου της ρύπανσης και προτείνουμε δύο εφαρμογές αυτού του μοντέλου. Είναι η πρώτη φορά που αυτό το πρόβλημα μελετάται από υπολογιστική σκοπιά. Το δίκτυο αντιπροσωπεύεται από ένα γράφημα όπου οι κόμβοι είναι οι ρύποι και οι ακμές μεταξύ των ρύπων αντιπροσωπεύουν την επίδραση της εξάπλωσης της ρύπανσης. Η κυβέρνηση θέτει όρια στα επίπεδα της εκπεμπόμενης ρύπανσης τόσο στις τοπικές περιοχές όσο και σε ολόκληρο το δίκτυο. Μελετάμε κυρίως τις κατηγορίες επίπεδων γραφημάτων και δέντρων που μοντελοποιούν τη ρύπανση του αέρα και του νερού και σχεδιάζουν φιλαλήθεις κατά προσέγγιση μηχανισμούς. Στο Κεφάλαιο 3 παρουσιάζουμε ένα νέο μοντέλο σχεδιασμού μηχανισμών για ένα νέο μοντέλο για την προϋπολογισμένη μέγιστη κάλυψη διάρκειας ζωής (BMLC) σε ασύρματα δίκτυα αισθητήρων (wsns). Το BMLC γενικεύει το γνωστό πρόβλημα κάλυψης μέγιστης διάρκειας ζωής στην περίπτωση όπου οι αισθητήρες ανήκουν σε εγωιστές πράκτορες, όπου κάθε πράκτορας έχει ιδιωτικό κόστος ανά μονάδα χρόνου για το ποσό που πρέπει να πληρωθεί για την ανάπτυξη του αισθητήρα του. Εισάγουμε ένα μοντέλο τυχαίων περιπτώσεων για το BMLC και σχεδιάζουμε έναν νέο προσεγγιστικό μηχανισμό απλοποιώντας το BMLC στο πρόβλημα του σακιδίου, το οποίο είναι φιλαλήθες σύμφωνα με ορισμένες τεχνικές παραδοχές. Για ένα στενά συνδεδεμένο πρόβλημα ελάχιστης κάλυψης στα wsns σε γραφήματα μονάδας δίσκου, γενικεύουμε ένα πρόσφατο PTAS για αυτό το πρόβλημα για να λάβουμε ένα φιλαλήθες PTAS για το πρόβλημα όπου το κόστος των αισθητήρων είναι ιδιωτικά δεδομένα των πρακτόρων. Στο Κεφάλαιο 4 μελετάμε προσεγγιστικούς αλγόριθμους που βασίζονται στην πρωταρχική διπλή μέθοδο για προβλήματα συνδεσιμότητας δικτύου. Στη συνέχεια αποδεικνύουμε ότι αυτοί οι αλγόριθμοι είναι μονότονοι και έτσι μπορούν να οδηγήσουν σε φιλαλήθεις μηχανισμούς. Τέλος στο Κεφάλαιο 5 μελετάμε το πρόβλημα της θέσης της εγκατάστασης στην πραγματική γραμμή κάτω από μη ωφελιμιστικές αντικειμενικές συναρτήσεις. Επεκτείνουμε τα προηγούμενα μοντέλα και εξάγουμε όρια προσεγγίσεως για ντετερμινιστικούς και τυχαιοποιημένους φιλαλήθεις μηχανισμούς. Ως υποπροϊόν δείχνουμε ότι οι ίδιες εγγυήσεις προσέγγισης ισχύουν για τον στόχο κοινωνικής χρησιμότητας.