2 Search Results for "Zhou, Yuren"

Document
DOI: 10.4230/LIPIcs.STACS.2019.31
Wealth Inequality and the Price of Anarchy

Authors: Kurtuluş Gemici, Elias Koutsoupias, Barnabé Monnot, Christos H. Papadimitriou, and Georgios Piliouras

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
The price of anarchy quantifies the degradation of social welfare in games due to the lack of a centralized authority that can enforce the optimal outcome. It is known that, in certain games, such effects can be ameliorated via tolls or taxes. This leads to a natural, but largely unexplored, question: what is the effect of such transfers on social inequality? We study this question in nonatomic congestion games, arguably one of the most thoroughly studied settings from the perspective of the price of anarchy. We introduce a new model that incorporates the income distribution of the population and captures the income elasticity of travel time (i.e., how does loss of time translate to lost income). This allows us to argue about the equality of wealth distribution both before and after employing a mechanism. We establish that, under reasonable assumptions, tolls always increase inequality in symmetric congestion games under any reasonable metric of inequality such as the Gini index. We introduce the inequity index, a novel measure for quantifying the magnitude of these forces towards a more unbalanced wealth distribution and show it has good normative properties (robustness to scaling of income, no-regret learning). We analyze inequity both in theoretical settings (Pigou’s network under various wealth distributions) as well as experimental ones (based on a large scale field experiment in Singapore). Finally, we provide an algorithm for computing optimal tolls for any point of the trade-off of relative importance of efficiency and equality. We conclude with a discussion of our findings in the context of theories of justice as developed in contemporary social sciences and present several directions for future research.
Cite as

Kurtuluş Gemici, Elias Koutsoupias, Barnabé Monnot, Christos H. Papadimitriou, and Georgios Piliouras. Wealth Inequality and the Price of Anarchy. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gemici_et_al:LIPIcs.STACS.2019.31,
  author =	{Gemici, Kurtulu\c{s} and Koutsoupias, Elias and Monnot, Barnab\'{e} and Papadimitriou, Christos H. and Piliouras, Georgios},
  title =	{{Wealth Inequality and the Price of Anarchy}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.31},
  URN =		{urn:nbn:de:0030-drops-102707},
  doi =		{10.4230/LIPIcs.STACS.2019.31},
  annote =	{Keywords: congestion games, inequality}
}
Document
DOI: 10.4230/DagSemProc.08051.3
A Comparison of GAs Penalizing Infeasible Solutions and Repairing Infeasible Solutions on the 0-1 Knapsack Problem

Authors: Jun He, Yuren Zhou, and Xin Yao

Published in: Dagstuhl Seminar Proceedings, Volume 8051, Theory of Evolutionary Algorithms (2008)

Abstract
Constraints exist in almost every optimization problem. Different constraint handling techniques have been incorporated with genetic algorithms (GAs), however most of current studies are based on computer experiments. An example is Michalewicz's comparison among GAs using different constraint handling techniques on the 0-1 knapsack problem. The following phenomena are observed in experiments: 1) the penalty method needs more generations to find a feasible solution to the restrictive capacity knapsack than the repair method; 2) the penalty method can find better solutions to the average capacity knapsack. Such observations need a theoretical explanation. This paper aims at providing a theoretical analysis of Michalewicz's experiments. The main result of the paper is that GAs using the repair method are more efficient than GAs using the penalty method on both restrictive capacity and average capacity knapsack problems. This result of the average capacity is a little different from Michalewicz's experimental results. So a supplemental experiment is implemented to support the theoretical claim. The results confirm the general principle pointed out by Coello: a better constraint-handling approach should tend to exploit specific domain knowledge.
Cite as

Jun He, Yuren Zhou, and Xin Yao. A Comparison of GAs Penalizing Infeasible Solutions and Repairing Infeasible Solutions on the 0-1 Knapsack Problem. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 8051, pp. 1-39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{he_et_al:DagSemProc.08051.3,
  author =	{He, Jun and Zhou, Yuren and Yao, Xin},
  title =	{{A Comparison of GAs Penalizing Infeasible Solutions and Repairing Infeasible Solutions on the 0-1 Knapsack Problem}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--39},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8051},
  editor =	{Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08051.3},
  URN =		{urn:nbn:de:0030-drops-14822},
  doi =		{10.4230/DagSemProc.08051.3},
  annote =	{Keywords: Genetic Algorithms, Constrained Optimization, Knapsack Problem, Computation Time, Performance Analysis}
}
  • Refine by Author
  • 1 Gemici, Kurtuluş
  • 1 He, Jun
  • 1 Koutsoupias, Elias
  • 1 Monnot, Barnabé
  • 1 Papadimitriou, Christos H.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Algorithmic game theory

  • Refine by Keyword
  • 1 Computation Time
  • 1 Constrained Optimization
  • 1 Genetic Algorithms
  • 1 Knapsack Problem
  • 1 Performance Analysis
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact