Power Diagram Detection with Applications to Information Elicitation

Steffen Borgwardt () and Rafael M. Frongillo ()
Additional contact information
Steffen Borgwardt: University of Colorado Denver
Rafael M. Frongillo: University of Colorado Boulder

Journal of Optimization Theory and Applications, 2019, vol. 181, issue 1, No 9, 184-196

Abstract: 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 $${\mathbb {R}}^d$$ R d 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 $${\mathbb {R}}^d$$ R d 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.

Keywords: Power diagram; Information elicitation; Linear programming; 90C05; 90C90; 91B06; 62C05 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-018-1442-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:181:y:2019:i:1:d:10.1007_s10957-018-1442-y

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-018-1442-y

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().