License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.45
URN: urn:nbn:de:0030-drops-74910
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7491/
Go to the corresponding LIPIcs Volume Portal

Bodwin, Greg

Testing Core Membership in Public Goods Economies

pdf-format:
LIPIcs-ICALP-2017-45.pdf (0.5 MB)

Abstract

This paper develops a recent line of economic theory seeking to understand public goods economies using methods of topological analysis. Our first main result is a very clean characterization of the economy's core (the standard solution concept in public goods). Specifically, we prove that a point is in the core iff it is Pareto efficient, individually rational, and the set of points it dominates is path connected.

While this structural theorem has a few interesting implications in economic theory, the main focus of the second part of this paper is on a particular algorithmic application that demonstrates its utility. Since the 1960s, economists have looked for an efficient computational process that decides whether or not a given point is in the core. All known algorithms so far run in exponential time (except in some artificially restricted settings). By heavily exploiting our new structure, we propose a new algorithm for testing core membership whose computational bottleneck is the solution of O(n) convex optimization problems on the utility function governing the economy. It is fairly natural to assume that convex optimization should be feasible, as it is needed even for very basic economic computational tasks such as testing Pareto efficiency. Nevertheless, even without this assumption, our work implies for the first time that core membership can be efficiently tested on (e.g.) utility functions that admit ``nice'' analytic expressions, or that appropriately defined epsilon-approximate versions of the problem are tractable (by using modern black-box epsilon-approximate convex optimization algorithms).

BibTeX - Entry

@InProceedings{bodwin:LIPIcs:2017:7491,
  author =	{Greg Bodwin},
  title =	{{Testing Core Membership in Public Goods Economies}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7491},
  URN =		{urn:nbn:de:0030-drops-74910},
  doi =		{10.4230/LIPIcs.ICALP.2017.45},
  annote =	{Keywords: Algorithmic Game Theory, Economics, Algorithms, Public Goods, Coalitional Stability}
}

Keywords: Algorithmic Game Theory, Economics, Algorithms, Public Goods, Coalitional Stability
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI