Power Diagram Detection with Applications to Information Elicitation View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2019-04

AUTHORS

Steffen Borgwardt, Rafael M. Frongillo

ABSTRACT

Power diagrams, a type of weighted Voronoi diagram, have many applications throughout operations research. We study the problem of power diagram detection: determining whether a given finite partition of Rd takes the form of a power diagram. This detection problem is particularly prevalent in the field of information elicitation, where one wishes to design contracts to incentivize self-minded agents to provide honest information. We devise a simple linear program to decide whether a polyhedral cell complex can be described as a power diagram. For positive instances, a representation of the cell complex as a power diagram is returned. Further, we discuss applications to property elicitation, peer prediction, and mechanism design, where this question arises. Our model can efficiently decide the question for complexes of Rd or of a convex subset thereof. The approach is based on the use of an alternative representation of power diagrams and invariance of a power diagram under uniform scaling of the parameters in this representation. More... »

PAGES

184-196

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10957-018-1442-y

DOI

http://dx.doi.org/10.1007/s10957-018-1442-y

DIMENSIONS

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


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/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Colorado Denver", 
          "id": "https://www.grid.ac/institutes/grid.241116.1", 
          "name": [
            "University of Colorado Denver, Denver, CO, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Borgwardt", 
        "givenName": "Steffen", 
        "id": "sg:person.013112364415.74", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013112364415.74"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Colorado Boulder", 
          "id": "https://www.grid.ac/institutes/grid.266190.a", 
          "name": [
            "University of Colorado Boulder, Boulder, CO, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Frongillo", 
        "givenName": "Rafael M.", 
        "id": "sg:person.012216112757.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012216112757.52"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0747-7171(87)80003-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001880026"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/10556789408805554", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002516943"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02187870", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003005419", 
          "https://doi.org/10.1007/bf02187870"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02187870", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003005419", 
          "https://doi.org/10.1007/bf02187870"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02187870", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003005419", 
          "https://doi.org/10.1007/bf02187870"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1386790.1386813", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011959116"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00283-014-9448-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019617669", 
          "https://doi.org/10.1007/s00283-014-9448-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-13129-0_29", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019882588", 
          "https://doi.org/10.1007/978-3-319-13129-0_29"
        ], 
        "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/1566374.1566391", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023603973"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10852-014-9263-y", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025300262", 
          "https://doi.org/10.1007/s10852-014-9263-y"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00181470", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031969818", 
          "https://doi.org/10.1007/bf00181470"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/pl00009434", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036408413", 
          "https://doi.org/10.1007/pl00009434"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/pl00009434", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036408413", 
          "https://doi.org/10.1007/pl00009434"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1008663629662", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038382810", 
          "https://doi.org/10.1023/a:1008663629662"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/pl00009187", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051809298", 
          "https://doi.org/10.1007/pl00009187"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/01621459.1971.10482346", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1058300819"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0216006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841952"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/110832707", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062864878"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1198/016214505000000907", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064198422"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/ijoc.4.4.369", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064707425"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/mnsc.1050.0379", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064714410"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/mnsc.1050.0379", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064714410"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ejor.2017.04.054", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1085079485"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/3070903", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1090927607"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/8685", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098932075"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-04", 
    "datePublishedReg": "2019-04-01", 
    "description": "Power diagrams, a type of weighted Voronoi diagram, have many applications throughout operations research. We study the problem of power diagram detection: determining whether a given finite partition of Rd takes the form of a power diagram. This detection problem is particularly prevalent in the field of information elicitation, where one wishes to design contracts to incentivize self-minded agents to provide honest information. We devise a simple linear program to decide whether a polyhedral cell complex can be described as a power diagram. For positive instances, a representation of the cell complex as a power diagram is returned. Further, we discuss applications to property elicitation, peer prediction, and mechanism design, where this question arises. Our model can efficiently decide the question for complexes of Rd or of a convex subset thereof. The approach is based on the use of an alternative representation of power diagrams and invariance of a power diagram under uniform scaling of the parameters in this representation.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10957-018-1442-y", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.6624045", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1044187", 
        "issn": [
          "0022-3239", 
          "1573-2878"
        ], 
        "name": "Journal of Optimization Theory and Applications", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "181"
      }
    ], 
    "name": "Power Diagram Detection with Applications to Information Elicitation", 
    "pagination": "184-196", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "8c00e0434c264c951969f307d79ba9655a6b2443a5fb3bb91e831e9733608822"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10957-018-1442-y"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1110128616"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10957-018-1442-y", 
      "https://app.dimensions.ai/details/publication/pub.1110128616"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T11:19", 
    "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/0000000354_0000000354/records_11713_00000002.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs10957-018-1442-y"
  }
]
 

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/s10957-018-1442-y'

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/s10957-018-1442-y'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10957-018-1442-y'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10957-018-1442-y'


 

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

