12 Search Results for "Piliouras, Georgios"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.93
Analyzing the Economic Impact of Decentralization on Users

Authors: Amit Levy, S. Matthew Weinberg, and Chenghan Zhou

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We model the ultimate price paid by users of a decentralized ledger as resulting from a two-stage game where Miners (/Proposers/etc.) first purchase blockspace via a Tullock contest, and then price that space to users. When analyzing our distributed ledger model, we find: - A characterization of all possible pure equilibria (although pure equilibria are not guaranteed to exist). - A natural sufficient condition, implied by Regularity (à la [Myerson, 1981]), for existence of a "market-clearing" pure equilibrium where Miners choose to sell all space allocated by the Distributed Ledger Protocol, and that this equilibrium is unique. - The market share of the largest miner is the relevant "measure of decentralization" to determine whether a market-clearing pure equilibrium exists. - Block rewards do not impact users' prices at equilibrium, when pure equilibria exist. But, higher block rewards can cause pure equilibria to exist. We also discuss aspects of our model and how they relate to blockchains deployed in practice. For example, only "patient" users (who are happy for their transactions to enter the blockchain under any miner) would enjoy the conclusions highlighted by our model, whereas "impatient" users (who are interested only for their transaction to be included in the very next block) still face monopoly pricing.
Cite as

