Search Results

Documents authored by Koutsoupias, Elias

Document
DOI: 10.4230/LIPIcs.AFT.2024.9
Blockchain Space Tokenization

Authors: Aggelos Kiayias, Elias Koutsoupias, Philip Lazos, and Giorgos Panagiotakos

Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)

Abstract
Handling congestion in blockchain systems is a fundamental problem given that the security and decentralization objectives of such systems lead to designs that compromise on (horizontal) scalability (what sometimes is referred to as the "blockchain trilemma"). Motivated by this, we focus on the question whether it is possible to design a transaction inclusion policy for block producers that facilitates fee and delay predictability while being incentive compatible at the same time. Reconciling these three properties is seemingly paradoxical given that the dominant approach to transaction processing is based on first-price auctions (e.g., as in Bitcoin) or dynamic adjustment of the minimum admissible fee (e.g. as in Ethereum EIP-1559) something that breaks fee predictability. At the same time, in fixed fee mechanisms (e.g., as in Cardano), fees are trivially predictable but are subject to relatively inexpensive bribing or denial of service attacks where transactions may be delayed indefinitely by a well funded attacker, hence breaking delay predictability. In this work, we set out to address this problem by putting forward blockchain space tokenization (BST), namely a new capability of a blockchain system to tokenize its capacity for transactions and allocate it to interested users who are willing to pay ahead of time for the ability to post transactions regularly for a period of time. We analyze our system in the face of worst-case transaction-processing attacks by introducing a security game played between the mempool mechanism and an adversary. Leveraging this framework, we prove that BST offers predictable and asymptotically optimal delays, predictable fees, and is incentive compatible, thus answering the question posed in the affirmative.
Cite as

Aggelos Kiayias, Elias Koutsoupias, Philip Lazos, and Giorgos Panagiotakos. Blockchain Space Tokenization. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kiayias_et_al:LIPIcs.AFT.2024.9,
  author =	{Kiayias, Aggelos and Koutsoupias, Elias and Lazos, Philip and Panagiotakos, Giorgos},
  title =	{{Blockchain Space Tokenization}},
  booktitle =	{6th Conference on Advances in Financial Technologies (AFT 2024)},
  pages =	{9:1--9:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-345-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{316},
  editor =	{B\"{o}hme, Rainer and Kiffer, Lucianna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.9},
  URN =		{urn:nbn:de:0030-drops-209453},
  doi =		{10.4230/LIPIcs.AFT.2024.9},
  annote =	{Keywords: Blockchain protocols, Predictable Service, Transaction Fees}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.Tokenomics.2022.1
Algorithmic Game Theory and Blockchains (Invited Talk)

Authors: Elias Koutsoupias

Published in: OASIcs, Volume 110, 4th International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2022)

Abstract
Algorithmic game theory has developed into a mature field over the past three decades. However, the emergence of blockchains has raised new fundamental questions at the intersection of computer science, economics, and game theory.
Cite as

Elias Koutsoupias. Algorithmic Game Theory and Blockchains (Invited Talk). In 4th International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2022). Open Access Series in Informatics (OASIcs), Volume 110, pp. 1:1-1:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{koutsoupias:OASIcs.Tokenomics.2022.1,
  author =	{Koutsoupias, Elias},
  title =	{{Algorithmic Game Theory and Blockchains}},
  booktitle =	{4th International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2022)},
  pages =	{1:1--1:2},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-274-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{110},
  editor =	{Amoussou-Guenou, Yackolley and Kiayias, Aggelos and Verdier, Marianne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2022.1},
  URN =		{urn:nbn:de:0030-drops-184180},
  doi =		{10.4230/OASIcs.Tokenomics.2022.1},
  annote =	{Keywords: Blockchains, Mining games, Reward sharing schemes, Distributed game theory}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.56
Truthful Allocation in Graphs and Hypergraphs

Authors: George Christodoulou, Elias Koutsoupias, and Annamária Kovács

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

