Alternatives to Truthfulness Are Hard to Recognize View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

Vincenzo Auletta , Paolo Penna , Giuseppe Persiano , Carmine Ventre

ABSTRACT

The central question in mechanism design is how to implement a given social choice function. One of the most studied concepts is that of truthful implementations in which truth-telling is always the best response of the players. The Revelation Principle says that one can focus on truthful implementations without loss of generality (if there is no truthful implementation then there is no implementation at all). Green and Laffont [1] showed that, in the scenario in which players’ responses can be partially verified, the revelation principle holds only in some particular cases. When the Revelation Principle does not hold, non-truthful implementations become interesting since they might be the only way to implement a social choice function of interest. In this work we show that, although non-truthful implementations may exist, they are hard to find. Namely, it is NP-hard to decide if a given social choice function can be implemented in a non-truthful manner, or even if it can be implemented at all. This is in contrast to the fact that truthful implementability can be recognized efficiently, even when partial verification of the agents is allowed. Our results also show that there is no “simple” characterization of those social choice functions for which it is worth looking for non-truthful implementations. More... »

PAGES

194-205

Book

TITLE

Algorithmic Game Theory

ISBN

978-3-540-79308-3
978-3-540-79309-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-79309-0_18

DOI

http://dx.doi.org/10.1007/978-3-540-79309-0_18