147 TRIPLES      21 PREDICATES      49 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10957-018-1442-y schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author Nb4e10b89a5f0429994b2a1a962ebabf1
4 schema:citation sg:pub.10.1007/978-3-319-13129-0_29
5 sg:pub.10.1007/bf00181470
6 sg:pub.10.1007/bf02187870
7 sg:pub.10.1007/pl00009187
8 sg:pub.10.1007/pl00009434
9 sg:pub.10.1007/s00283-014-9448-2
10 sg:pub.10.1007/s10852-014-9263-y
11 sg:pub.10.1023/a:1008663629662
12 https://doi.org/10.1016/j.ejor.2017.04.054
13 https://doi.org/10.1016/s0747-7171(87)80003-2
14 https://doi.org/10.1080/01621459.1971.10482346
15 https://doi.org/10.1080/10556789408805554
16 https://doi.org/10.1137/0216006
17 https://doi.org/10.1137/110832707
18 https://doi.org/10.1142/8685
19 https://doi.org/10.1145/1064009.1064040
20 https://doi.org/10.1145/1386790.1386813
21 https://doi.org/10.1145/1566374.1566391
22 https://doi.org/10.1145/3070903
23 https://doi.org/10.1198/016214505000000907
24 https://doi.org/10.1287/ijoc.4.4.369
25 https://doi.org/10.1287/mnsc.1050.0379
26 schema:datePublished 2019-04
27 schema:datePublishedReg 2019-04-01
28 schema:description Power diagrams, a type of weighted Voronoi diagram, have many applications throughout operations research. We study the problem of power diagram detection: determining whether a given finite partition of Rd takes the form of a power diagram. This detection problem is particularly prevalent in the field of information elicitation, where one wishes to design contracts to incentivize self-minded agents to provide honest information. We devise a simple linear program to decide whether a polyhedral cell complex can be described as a power diagram. For positive instances, a representation of the cell complex as a power diagram is returned. Further, we discuss applications to property elicitation, peer prediction, and mechanism design, where this question arises. Our model can efficiently decide the question for complexes of Rd or of a convex subset thereof. The approach is based on the use of an alternative representation of power diagrams and invariance of a power diagram under uniform scaling of the parameters in this representation.
29 schema:genre research_article
30 schema:inLanguage en
31 schema:isAccessibleForFree true
32 schema:isPartOf N8557a74f2b8741ec98f52b83a102258a
33 Nc69545e0037c43a79e363ce35cf05655
34 sg:journal.1044187
35 schema:name Power Diagram Detection with Applications to Information Elicitation
36 schema:pagination 184-196
37 schema:productId N14c497c1ef624e60886babfea598c420
38 N5da5316523e3486fb1f8757d33968c56
39 Nf1c7cc4262084a4aacc435e02769cada
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1110128616
41 https://doi.org/10.1007/s10957-018-1442-y
42 schema:sdDatePublished 2019-04-11T11:19
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher N92f6a4e7e19b4bcc8d9fe82e5acd89c5
45 schema:url https://link.springer.com/10.1007%2Fs10957-018-1442-y
46 sgo:license sg:explorer/license/
47 sgo:sdDataset articles
48 rdf:type schema:ScholarlyArticle
49 N0fc38279830544189370b0f430f33846 rdf:first sg:person.012216112757.52
50 rdf:rest rdf:nil
51 N14c497c1ef624e60886babfea598c420 schema:name readcube_id
52 schema:value 8c00e0434c264c951969f307d79ba9655a6b2443a5fb3bb91e831e9733608822
53 rdf:type schema:PropertyValue
54 N5da5316523e3486fb1f8757d33968c56 schema:name dimensions_id
55 schema:value pub.1110128616
56 rdf:type schema:PropertyValue
57 N8557a74f2b8741ec98f52b83a102258a schema:issueNumber 1
58 rdf:type schema:PublicationIssue
59 N92f6a4e7e19b4bcc8d9fe82e5acd89c5 schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 Nb4e10b89a5f0429994b2a1a962ebabf1 rdf:first sg:person.013112364415.74
62 rdf:rest N0fc38279830544189370b0f430f33846
63 Nc69545e0037c43a79e363ce35cf05655 schema:volumeNumber 181
64 rdf:type schema:PublicationVolume
65 Nf1c7cc4262084a4aacc435e02769cada schema:name doi
66 schema:value 10.1007/s10957-018-1442-y
67 rdf:type schema:PropertyValue
68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
69 schema:name Information and Computing Sciences
70 rdf:type schema:DefinedTerm
71 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
72 schema:name Computer Software
73 rdf:type schema:DefinedTerm
74 sg:grant.6624045 http://pending.schema.org/fundedItem sg:pub.10.1007/s10957-018-1442-y
75 rdf:type schema:MonetaryGrant
76 sg:journal.1044187 schema:issn 0022-3239
77 1573-2878
78 schema:name Journal of Optimization Theory and Applications
79 rdf:type schema:Periodical
80 sg:person.012216112757.52 schema:affiliation https://www.grid.ac/institutes/grid.266190.a
81 schema:familyName Frongillo
82 schema:givenName Rafael M.
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012216112757.52
84 rdf:type schema:Person
85 sg:person.013112364415.74 schema:affiliation https://www.grid.ac/institutes/grid.241116.1
86 schema:familyName Borgwardt
87 schema:givenName Steffen
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013112364415.74
89 rdf:type schema:Person
90 sg:pub.10.1007/978-3-319-13129-0_29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019882588
91 https://doi.org/10.1007/978-3-319-13129-0_29
92 rdf:type schema:CreativeWork
93 sg:pub.10.1007/bf00181470 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031969818
94 https://doi.org/10.1007/bf00181470
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/bf02187870 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003005419
97 https://doi.org/10.1007/bf02187870
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/pl00009187 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051809298
100 https://doi.org/10.1007/pl00009187
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/pl00009434 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036408413
103 https://doi.org/10.1007/pl00009434
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/s00283-014-9448-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019617669
106 https://doi.org/10.1007/s00283-014-9448-2
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/s10852-014-9263-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1025300262
109 https://doi.org/10.1007/s10852-014-9263-y
110 rdf:type schema:CreativeWork
111 sg:pub.10.1023/a:1008663629662 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038382810
112 https://doi.org/10.1023/a:1008663629662
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/j.ejor.2017.04.054 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085079485
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1016/s0747-7171(87)80003-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001880026
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1080/01621459.1971.10482346 schema:sameAs https://app.dimensions.ai/details/publication/pub.1058300819
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1080/10556789408805554 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002516943
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1137/0216006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841952
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1137/110832707 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062864878
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1142/8685 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098932075
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1145/1064009.1064040 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021789994
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1145/1386790.1386813 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011959116
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1145/1566374.1566391 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023603973
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1145/3070903 schema:sameAs https://app.dimensions.ai/details/publication/pub.1090927607
135 rdf:type schema:CreativeWork
136 https://doi.org/10.1198/016214505000000907 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064198422
137 rdf:type schema:CreativeWork
138 https://doi.org/10.1287/ijoc.4.4.369 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064707425
139 rdf:type schema:CreativeWork
140 https://doi.org/10.1287/mnsc.1050.0379 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064714410
141 rdf:type schema:CreativeWork
142 https://www.grid.ac/institutes/grid.241116.1 schema:alternateName University of Colorado Denver
143 schema:name University of Colorado Denver, Denver, CO, USA
144 rdf:type schema:Organization
145 https://www.grid.ac/institutes/grid.266190.a schema:alternateName University of Colorado Boulder
146 schema:name University of Colorado Boulder, Boulder, CO, USA
147 rdf:type schema:Organization
 




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


...