Improved Lower Bounds for Non-utilitarian Truthfulness View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2008

AUTHORS

Iftah Gamzu

ABSTRACT

One of the most fundamental results in the field of mechanism design states that every utilitarian social choice function admits a mechanism that truthfully implements it. In stark contrast with this finding, when one considers a non-utilitarian social choice function, it turns out that no guarantees can be made, i.e. there are non-utilitarian functions, which cannot be truthfully implemented. In light of this state of affairs, one of the most natural and intriguing objectives of research is to understand the inherent limitations in the infrastructure of truthful mechanisms for non-utilitarian social choice functions. In this paper, we focus our attention on studying the boundaries imposed by truthfulness for two non-utilitarian multi-parameter optimization problems. The first is the workload minimization in inter-domain routing problem, and the other is the unrelated machines scheduling problem. Our main findings can be briefly summarized as follows: We prove that any truthful deterministic mechanism, and any universal truthful randomized mechanism for the workload minimization in inter-domain routing problem cannot achieve an approximation guarantee that is better than 2. These results improve the current lower bounds of and , which are due to Mu’alem and Schapira [SODA ’07].We establish a lower bound of on the achievable approximation ratio of any truthful deterministic mechanism for the unrelated machines scheduling problem when the number of machines is at least 3. This lower bound is comparable to a recent result by Christodoulou, Koutsoupias and Vidali [SODA ’07]. Nevertheless, our approach is considerably simpler, and thus may shed some new light on the core of this problem. We prove that any truthful deterministic mechanism, and any universal truthful randomized mechanism for the workload minimization in inter-domain routing problem cannot achieve an approximation guarantee that is better than 2. These results improve the current lower bounds of and , which are due to Mu’alem and Schapira [SODA ’07]. We establish a lower bound of on the achievable approximation ratio of any truthful deterministic mechanism for the unrelated machines scheduling problem when the number of machines is at least 3. This lower bound is comparable to a recent result by Christodoulou, Koutsoupias and Vidali [SODA ’07]. Nevertheless, our approach is considerably simpler, and thus may shed some new light on the core of this problem. More... »

PAGES

15-26