Amit Levy, S. Matthew Weinberg, and Chenghan Zhou. Analyzing the Economic Impact of Decentralization on Users. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 93:1-93:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{levy_et_al:LIPIcs.ITCS.2026.93,
  author =	{Levy, Amit and Weinberg, S. Matthew and Zhou, Chenghan},
  title =	{{Analyzing the Economic Impact of Decentralization on Users}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{93:1--93:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.93},
  URN =		{urn:nbn:de:0030-drops-253805},
  doi =		{10.4230/LIPIcs.ITCS.2026.93},
  annote =	{Keywords: Blockchain, Cryptocurrency, Blockspace Markets, Decentralization, Distributed Ledgers, Equilibrium Analysis, Tullock Contests}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.21
Pool Formation in Oceanic Games: Shapley Value and Proportional Sharing

Authors: Aggelos Kiayias, Elias Koutsoupias, Evangelos Markakis, and Panagiotis Tsamopoulos

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
We study a game-theoretic model for pool formation in Proof of Stake blockchain protocols. In such systems, stakeholders can form pools as a means of obtaining regular rewards from participation in ledger maintenance, with the power of each pool being dependent on its collective stake. The question we are interested in is the design of mechanisms, i.e., "reward sharing schemes," that suitably split rewards among pool members and achieve favorable properties in the resulting pool configuration. With this in mind, we initiate a non-cooperative game-theoretic analysis of the well known Shapley value scheme from cooperative game theory into the context of blockchains. In particular, we focus on the oceanic model of games, proposed by Milnor and Shapley (1978), which is suitable for populations where a small set of large players coexists with a big mass of rather small, negligible players. This provides an appropriate level of abstraction for pool formation processes that occur among the stakeholders of a blockchain. We provide comparisons between the Shapley mechanism and the more standard proportional scheme, in terms of attained decentralization, via a Price of Stability analysis and in terms of susceptibility to Sybil attacks, i.e., the strategic splitting of a players' stake with the intention of participating in multiple pools for increased profit. Interestingly, while the widely deployed proportional scheme appears to have certain advantages, the Shapley value scheme, which rewards higher the most pivotal players, emerges as a competitive alternative, by being able to bypass some of the downsides of proportional sharing in terms of Sybil attack susceptibility, while also not being far from optimal guarantees w.r.t. decentralization. Finally, we also complement our study with some variations of proportional sharing, where the profit is split in proportion to a superadditive or a subadditive function of the stake, showing that our results for the Shapley value scheme are maintained in comparison to these functions as well.
Cite as

Aggelos Kiayias, Elias Koutsoupias, Evangelos Markakis, and Panagiotis Tsamopoulos. Pool Formation in Oceanic Games: Shapley Value and Proportional Sharing. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kiayias_et_al:LIPIcs.AFT.2025.21,
  author =	{Kiayias, Aggelos and Koutsoupias, Elias and Markakis, Evangelos and Tsamopoulos, Panagiotis},
  title =	{{Pool Formation in Oceanic Games: Shapley Value and Proportional Sharing}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{21:1--21:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.21},
  URN =		{urn:nbn:de:0030-drops-247409},
  doi =		{10.4230/LIPIcs.AFT.2025.21},
  annote =	{Keywords: Shapley value, Nash equilibria, Price of Stability, Reward sharing schemes, Proof of Stake blockchains}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.24
Multidimensional Blockchain Fees Are (Essentially) Optimal

Authors: Guillermo Angeris, Theo Diamandis, and Ciamac Moallemi

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
In this paper we show that, using only mild assumptions, dynamic multidimensional blockchain fee markets have strong performance guarantees, even against worst-case adversaries. In particular, we show that the average welfare gap between the following two scenarios is at most O(1/√T), where T is the length of the time horizon considered. In the first scenario, the designer knows all future actions by users and is allowed to fix the optimal prices of resources ahead of time, based on the designer’s oracular knowledge of those actions. In the second, the prices are updated by a very simple algorithm that does not have this oracular knowledge, special cases of which are EIP-4844 and EIP-1559, both fee mechanisms used by the Ethereum blockchain. Roughly speaking, this means that, on average, over a reasonable timescale, there is no difference in welfare between "correctly" fixing the prices, with oracular knowledge of the future, when compared to the proposed algorithm. We show a matching lower bound of Ω(1/√T) for any implementable algorithm and also separately consider the case where the adversary is known to be stochastic.
Cite as

Guillermo Angeris, Theo Diamandis, and Ciamac Moallemi. Multidimensional Blockchain Fees Are (Essentially) Optimal. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{angeris_et_al:LIPIcs.AFT.2025.24,
  author =	{Angeris, Guillermo and Diamandis, Theo and Moallemi, Ciamac},
  title =	{{Multidimensional Blockchain Fees Are (Essentially) Optimal}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.24},
  URN =		{urn:nbn:de:0030-drops-247433},
  doi =		{10.4230/LIPIcs.AFT.2025.24},
  annote =	{Keywords: Blockchains, transaction fees, online optimization, convex optimization}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.23
Transaction Fee Market Design for Parallel Execution

Authors: Bahar Acilan, Andrei Constantinescu, Lioba Heimbach, and Roger Wattenhofer

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
Given the low throughput of blockchains like Bitcoin and Ethereum, scalability - the ability to process an increasing number of transactions - has become a central focus of blockchain research. One promising approach is the parallelization of transaction execution across multiple threads. However, achieving efficient parallelization requires a redesign of the incentive structure within the fee market. Currently, the fee market does not differentiate between transactions that access multiple high-demand storage keys (i.e., unique identifiers for individual data entries) versus a single low-demand one, as long as they require the same computational effort. Addressing this discrepancy is crucial for enabling more effective parallel execution. In this work, we aim to bridge the gap between the current fee market and the need for parallel execution by exploring alternative fee market designs. To this end, we propose a framework consisting of two key components: a Gas Computation Mechanism (GCM), which quantifies the load a transaction places on the network in terms of parallelization and computation, measured in units of gas, and a Transaction Fee Mechanism (TFM), which assigns a price to each unit of gas. We additionally introduce a set of desirable properties for a GCM, propose several candidate mechanisms, and evaluate them against these criteria. Our analysis highlights two strong candidates: the weighted area GCM, which integrates smoothly with existing TFMs such as EIP‑1559 and satisfies a broad subset of the outlined properties, and the time-proportional makespan GCM, which assigns gas costs based on the context of the entire block’s schedule and, through this dependence on the overall execution outcome, captures the dynamics of parallel execution more accurately.
Cite as

Bahar Acilan, Andrei Constantinescu, Lioba Heimbach, and Roger Wattenhofer. Transaction Fee Market Design for Parallel Execution. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 23:1-23:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{acilan_et_al:LIPIcs.AFT.2025.23,
  author =	{Acilan, Bahar and Constantinescu, Andrei and Heimbach, Lioba and Wattenhofer, Roger},
  title =	{{Transaction Fee Market Design for Parallel Execution}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{23:1--23:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.23},
  URN =		{urn:nbn:de:0030-drops-247426},
  doi =		{10.4230/LIPIcs.AFT.2025.23},
  annote =	{Keywords: blockchain, transaction fee mechanism, parallel execution}
}
Document
Extended Abstract
DOI: 10.4230/LIPIcs.ITCS.2025.80
Diversity in Evolutionary Dynamics (Extended Abstract)

Authors: Yuval Rabani, Leonard J. Schulman, and Alistair Sinclair

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
Since this paper is under journal submission, we publish only an extended abstract here. A full version can be found at https://arxiv.org/abs/2406.03938.
Cite as

Yuval Rabani, Leonard J. Schulman, and Alistair Sinclair. Diversity in Evolutionary Dynamics (Extended Abstract). In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 80:1-80:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rabani_et_al:LIPIcs.ITCS.2025.80,
  author =	{Rabani, Yuval and Schulman, Leonard J. and Sinclair, Alistair},
  title =	{{Diversity in Evolutionary Dynamics}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{80:1--80:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.80},
  URN =		{urn:nbn:de:0030-drops-227086},
  doi =		{10.4230/LIPIcs.ITCS.2025.80},
  annote =	{Keywords: Mathematical models of evolution, replicator dynamics, weak selection, genetic diversity, game theory, dynamical systems}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.10
Algorithmic Collusion Without Threats

Authors: Eshwar Ram Arunachaleswaran, Natalie Collina, Sampath Kannan, Aaron Roth, and Juba Ziani

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
There has been substantial recent concern that automated pricing algorithms might learn to "collude." Supra-competitive prices can emerge as a Nash equilibrium of repeated pricing games, in which sellers play strategies which threaten to punish their competitors if they ever "defect" from a set of supra-competitive prices, and these strategies can be automatically learned. But threats are anti-competitive on their face. In fact, a standard economic intuition is that supra-competitive prices emerge from either the use of threats, or a failure of one party to correctly optimize their payoff. Is this intuition correct? Would explicitly preventing threats in algorithmic decision-making prevent supra-competitive prices when sellers are optimizing for their own revenue? No. We show that supra-competitive prices can robustly emerge even when both players are using algorithms which do not explicitly encode threats, and which optimize for their own revenue. Since deploying an algorithm is a form of commitment, we study sequential Bertrand pricing games (and a continuous variant) in which a first mover deploys an algorithm and then a second mover optimizes within the resulting environment. We show that if the first mover deploys any algorithm with a no-regret guarantee, and then the second mover even approximately optimizes within this now static environment, monopoly-like prices arise. The result holds for any no-regret learning algorithm deployed by the first mover and for any pricing policy of the second mover that obtains them profit at least as high as a random pricing would - and hence the result applies even when the second mover is optimizing only within a space of non-responsive pricing distributions which are incapable of encoding threats. In fact, there exists a set of strategies, neither of which explicitly encode threats that form a Nash equilibrium of the simultaneous pricing game in algorithm space, and lead to near monopoly prices. This suggests that the definition of "algorithmic collusion" may need to be expanded, to include strategies without explicitly encoded threats.
Cite as

Eshwar Ram Arunachaleswaran, Natalie Collina, Sampath Kannan, Aaron Roth, and Juba Ziani. Algorithmic Collusion Without Threats. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{arunachaleswaran_et_al:LIPIcs.ITCS.2025.10,
  author =	{Arunachaleswaran, Eshwar Ram and Collina, Natalie and Kannan, Sampath and Roth, Aaron and Ziani, Juba},
  title =	{{Algorithmic Collusion Without Threats}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.10},
  URN =		{urn:nbn:de:0030-drops-226386},
  doi =		{10.4230/LIPIcs.ITCS.2025.10},
  annote =	{Keywords: Algorithmic Game Theory, Algorithmic Collusion, No-Regret Dynamics}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.65
On the Approximability of Multistage Min-Sum Set Cover

Authors: Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, and Stratis Skoulakis

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We investigate the polynomial-time approximability of the multistage version of Min-Sum Set Cover (Mult-MSSC), a natural and intriguing generalization of the classical List Update problem. In Mult-MSSC, we maintain a sequence of permutations (π⁰, π¹, …, π^T) on n elements, based on a sequence of requests ℛ = (R¹, …, R^T). We aim to minimize the total cost of updating π^{t-1} to π^{t}, quantified by the Kendall tau distance d_{KT}(π^{t-1}, π^t), plus the total cost of covering each request R^t with the current permutation π^t, quantified by the position of the first element of R^t in π^t. Using a reduction from Set Cover, we show that Mult-MSSC does not admit an O(1)-approximation, unless P = NP, and that any o(log n) (resp. o(r)) approximation to Mult-MSSC implies a sublogarithmic (resp. o(r)) approximation to Set Cover (resp. where each element appears at most r times). Our main technical contribution is to show that Mult-MSSC can be approximated in polynomial-time within a factor of O(log² n) in general instances, by randomized rounding, and within a factor of O(r²), if all requests have cardinality at most r, by deterministic rounding.
Cite as

Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, and Stratis Skoulakis. On the Approximability of Multistage Min-Sum Set Cover. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 65:1-65:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fotakis_et_al:LIPIcs.ICALP.2021.65,
  author =	{Fotakis, Dimitris and Kostopanagiotis, Panagiotis and Nakos, Vasileios and Piliouras, Georgios and Skoulakis, Stratis},
  title =	{{On the Approximability of Multistage Min-Sum Set Cover}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{65:1--65:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.65},
  URN =		{urn:nbn:de:0030-drops-141341},
  doi =		{10.4230/LIPIcs.ICALP.2021.65},
  annote =	{Keywords: Approximation Algorithms, Multistage Min-Sum Set Cover, Multistage Optimization Problems}
}
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.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/LIPIcs.ITCS.2018.59
Learning Dynamics and the Co-Evolution of Competing Sexual Species

Authors: Georgios Piliouras and Leonard J. Schulman

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
We analyze a stylized model of co-evolution between any two purely competing species (e.g., host and parasite), both sexually reproducing. Similarly to a recent model [Livnat et al. FOCS'14] the fitness of an individual depends on whether the truth assignments on n variables that reproduce through recombination satisfy a particular Boolean function. Whereas in the original model a satisfying assignment always confers a small evolutionary advantage, in our model the two species are in an evolutionary race with the parasite enjoying the advantage if the value of its Boolean function matches its host, and the host wishing to mismatch its parasite. Surprisingly, this model makes a simple and robust behavioral prediction. The typical system behavior is periodic. These cycles stay bounded away from the boundary and thus, learning-dynamics competition between sexual species can provide an explanation for genetic diversity. This explanation is due solely to the natural selection process. No mutations, environmental changes, etc., need be invoked. The game played at the gene level may have many Nash equilibria with widely diverse fitness levels. Nevertheless, sexual evolution leads to gene coordination that implements an optimal strategy, i.e., an optimal population mixture, at the species level. Namely, the play of the many "selfish genes" implements a time-averaged correlated equilibrium where the average fitness of each species is exactly equal to its value in the two species zero-sum competition. Our analysis combines tools from game theory, dynamical systems and Boolean functions to establish a novel class of conservative dynamical systems.
Cite as

Georgios Piliouras and Leonard J. Schulman. Learning Dynamics and the Co-Evolution of Competing Sexual Species. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 59:1-59:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{piliouras_et_al:LIPIcs.ITCS.2018.59,
  author =	{Piliouras, Georgios and Schulman, Leonard J.},
  title =	{{Learning Dynamics and the Co-Evolution of Competing Sexual Species}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{59:1--59:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.59},
  URN =		{urn:nbn:de:0030-drops-83637},
  doi =		{10.4230/LIPIcs.ITCS.2018.59},
  annote =	{Keywords: Dynamical Systems, Potential Game, Team Zero-Sum Game, Boolean Functions, Replicator Dynamics}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.2
Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions

Authors: Ioannis Panageas and Georgios Piliouras

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
Given a twice continuously differentiable cost function f, we prove that the set of initial conditions so that gradient descent converges to saddle points where \nabla^2 f has at least one strictly negative eigenvalue, has (Lebesgue) measure zero, even for cost functions f with non-isolated critical points, answering an open question in [Lee, Simchowitz, Jordan, Recht, COLT 2016]. Moreover, this result extends to forward-invariant convex subspaces, allowing for weak (non-globally Lipschitz) smoothness assumptions. Finally, we produce an upper bound on the allowable step-size.
Cite as

Ioannis Panageas and Georgios Piliouras. Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{panageas_et_al:LIPIcs.ITCS.2017.2,
  author =	{Panageas, Ioannis and Piliouras, Georgios},
  title =	{{Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.2},
  URN =		{urn:nbn:de:0030-drops-81640},
  doi =		{10.4230/LIPIcs.ITCS.2017.2},
  annote =	{Keywords: Gradient Descent, Center-stable manifold, Saddle points, Hessian}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.16
Mutation, Sexual Reproduction and Survival in Dynamic Environments

Authors: Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
A new approach to understanding evolution [Valiant, JACM 2009], namely viewing it through the lens of computation, has already started yielding new insights, e.g., natural selection under sexual reproduction can be interpreted as the Multiplicative Weight Update (MWU) Algorithm in coordination games played among genes [Chastain, Livnat, Papadimitriou, Vazirani, PNAS 2014]. Using this machinery, we study the role of mutation in changing environments in the presence of sexual reproduction. Following [Wolf, Vazirani, Arkin, J. Theor. Biology], we model changing environments via a Markov chain, with the states representing environments, each with its own fitness matrix. In this setting, we show that in the absence of mutation, the population goes extinct, but in the presence of mutation, the population survives with positive probability. On the way to proving the above theorem, we need to establish some facts about dynamics in games. We provide the first, to our knowledge, polynomial convergence bound for noisy MWU in a coordination game. Finally, we also show that in static environments, sexual evolution with mutation converges, for any level of mutation.
Cite as

Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani. Mutation, Sexual Reproduction and Survival in Dynamic Environments. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 16:1-16:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{mehta_et_al:LIPIcs.ITCS.2017.16,
  author =	{Mehta, Ruta and Panageas, Ioannis and Piliouras, Georgios and Tetali, Prasad and Vazirani, Vijay V.},
  title =	{{Mutation, Sexual Reproduction and Survival in Dynamic Environments}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{16:1--16:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.16},
  URN =		{urn:nbn:de:0030-drops-81655},
  doi =		{10.4230/LIPIcs.ITCS.2017.16},
  annote =	{Keywords: Evolution, Non-linear dynamics, Mutation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.65
The Computational Complexity of Genetic Diversity

Authors: Ruta Mehta, Ioannis Panageas, Georgios Piliouras, and Sadra Yazdanbod

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
A key question in biological systems is whether genetic diversity persists in the long run under evolutionary competition, or whether a single dominant genotype emerges. Classic work by [Kalmus, J. og Genetics, 1945] has established that even in simple diploid species (species with chromosome pairs) diversity can be guaranteed as long as the heterozygous (having different alleles for a gene on two chromosomes) individuals enjoy a selective advantage. Despite the classic nature of the problem, as we move towards increasingly polymorphic traits (e.g., human blood types) predicting diversity (and its implications) is still not fully understood. Our key contribution is to establish complexity theoretic hardness results implying that even in the textbook case of single locus (gene) diploid models, predicting whether diversity survives or not given its fitness landscape is algorithmically intractable. Our hardness results are structurally robust along several dimensions, e.g., choice of parameter distribution, different definitions of stability/persistence, restriction to typical subclasses of fitness landscapes. Technically, our results exploit connections between game theory, nonlinear dynamical systems, and complexity theory and establish hardness results for predicting the evolution of a deterministic variant of the well known multiplicative weights update algorithm in symmetric coordination games; finding one Nash equilibrium is easy in these games. In the process we characterize stable fixed points of these dynamics using the notions of Nash equilibrium and negative semidefiniteness. This as well as hardness results for decision problems in coordination games may be of independent interest. Finally, we complement our results by establishing that under randomly chosen fitness landscapes diversity survives with significant probability. The full version of this paper is available at http://arxiv.org/abs/1411.6322.
Cite as

Ruta Mehta, Ioannis Panageas, Georgios Piliouras, and Sadra Yazdanbod. The Computational Complexity of Genetic Diversity. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 65:1-65:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{mehta_et_al:LIPIcs.ESA.2016.65,
  author =	{Mehta, Ruta and Panageas, Ioannis and Piliouras, Georgios and Yazdanbod, Sadra},
  title =	{{The Computational Complexity of Genetic Diversity}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{65:1--65:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.65},
  URN =		{urn:nbn:de:0030-drops-64073},
  doi =		{10.4230/LIPIcs.ESA.2016.65},
  annote =	{Keywords: Dynamical Systems, Stability, Complexity, Optimization, Equilibrium}
}
  • Refine by Type
  • 12 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 5 2025
  • 1 2021
  • 1 2019
  • 1 2018
  • Show More...

  • Refine by Author
  • 6 Piliouras, Georgios
  • 3 Panageas, Ioannis
  • 2 Koutsoupias, Elias
  • 2 Mehta, Ruta
  • 2 Schulman, Leonard J.
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Algorithmic game theory
  • 2 Theory of computation → Algorithmic game theory and mechanism design
  • 1 Applied computing → Digital cash
  • 1 Applied computing → Economics
  • 1 Applied computing → Population genetics
  • Show More...

  • Refine by Keyword
  • 2 Dynamical Systems
  • 1 Algorithmic Collusion
  • 1 Algorithmic Game Theory
  • 1 Approximation Algorithms
  • 1 Blockchain
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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