Search Results

Documents authored by Markakis, Evangelos

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/DagRep.14.9.145
Fair Division: Algorithms, Solution Concepts, and Applications (Dagstuhl Seminar 24401)

Authors: Evangelos Markakis, Ruta Mehta, and Yair Zick

Published in: Dagstuhl Reports, Volume 14, Issue 9 (2025)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 24401 "Fair Division: Algorithms, Solution Concepts, and Applications". The main goal of the seminar was to bring together leading scientists in the field of fair division so as to discuss current challenges and research directions. We summarize organizational aspects of the seminar, the talk abstracts, and the problems that were discussed in the open problem sessions.
Cite as

Evangelos Markakis, Ruta Mehta, and Yair Zick. Fair Division: Algorithms, Solution Concepts, and Applications (Dagstuhl Seminar 24401). In Dagstuhl Reports, Volume 14, Issue 9, pp. 145-166, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{markakis_et_al:DagRep.14.9.145,
  author =	{Markakis, Evangelos and Mehta, Ruta and Zick, Yair},
  title =	{{Fair Division: Algorithms, Solution Concepts, and Applications (Dagstuhl Seminar 24401)}},
  pages =	{145--166},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{14},
  number =	{9},
  editor =	{Markakis, Evangelos and Mehta, Ruta and Zick, Yair},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.9.145},
  URN =		{urn:nbn:de:0030-drops-226049},
  doi =		{10.4230/DagRep.14.9.145},
  annote =	{Keywords: algorithm design, Algorithmic game theory, cake cutting, envy-freeness, fair division}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.26
Achieving Envy-Freeness Through Items Sale

Authors: Vittorio Bilò, Evangelos Markakis, and Cosimo Vinci

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We consider a fair division setting of allocating indivisible items to a set of agents. In order to cope with the well-known impossibility results related to the non-existence of envy-free allocations, we allow the option of selling some of the items so as to compensate envious agents with monetary rewards. In fact, this approach is not new in practice, as it is applied in some countries in inheritance or divorce cases. A drawback of this approach is that it may create a value loss, since the market value derived by selling an item can be less than the value perceived by the agents. Therefore, given the market values of all items, a natural goal is to identify which items to sell so as to arrive at an envy-free allocation, while at the same time maximizing the overall social welfare. Our work is focused on the algorithmic study of this problem, and we provide both positive and negative results on its approximability. When the agents have a commonly accepted value for each item, our results show a sharp separation between the cases of two or more agents. In particular, we establish a PTAS for two agents, and we complement this with a hardness result, that for three or more agents, the best approximation guarantee is provided by essentially selling all items. This hardness barrier, however, is relieved when the number of distinct item values is constant, as we provide an efficient algorithm for any number of agents. We also explore the generalization to heterogeneous valuations, where the hardness result continues to hold, and where we provide positive results for certain special cases.
Cite as