References to SciGraph publications

  • 2007. Mechanism Design for Fractional Scheduling on Unrelated Machines in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1971-09. Multipart pricing of public goods in PUBLIC CHOICE
  • 2005-07. A BGP-based mechanism for lowest-cost routing in DISTRIBUTED COMPUTING
  • 1993-02. An approximation algorithm for the generalized assignment problem in MATHEMATICAL PROGRAMMING
  • 1990-01. Approximation algorithms for scheduling unrelated parallel machines in MATHEMATICAL PROGRAMMING
  • Book

    TITLE

    Approximation and Online Algorithms

    ISBN

    978-3-540-77917-9
    978-3-540-77918-6

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-77918-6_2

    DOI

    http://dx.doi.org/10.1007/978-3-540-77918-6_2

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1030343069


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Numerical and Computational Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Tel Aviv University", 
              "id": "https://www.grid.ac/institutes/grid.12136.37", 
              "name": [
                "School of Computer Science, Tel-Aviv University, 69978, Tel-Aviv, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gamzu", 
            "givenName": "Iftah", 
            "id": "sg:person.012212237551.11", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012212237551.11"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01726210", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003499590", 
              "https://doi.org/10.1007/bf01726210"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01726210", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003499590", 
              "https://doi.org/10.1007/bf01726210"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01585745", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006292857", 
              "https://doi.org/10.1007/bf01585745"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1064009.1064040", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021789994"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1060590.1060639", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025774284"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-005-0122-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026876838", 
              "https://doi.org/10.1007/s00446-005-0122-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-005-0122-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026876838", 
              "https://doi.org/10.1007/s00446-005-0122-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01585178", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032899049", 
              "https://doi.org/10.1007/bf01585178"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1132516.1132607", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033789959"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1250910.1250947", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033988833"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/game.1999.0790", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036056755"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-73420-8_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044107492", 
              "https://doi.org/10.1007/978-3-540-73420-8_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-73420-8_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044107492", 
              "https://doi.org/10.1007/978-3-540-73420-8_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1111/j.1468-0262.2006.00695.x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046583996"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/1914085", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1069641186"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1977.24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086173273"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2008", 
        "datePublishedReg": "2008-01-01", 
        "description": "One of the most fundamental results in the field of mechanism design states that every utilitarian social choice function admits a mechanism that truthfully implements it. In stark contrast with this finding, when one considers a non-utilitarian social choice function, it turns out that no guarantees can be made, i.e. there are non-utilitarian functions, which cannot be truthfully implemented. In light of this state of affairs, one of the most natural and intriguing objectives of research is to understand the inherent limitations in the infrastructure of truthful mechanisms for non-utilitarian social choice functions. In this paper, we focus our attention on studying the boundaries imposed by truthfulness for two non-utilitarian multi-parameter optimization problems. The first is the workload minimization in inter-domain routing problem, and the other is the unrelated machines scheduling problem. Our main findings can be briefly summarized as follows: We prove that any truthful deterministic mechanism, and any universal truthful randomized mechanism for the workload minimization in inter-domain routing problem cannot achieve an approximation guarantee that is better than 2. These results improve the current lower bounds of and , which are due to Mu\u2019alem and Schapira [SODA \u201907].We establish a lower bound of on the achievable approximation ratio of any truthful deterministic mechanism for the unrelated machines scheduling problem when the number of machines is at least 3. This lower bound is comparable to a recent result by Christodoulou, Koutsoupias and Vidali [SODA \u201907]. Nevertheless, our approach is considerably simpler, and thus may shed some new light on the core of this problem. We prove that any truthful deterministic mechanism, and any universal truthful randomized mechanism for the workload minimization in inter-domain routing problem cannot achieve an approximation guarantee that is better than 2. These results improve the current lower bounds of and , which are due to Mu\u2019alem and Schapira [SODA \u201907]. We establish a lower bound of on the achievable approximation ratio of any truthful deterministic mechanism for the unrelated machines scheduling problem when the number of machines is at least 3. This lower bound is comparable to a recent result by Christodoulou, Koutsoupias and Vidali [SODA \u201907]. Nevertheless, our approach is considerably simpler, and thus may shed some new light on the core of this problem.", 
        "editor": [
          {
            "familyName": "Kaklamanis", 
            "givenName": "Christos", 
            "type": "Person"
          }, 
          {
            "familyName": "Skutella", 
            "givenName": "Martin", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-77918-6_2", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-77917-9", 
            "978-3-540-77918-6"
          ], 
          "name": "Approximation and Online Algorithms", 
          "type": "Book"
        }, 
        "name": "Improved Lower Bounds for Non-utilitarian Truthfulness", 
        "pagination": "15-26", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-77918-6_2"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "908c341e562c99b7d86c89a7ea6ec7a2c7dd9ae20b22b5e12f2b1f53e64af009"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1030343069"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-77918-6_2", 
          "https://app.dimensions.ai/details/publication/pub.1030343069"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T06:03", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000349_0000000349/records_113667_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-77918-6_2"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-77918-6_2'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-77918-6_2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-77918-6_2'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-77918-6_2'


     

    This table displays all metadata directly associated to this object as RDF triples.

    114 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-77918-6_2 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author Na93e4e27aedd4caeaf83e7e90aab7a86
    4 schema:citation sg:pub.10.1007/978-3-540-73420-8_6
    5 sg:pub.10.1007/bf01585178
    6 sg:pub.10.1007/bf01585745
    7 sg:pub.10.1007/bf01726210
    8 sg:pub.10.1007/s00446-005-0122-y
    9 https://doi.org/10.1006/game.1999.0790
    10 https://doi.org/10.1109/sfcs.1977.24
    11 https://doi.org/10.1111/j.1468-0262.2006.00695.x
    12 https://doi.org/10.1145/1060590.1060639
    13 https://doi.org/10.1145/1064009.1064040
    14 https://doi.org/10.1145/1132516.1132607
    15 https://doi.org/10.1145/1250910.1250947
    16 https://doi.org/10.2307/1914085
    17 schema:datePublished 2008
    18 schema:datePublishedReg 2008-01-01
    19 schema:description One of the most fundamental results in the field of mechanism design states that every utilitarian social choice function admits a mechanism that truthfully implements it. In stark contrast with this finding, when one considers a non-utilitarian social choice function, it turns out that no guarantees can be made, i.e. there are non-utilitarian functions, which cannot be truthfully implemented. In light of this state of affairs, one of the most natural and intriguing objectives of research is to understand the inherent limitations in the infrastructure of truthful mechanisms for non-utilitarian social choice functions. In this paper, we focus our attention on studying the boundaries imposed by truthfulness for two non-utilitarian multi-parameter optimization problems. The first is the workload minimization in inter-domain routing problem, and the other is the unrelated machines scheduling problem. Our main findings can be briefly summarized as follows: We prove that any truthful deterministic mechanism, and any universal truthful randomized mechanism for the workload minimization in inter-domain routing problem cannot achieve an approximation guarantee that is better than 2. These results improve the current lower bounds of and , which are due to Mu’alem and Schapira [SODA ’07].We establish a lower bound of on the achievable approximation ratio of any truthful deterministic mechanism for the unrelated machines scheduling problem when the number of machines is at least 3. This lower bound is comparable to a recent result by Christodoulou, Koutsoupias and Vidali [SODA ’07]. Nevertheless, our approach is considerably simpler, and thus may shed some new light on the core of this problem. We prove that any truthful deterministic mechanism, and any universal truthful randomized mechanism for the workload minimization in inter-domain routing problem cannot achieve an approximation guarantee that is better than 2. These results improve the current lower bounds of and , which are due to Mu’alem and Schapira [SODA ’07]. We establish a lower bound of on the achievable approximation ratio of any truthful deterministic mechanism for the unrelated machines scheduling problem when the number of machines is at least 3. This lower bound is comparable to a recent result by Christodoulou, Koutsoupias and Vidali [SODA ’07]. Nevertheless, our approach is considerably simpler, and thus may shed some new light on the core of this problem.
    20 schema:editor N602f1fdde7f0437791a84c20a97d7c83
    21 schema:genre chapter
    22 schema:inLanguage en
    23 schema:isAccessibleForFree false
    24 schema:isPartOf N55ff0b56a6a64d04b328bc8403608865
    25 schema:name Improved Lower Bounds for Non-utilitarian Truthfulness
    26 schema:pagination 15-26
    27 schema:productId N855ffa0253524b1c84de149959a4401a
    28 N8fd2a50194f8499f8bb2870325e8ba25
    29 N9e04ccf265304456a1195fcbd1ad4802
    30 schema:publisher N642ea541b24b49e790fa69d6946b88c6
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030343069
    32 https://doi.org/10.1007/978-3-540-77918-6_2
    33 schema:sdDatePublished 2019-04-16T06:03
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher N71ce0d9c8c334ab0bef078ed208a89ca
    36 schema:url https://link.springer.com/10.1007%2F978-3-540-77918-6_2
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset chapters
    39 rdf:type schema:Chapter
    40 N4f009bdbb43d496c8b0f066a2d62e421 schema:familyName Kaklamanis
    41 schema:givenName Christos
    42 rdf:type schema:Person
    43 N55ff0b56a6a64d04b328bc8403608865 schema:isbn 978-3-540-77917-9
    44 978-3-540-77918-6
    45 schema:name Approximation and Online Algorithms
    46 rdf:type schema:Book
    47 N5b161d56493b4c5a919c33da8b84330d rdf:first Naea7a5ae140e4d589fc76e95b716c68e
    48 rdf:rest rdf:nil
    49 N602f1fdde7f0437791a84c20a97d7c83 rdf:first N4f009bdbb43d496c8b0f066a2d62e421
    50 rdf:rest N5b161d56493b4c5a919c33da8b84330d
    51 N642ea541b24b49e790fa69d6946b88c6 schema:location Berlin, Heidelberg
    52 schema:name Springer Berlin Heidelberg
    53 rdf:type schema:Organisation
    54 N71ce0d9c8c334ab0bef078ed208a89ca schema:name Springer Nature - SN SciGraph project
    55 rdf:type schema:Organization
    56 N855ffa0253524b1c84de149959a4401a schema:name doi
    57 schema:value 10.1007/978-3-540-77918-6_2
    58 rdf:type schema:PropertyValue
    59 N8fd2a50194f8499f8bb2870325e8ba25 schema:name readcube_id
    60 schema:value 908c341e562c99b7d86c89a7ea6ec7a2c7dd9ae20b22b5e12f2b1f53e64af009
    61 rdf:type schema:PropertyValue
    62 N9e04ccf265304456a1195fcbd1ad4802 schema:name dimensions_id
    63 schema:value pub.1030343069
    64 rdf:type schema:PropertyValue
    65 Na93e4e27aedd4caeaf83e7e90aab7a86 rdf:first sg:person.012212237551.11
    66 rdf:rest rdf:nil
    67 Naea7a5ae140e4d589fc76e95b716c68e schema:familyName Skutella
    68 schema:givenName Martin
    69 rdf:type schema:Person
    70 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Mathematical Sciences
    72 rdf:type schema:DefinedTerm
    73 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Numerical and Computational Mathematics
    75 rdf:type schema:DefinedTerm
    76 sg:person.012212237551.11 schema:affiliation https://www.grid.ac/institutes/grid.12136.37
    77 schema:familyName Gamzu
    78 schema:givenName Iftah
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012212237551.11
    80 rdf:type schema:Person
    81 sg:pub.10.1007/978-3-540-73420-8_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044107492
    82 https://doi.org/10.1007/978-3-540-73420-8_6
    83 rdf:type schema:CreativeWork
    84 sg:pub.10.1007/bf01585178 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032899049
    85 https://doi.org/10.1007/bf01585178
    86 rdf:type schema:CreativeWork
    87 sg:pub.10.1007/bf01585745 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006292857
    88 https://doi.org/10.1007/bf01585745
    89 rdf:type schema:CreativeWork
    90 sg:pub.10.1007/bf01726210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003499590
    91 https://doi.org/10.1007/bf01726210
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1007/s00446-005-0122-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1026876838
    94 https://doi.org/10.1007/s00446-005-0122-y
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1006/game.1999.0790 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036056755
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1109/sfcs.1977.24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086173273
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1111/j.1468-0262.2006.00695.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1046583996
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1145/1060590.1060639 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025774284
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1145/1064009.1064040 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021789994
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1145/1132516.1132607 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033789959
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1145/1250910.1250947 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033988833
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.2307/1914085 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069641186
    111 rdf:type schema:CreativeWork
    112 https://www.grid.ac/institutes/grid.12136.37 schema:alternateName Tel Aviv University
    113 schema:name School of Computer Science, Tel-Aviv University, 69978, Tel-Aviv, Israel
    114 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...