DIMENSIONS

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


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/2203", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Philosophy", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/22", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Philosophy and Religious Studies", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Salerno", 
          "id": "https://www.grid.ac/institutes/grid.11780.3f", 
          "name": [
            "Dipartimento di Informatica ed Applicazioni, Universit\u00e0 di Salerno, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Auletta", 
        "givenName": "Vincenzo", 
        "id": "sg:person.016327521101.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016327521101.60"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Salerno", 
          "id": "https://www.grid.ac/institutes/grid.11780.3f", 
          "name": [
            "Dipartimento di Informatica ed Applicazioni, Universit\u00e0 di Salerno, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Penna", 
        "givenName": "Paolo", 
        "id": "sg:person.013624103516.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Salerno", 
          "id": "https://www.grid.ac/institutes/grid.11780.3f", 
          "name": [
            "Dipartimento di Informatica ed Applicazioni, Universit\u00e0 di Salerno, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Persiano", 
        "givenName": "Giuseppe", 
        "id": "sg:person.013255374317.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013255374317.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Liverpool", 
          "id": "https://www.grid.ac/institutes/grid.10025.36", 
          "name": [
            "Computer Science Department, University of Liverpool, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ventre", 
        "givenName": "Carmine", 
        "id": "sg:person.013762200435.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013762200435.42"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0304-4068(87)90007-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007161802"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/pl00013697", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028800828", 
          "https://doi.org/10.1007/pl00013697"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2297639", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069869023"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2008", 
    "datePublishedReg": "2008-01-01", 
    "description": "The central question in mechanism design is how to implement a given social choice function. One of the most studied concepts is that of truthful implementations in which truth-telling is always the best response of the players. The Revelation Principle says that one can focus on truthful implementations without loss of generality (if there is no truthful implementation then there is no implementation at all). Green and Laffont [1] showed that, in the scenario in which players\u2019 responses can be partially verified, the revelation principle holds only in some particular cases. When the Revelation Principle does not hold, non-truthful implementations become interesting since they might be the only way to implement a social choice function of interest. In this work we show that, although non-truthful implementations may exist, they are hard to find. Namely, it is NP-hard to decide if a given social choice function can be implemented in a non-truthful manner, or even if it can be implemented at all. This is in contrast to the fact that truthful implementability can be recognized efficiently, even when partial verification of the agents is allowed. Our results also show that there is no \u201csimple\u201d characterization of those social choice functions for which it is worth looking for non-truthful implementations.", 
    "editor": [
      {
        "familyName": "Monien", 
        "givenName": "Burkhard", 
        "type": "Person"
      }, 
      {
        "familyName": "Schroeder", 
        "givenName": "Ulf-Peter", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-79309-0_18", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-79308-3", 
        "978-3-540-79309-0"
      ], 
      "name": "Algorithmic Game Theory", 
      "type": "Book"
    }, 
    "name": "Alternatives to Truthfulness Are Hard to Recognize", 
    "pagination": "194-205", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051927126"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-79309-0_18"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f759bd3812859aa95484b62d2c57f479b78515a6686964b35ed43c3495a9cece"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-79309-0_18", 
      "https://app.dimensions.ai/details/publication/pub.1051927126"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T07:32", 
    "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/0000000356_0000000356/records_57900_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-79309-0_18"
  }
]
 

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-79309-0_18'

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-79309-0_18'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-79309-0_18'

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-79309-0_18'


 

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

104 TRIPLES      23 PREDICATES      30 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-79309-0_18 schema:about anzsrc-for:22
2 anzsrc-for:2203
3 schema:author N343feb45d2644c4d89cde03f70cbe8c1
4 schema:citation sg:pub.10.1007/pl00013697
5 https://doi.org/10.1016/0304-4068(87)90007-3
6 https://doi.org/10.2307/2297639
7 schema:datePublished 2008
8 schema:datePublishedReg 2008-01-01
9 schema:description The central question in mechanism design is how to implement a given social choice function. One of the most studied concepts is that of truthful implementations in which truth-telling is always the best response of the players. The Revelation Principle says that one can focus on truthful implementations without loss of generality (if there is no truthful implementation then there is no implementation at all). Green and Laffont [1] showed that, in the scenario in which players’ responses can be partially verified, the revelation principle holds only in some particular cases. When the Revelation Principle does not hold, non-truthful implementations become interesting since they might be the only way to implement a social choice function of interest. In this work we show that, although non-truthful implementations may exist, they are hard to find. Namely, it is NP-hard to decide if a given social choice function can be implemented in a non-truthful manner, or even if it can be implemented at all. This is in contrast to the fact that truthful implementability can be recognized efficiently, even when partial verification of the agents is allowed. Our results also show that there is no “simple” characterization of those social choice functions for which it is worth looking for non-truthful implementations.
10 schema:editor N939ed7a1d1c24d8c835c35d2b44f7f68
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree true
14 schema:isPartOf Nfe2feeaab1184ce9a02b3c9250fcfc46
15 schema:name Alternatives to Truthfulness Are Hard to Recognize
16 schema:pagination 194-205
17 schema:productId N1fd56e403b084840a57c0adf984dc697
18 Nadef60acd48e4f4eafca0b87ac1125d3
19 Nd2224b24354d458e8c26d5f419ae9d74
20 schema:publisher N38f80b5b9b454c388f6053ea0c3433fc
21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051927126
22 https://doi.org/10.1007/978-3-540-79309-0_18
23 schema:sdDatePublished 2019-04-16T07:32
24 schema:sdLicense https://scigraph.springernature.com/explorer/license/
25 schema:sdPublisher Nb675bd552dc14cd3be71b9247003d61f
26 schema:url https://link.springer.com/10.1007%2F978-3-540-79309-0_18
27 sgo:license sg:explorer/license/
28 sgo:sdDataset chapters
29 rdf:type schema:Chapter
30 N0cffd3f2552740ee89af1e0b8b430e67 schema:familyName Monien
31 schema:givenName Burkhard
32 rdf:type schema:Person
33 N1fd56e403b084840a57c0adf984dc697 schema:name doi
34 schema:value 10.1007/978-3-540-79309-0_18
35 rdf:type schema:PropertyValue
36 N343feb45d2644c4d89cde03f70cbe8c1 rdf:first sg:person.016327521101.60
37 rdf:rest Nfede3274c3f44739965007e86fbb0258
38 N38f80b5b9b454c388f6053ea0c3433fc schema:location Berlin, Heidelberg
39 schema:name Springer Berlin Heidelberg
40 rdf:type schema:Organisation
41 N3f6b943e3cf64aae86aa566f342cc79d schema:familyName Schroeder
42 schema:givenName Ulf-Peter
43 rdf:type schema:Person
44 N4ab73db6b7984b3e82d11f241317c003 rdf:first sg:person.013762200435.42
45 rdf:rest rdf:nil
46 N717863f0fa0d41a3a4d588600010af06 rdf:first N3f6b943e3cf64aae86aa566f342cc79d
47 rdf:rest rdf:nil
48 N83c68618deac4258966869623226f148 rdf:first sg:person.013255374317.27
49 rdf:rest N4ab73db6b7984b3e82d11f241317c003
50 N939ed7a1d1c24d8c835c35d2b44f7f68 rdf:first N0cffd3f2552740ee89af1e0b8b430e67
51 rdf:rest N717863f0fa0d41a3a4d588600010af06
52 Nadef60acd48e4f4eafca0b87ac1125d3 schema:name readcube_id
53 schema:value f759bd3812859aa95484b62d2c57f479b78515a6686964b35ed43c3495a9cece
54 rdf:type schema:PropertyValue
55 Nb675bd552dc14cd3be71b9247003d61f schema:name Springer Nature - SN SciGraph project
56 rdf:type schema:Organization
57 Nd2224b24354d458e8c26d5f419ae9d74 schema:name dimensions_id
58 schema:value pub.1051927126
59 rdf:type schema:PropertyValue
60 Nfe2feeaab1184ce9a02b3c9250fcfc46 schema:isbn 978-3-540-79308-3
61 978-3-540-79309-0
62 schema:name Algorithmic Game Theory
63 rdf:type schema:Book
64 Nfede3274c3f44739965007e86fbb0258 rdf:first sg:person.013624103516.76
65 rdf:rest N83c68618deac4258966869623226f148
66 anzsrc-for:22 schema:inDefinedTermSet anzsrc-for:
67 schema:name Philosophy and Religious Studies
68 rdf:type schema:DefinedTerm
69 anzsrc-for:2203 schema:inDefinedTermSet anzsrc-for:
70 schema:name Philosophy
71 rdf:type schema:DefinedTerm
72 sg:person.013255374317.27 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
73 schema:familyName Persiano
74 schema:givenName Giuseppe
75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013255374317.27
76 rdf:type schema:Person
77 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
78 schema:familyName Penna
79 schema:givenName Paolo
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
81 rdf:type schema:Person
82 sg:person.013762200435.42 schema:affiliation https://www.grid.ac/institutes/grid.10025.36
83 schema:familyName Ventre
84 schema:givenName Carmine
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013762200435.42
86 rdf:type schema:Person
87 sg:person.016327521101.60 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
88 schema:familyName Auletta
89 schema:givenName Vincenzo
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016327521101.60
91 rdf:type schema:Person
92 sg:pub.10.1007/pl00013697 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028800828
93 https://doi.org/10.1007/pl00013697
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1016/0304-4068(87)90007-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007161802
96 rdf:type schema:CreativeWork
97 https://doi.org/10.2307/2297639 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069869023
98 rdf:type schema:CreativeWork
99 https://www.grid.ac/institutes/grid.10025.36 schema:alternateName University of Liverpool
100 schema:name Computer Science Department, University of Liverpool, UK
101 rdf:type schema:Organization
102 https://www.grid.ac/institutes/grid.11780.3f schema:alternateName University of Salerno
103 schema:name Dipartimento di Informatica ed Applicazioni, Università di Salerno, Italy
104 rdf:type schema:Organization
 




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


...