Abstract
We study truthful mechanisms for allocation problems in graphs, both for the minimization (i.e., scheduling) and maximization (i.e., auctions) setting. The minimization problem is a special case of the well-studied unrelated machines scheduling problem, in which every given task can be executed only by two pre-specified machines in the case of graphs or a given subset of machines in the case of hypergraphs. This corresponds to a multigraph whose nodes are the machines and its hyperedges are the tasks. This class of problems belongs to multidimensional mechanism design, for which there are no known general mechanisms other than the VCG and its generalization to affine minimizers. We propose a new class of mechanisms that are truthful and have significantly better performance than affine minimizers in many settings. Specifically, we provide upper and lower bounds for truthful mechanisms for general multigraphs, as well as special classes of graphs such as stars, trees, planar graphs, k-degenerate graphs, and graphs of a given treewidth. We also consider the objective of minimizing or maximizing the L^p-norm of the values of the players, a generalization of the makespan minimization that corresponds to p = ∞, and extend the results to any p > 0.
Cite as

George Christodoulou, Elias Koutsoupias, and Annamária Kovács. Truthful Allocation in Graphs and Hypergraphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 56:1-56:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.ICALP.2021.56,
  author =	{Christodoulou, George and Koutsoupias, Elias and Kov\'{a}cs, Annam\'{a}ria},
  title =	{{Truthful Allocation in Graphs and Hypergraphs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{56:1--56:20},
  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.56},
  URN =		{urn:nbn:de:0030-drops-141256},
  doi =		{10.4230/LIPIcs.ICALP.2021.56},
  annote =	{Keywords: Algorithmic Game Theory, Scheduling Unrelated Machines, Mechanism Design}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.57
Towards the k-Server Conjecture: A Unifying Potential, Pushing the Frontier to the Circle

Authors: Christian Coester and Elias Koutsoupias

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

Abstract
The k-server conjecture, first posed by Manasse, McGeoch and Sleator in 1988, states that a k-competitive deterministic algorithm for the k-server problem exists. It is conjectured that the work function algorithm (WFA) achieves this guarantee, a multi-purpose algorithm with applications to various online problems. This has been shown for several special cases: k = 2, (k+1)-point metrics, (k+2)-point metrics, the line metric, weighted star metrics, and k = 3 in the Manhattan plane. The known proofs of these results are based on potential functions tied to each particular special case, thus requiring six different potential functions for the six cases. We present a single potential function proving k-competitiveness of WFA for all these cases. We also use this potential to show k-competitiveness of WFA on multiray spaces and for k = 3 on trees. While the DoubleCoverage algorithm was known to be k-competitive for these latter cases, it has been open for WFA. Our potential captures a type of lazy adversary and thus shows that in all settled cases, the worst-case adversary is lazy. Chrobak and Larmore conjectured in 1992 that a potential capturing the lazy adversary would resolve the k-server conjecture. To our major surprise, this is not the case, as we show (using connections to the k-taxi problem) that our potential fails for three servers on the circle. Thus, our potential highlights laziness of the adversary as a fundamental property that is shared by all settled cases but violated in general. On the one hand, this weakens our confidence in the validity of the k-server conjecture. On the other hand, if the k-server conjecture holds, then we believe it can be proved by a variant of our potential.
Cite as

Christian Coester and Elias Koutsoupias. Towards the k-Server Conjecture: A Unifying Potential, Pushing the Frontier to the Circle. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 57:1-57:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{coester_et_al:LIPIcs.ICALP.2021.57,
  author =	{Coester, Christian and Koutsoupias, Elias},
  title =	{{Towards the k-Server Conjecture: A Unifying Potential, Pushing the Frontier to the Circle}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{57:1--57:20},
  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.57},
  URN =		{urn:nbn:de:0030-drops-141263},
  doi =		{10.4230/LIPIcs.ICALP.2021.57},
  annote =	{Keywords: Online algorithms, competitive analysis, k-server, work function algorithm}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.8
Better Bounds for Online Line Chasing

Authors: Marcin Bienkowski, Jarosław Byrka, Marek Chrobak, Christian Coester, Łukasz Jeż, and Elias Koutsoupias

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We study online competitive algorithms for the line chasing problem in Euclidean spaces R^d, where the input consists of an initial point P_0 and a sequence of lines X_1, X_2, ..., X_m, revealed one at a time. At each step t, when the line X_t is revealed, the algorithm must determine a point P_t in X_t. An online algorithm is called c-competitive if for any input sequence the path P_0, P_1 , ..., P_m it computes has length at most c times the optimum path. The line chasing problem is a variant of a more general convex body chasing problem, where the sets X_t are arbitrary convex sets. To date, the best competitive ratio for the line chasing problem was 28.1, even in the plane. We improve this bound by providing a simple 3-competitive algorithm for any dimension d. We complement this bound by a matching lower bound for algorithms that are memoryless in the sense of our algorithm, and a lower bound of 1.5358 for arbitrary algorithms. The latter bound also improves upon the previous lower bound of sqrt{2}~=1.412 for convex body chasing in 2 dimensions.
Cite as

Marcin Bienkowski, Jarosław Byrka, Marek Chrobak, Christian Coester, Łukasz Jeż, and Elias Koutsoupias. Better Bounds for Online Line Chasing. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.MFCS.2019.8,
  author =	{Bienkowski, Marcin and Byrka, Jaros{\l}aw and Chrobak, Marek and Coester, Christian and Je\.{z}, {\L}ukasz and Koutsoupias, Elias},
  title =	{{Better Bounds for Online Line Chasing}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.8},
  URN =		{urn:nbn:de:0030-drops-109521},
  doi =		{10.4230/LIPIcs.MFCS.2019.8},
  annote =	{Keywords: convex body chasing, line chasing, competitive analysis}
}
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.ICALP.2017.14
The Infinite Server Problem

Authors: Christian Coester, Elias Koutsoupias, and Philip Lazos

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We study a variant of the k-server problem, the infinite server problem, in which infinitely many servers reside initially at a particular point of the metric space and serve a sequence of requests. In the framework of competitive analysis, we show a surprisingly tight connection between this problem and the (h,k)-server problem, in which an online algorithm with k servers competes against an offline algorithm with h servers. Specifically, we show that the infinite server problem has bounded competitive ratio if and only if the (h,k)-server problem has bounded competitive ratio for some k=O(h). We give a lower bound of 3.146 for the competitive ratio of the infinite server problem, which implies the same lower bound for the (h,k)-server problem even when k>>h and holds also for the line metric; the previous known bounds were 2.4 for general metric spaces and 2 for the line. For weighted trees and layered graphs we obtain upper bounds, although they depend on the depth. Of particular interest is the infinite server problem on the line, which we show to be equivalent to the seemingly easier case in which all requests are in a fixed bounded interval away from the original position of the servers. This is a special case of a more general reduction from arbitrary metric spaces to bounded subspaces. Unfortunately, classical approaches (double coverage and generalizations, work function algorithm, balancing algorithms) fail even for this special case.
Cite as

Christian Coester, Elias Koutsoupias, and Philip Lazos. The Infinite Server Problem. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{coester_et_al:LIPIcs.ICALP.2017.14,
  author =	{Coester, Christian and Koutsoupias, Elias and Lazos, Philip},
  title =	{{The Infinite Server Problem}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.14},
  URN =		{urn:nbn:de:0030-drops-74563},
  doi =		{10.4230/LIPIcs.ICALP.2017.14},
  annote =	{Keywords: Online Algorithms, k-Server, Resource Augmentation}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.47
Online Market Intermediation

Authors: Yiannis Giannakopoulos, Elias Koutsoupias, and Philip Lazos

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We study a dynamic market setting where an intermediary interacts with an unknown large sequence of agents that can be either sellers or buyers: their identities, as well as the sequence length n, are decided in an adversarial, online way. Each agent is interested in trading a single item, and all items in the market are identical. The intermediary has some prior, incomplete knowledge of the agents' values for the items: all seller values are independently drawn from the same distribution F_S, and all buyer values from F_B. The two distributions may differ, and we make common regularity assumptions, namely that F_B is MHR and F_S is log-concave. We focus on online, posted-price mechanisms, and analyse two objectives: that of maximizing the intermediary's profit and that of maximizing the social welfare, under a competitive analysis benchmark. First, on the negative side, for general agent sequences we prove tight competitive ratios of Theta(\sqrt(n)) and Theta(\ln n), respectively for the two objectives. On the other hand, under the extra assumption that the intermediary knows some bound \alpha on the ratio between the number of sellers and buyers, we design asymptotically optimal online mechanisms with competitive ratios of 1+o(1) and 4, respectively. Additionally, we study the model where the number of items that can be stored in stock throughout the execution is bounded, in which case the competitive ratio for the profit is improved to O(ln n).
Cite as

Yiannis Giannakopoulos, Elias Koutsoupias, and Philip Lazos. Online Market Intermediation. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{giannakopoulos_et_al:LIPIcs.ICALP.2017.47,
  author =	{Giannakopoulos, Yiannis and Koutsoupias, Elias and Lazos, Philip},
  title =	{{Online Market Intermediation}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{47:1--47:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.47},
  URN =		{urn:nbn:de:0030-drops-74815},
  doi =		{10.4230/LIPIcs.ICALP.2017.47},
  annote =	{Keywords: optimal auctions, bilateral trade, sequential auctions, online algorithms, competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.43
Carpooling in Social Networks

Authors: Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Claire Mathieu, and Rotem Zach

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We consider the online carpool fairness problem of [Fagin and Williams, 1983] in which an online algorithm is presented with a sequence of pairs drawn from a group of n potential drivers. The online algorithm must select one driver from each pair, with the objective of partitioning the driving burden as fairly as possible for all drivers. The unfairness of an online algorithm is a measure of the worst-case deviation between the number of times a person has driven and the number of times they would have driven if life was completely fair. We introduce a version of the problem in which drivers only carpool with their neighbors in a given social network graph; this is a generalization of the original problem, which corresponds to the social network of the complete graph. We show that for graphs of degree d, the unfairness of deterministic algorithms against adversarial sequences is exactly d/2. For random sequences of edges from planar graph social networks we give a [deterministic] algorithm with logarithmic unfairness (holds more generally for any bounded-genus graph). This does not follow from previous random sequence results in the original model, as we show that restricting the random sequences to sparse social network graphs may increase the unfairness. A very natural class of randomized online algorithms are so-called static algorithms that preserve the same state distribution over time. Surprisingly, we show that any such algorithm has unfairness ~Theta(sqrt(d)) against oblivious adversaries. This shows that the local random greedy algorithm of [Ajtai et al, 1996] is close to optimal amongst the class of static algorithms. A natural (non-static) algorithm is global random greedy (which acts greedily and breaks ties at random). We improve the lower bound on the competitive ratio from Omega(log^{1/3}(d)) to Omega(log(d)). We also show that the competitive ratio of global random greedy against adaptive adversaries is Omega(d).
Cite as

Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Claire Mathieu, and Rotem Zach. Carpooling in Social Networks. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fiat_et_al:LIPIcs.ICALP.2016.43,
  author =	{Fiat, Amos and Karlin, Anna R. and Koutsoupias, Elias and Mathieu, Claire and Zach, Rotem},
  title =	{{Carpooling in Social Networks}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{43:1--43:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.43},
  URN =		{urn:nbn:de:0030-drops-63234},
  doi =		{10.4230/LIPIcs.ICALP.2016.43},
  annote =	{Keywords: Online algorithms, Fairness, Randomized algorithms, Competitive ratio, Carpool problem}
}
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 About DROPS Imprint Privacy Contact