Vittorio Bilò, Evangelos Markakis, and Cosimo Vinci. Achieving Envy-Freeness Through Items Sale. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ESA.2024.26,
  author =	{Bil\`{o}, Vittorio and Markakis, Evangelos and Vinci, Cosimo},
  title =	{{Achieving Envy-Freeness Through Items Sale}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.26},
  URN =		{urn:nbn:de:0030-drops-210977},
  doi =		{10.4230/LIPIcs.ESA.2024.26},
  annote =	{Keywords: Fair Item Allocation, Approximation Algorithms, Envy-freeness, Markets}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.41
A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games

Authors: Argyrios Deligkas, Michail Fasoulakis, and Evangelos Markakis

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Since the celebrated PPAD-completeness result for Nash equilibria in bimatrix games, a long line of research has focused on polynomial-time algorithms that compute ε-approximate Nash equilibria. Finding the best possible approximation guarantee that we can have in polynomial time has been a fundamental and non-trivial pursuit on settling the complexity of approximate equilibria. Despite a significant amount of effort, the algorithm of Tsaknakis and Spirakis [Tsaknakis and Spirakis, 2008], with an approximation guarantee of (0.3393+δ), remains the state of the art over the last 15 years. In this paper, we propose a new refinement of the Tsaknakis-Spirakis algorithm, resulting in a polynomial-time algorithm that computes a (1/3+δ)-Nash equilibrium, for any constant δ > 0. The main idea of our approach is to go beyond the use of convex combinations of primal and dual strategies, as defined in the optimization framework of [Tsaknakis and Spirakis, 2008], and enrich the pool of strategies from which we build the strategy profiles that we output in certain bottleneck cases of the algorithm.
Cite as

Argyrios Deligkas, Michail Fasoulakis, and Evangelos Markakis. A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{deligkas_et_al:LIPIcs.ESA.2022.41,
  author =	{Deligkas, Argyrios and Fasoulakis, Michail and Markakis, Evangelos},
  title =	{{A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.41},
  URN =		{urn:nbn:de:0030-drops-169790},
  doi =		{10.4230/LIPIcs.ESA.2022.41},
  annote =	{Keywords: bimatrix games, approximate Nash equilibria}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.20
Cost Sharing over Combinatorial Domains: Complement-Free Cost Functions and Beyond

Authors: Georgios Birmpas, Evangelos Markakis, and Guido Schäfer

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We study mechanism design for combinatorial cost sharing models. Imagine that multiple items or services are available to be shared among a set of interested agents. The outcome of a mechanism in this setting consists of an assignment, determining for each item the set of players who are granted service, together with respective payments. Although there are several works studying specialized versions of such problems, there has been almost no progress for general combinatorial cost sharing domains until recently [S. Dobzinski and S. Ovadia, 2017]. Still, many questions about the interplay between strategyproofness, cost recovery and economic efficiency remain unanswered. The main goal of our work is to further understand this interplay in terms of budget balance and social cost approximation. Towards this, we provide a refinement of cross-monotonicity (which we term trace-monotonicity) that is applicable to iterative mechanisms. The trace here refers to the order in which players become finalized. On top of this, we also provide two parameterizations (complementary to a certain extent) of cost functions which capture the behavior of their average cost-shares. Based on our trace-monotonicity property, we design a scheme of ascending cost sharing mechanisms which is applicable to the combinatorial cost sharing setting with symmetric submodular valuations. Using our first cost function parameterization, we identify conditions under which our mechanism is weakly group-strategyproof, O(1)-budget-balanced and O(H_n)-approximate with respect to the social cost. Further, we show that our mechanism is budget-balanced and H_n-approximate if both the valuations and the cost functions are symmetric submodular; given existing impossibility results, this is best possible. Finally, we consider general valuation functions and exploit our second parameterization to derive a more fine-grained analysis of the Sequential Mechanism introduced by Moulin. This mechanism is budget balanced by construction, but in general only guarantees a poor social cost approximation of n. We identify conditions under which the mechanism achieves improved social cost approximation guarantees. In particular, we derive improved mechanisms for fundamental cost sharing problems, including Vertex Cover and Set Cover.
Cite as

Georgios Birmpas, Evangelos Markakis, and Guido Schäfer. Cost Sharing over Combinatorial Domains: Complement-Free Cost Functions and Beyond. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{birmpas_et_al:LIPIcs.ESA.2019.20,
  author =	{Birmpas, Georgios and Markakis, Evangelos and Sch\"{a}fer, Guido},
  title =	{{Cost Sharing over Combinatorial Domains: Complement-Free Cost Functions and Beyond}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.20},
  URN =		{urn:nbn:de:0030-drops-111419},
  doi =		{10.4230/LIPIcs.ESA.2019.20},
  annote =	{Keywords: Approximation Algorithms, Combinatorial Cost Sharing, Mechanism Design, Truthfulness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.9
Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results

Authors: Georgios Amanatidis, Evangelos Markakis, and Krzysztof Sornat

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
We study a revenue maximization problem in the context of social networks. Namely, we consider a model introduced by Alon, Mansour, and Tennenholtz (EC 2013) that captures inequity aversion, i.e., prices offered to neighboring vertices should not be significantly different. We first provide approximation algorithms for a natural class of instances, referred to as the class of single-value revenue functions. Our results improve on the current state of the art, especially when the number of distinct prices is small. This applies, for example, to settings where the seller will only consider a fixed number of discount types or special offers. We then resolve one of the open questions posed in Alon et al., by establishing APX-hardness for the problem. Surprisingly, we further show that the problem is NP-complete even when the price differences are allowed to be relatively large. Finally, we also provide some extensions of the model of Alon et al., regarding the allowed set of prices.
Cite as

Georgios Amanatidis, Evangelos Markakis, and Krzysztof Sornat. Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{amanatidis_et_al:LIPIcs.MFCS.2016.9,
  author =	{Amanatidis, Georgios and Markakis, Evangelos and Sornat, Krzysztof},
  title =	{{Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{9:1--9:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.9},
  URN =		{urn:nbn:de:0030-drops-64254},
  doi =		{10.4230/LIPIcs.MFCS.2016.9},
  annote =	{Keywords: inequity aversion, social networks, revenue maximization}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact