Search Publications
Publications
2022 |
Danassis, Panayiotis; Triastcyn, Aleksei; Faltings, Boi PermLink A Distributed Differentially Private Algorithm for Resource Allocation in Unboundedly Large Settings Conference Proceedings of the 21th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '22 International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2022. @conference{danassis2022aamas, title = {A Distributed Differentially Private Algorithm for Resource Allocation in Unboundedly Large Settings}, author = {Panayiotis Danassis and Aleksei Triastcyn and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2022/03/arxiv_palma.pdf}, year = {2022}, date = {2022-05-09}, booktitle = {Proceedings of the 21th International Conference on Autonomous Agents and MultiAgent Systems}, publisher = {International Foundation for Autonomous Agents and Multiagent Systems}, address = {Richland, SC}, series = {AAMAS '22}, abstract = {We introduce a practical and scalable algorithm (PALMA) for solving one of the fundamental problems of multi-agent systems -- finding matches and allocations -- in unboundedly large settings (e.g., resource allocation in urban environments, mobility-on-demand systems, etc.), while providing strong worst-case privacy guarantees. PALMA is decentralized, runs on-device, requires no inter-agent communication, and converges in constant time under reasonable assumptions. We evaluate PALMA in a mobility-on-demand and a paper assignment scenario, using real data in both, and demonstrate that it provides a strong level of privacy ($varepsilon leq 1$ and median as low as $varepsilon = 0.5$ across agents) and high-quality matchings (up to $86%$ of the non-private optimal, outperforming even the privacy-preserving centralized maximum-weight matching baseline).}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We introduce a practical and scalable algorithm (PALMA) for solving one of the fundamental problems of multi-agent systems -- finding matches and allocations -- in unboundedly large settings (e.g., resource allocation in urban environments, mobility-on-demand systems, etc.), while providing strong worst-case privacy guarantees. PALMA is decentralized, runs on-device, requires no inter-agent communication, and converges in constant time under reasonable assumptions. We evaluate PALMA in a mobility-on-demand and a paper assignment scenario, using real data in both, and demonstrate that it provides a strong level of privacy ($varepsilon leq 1$ and median as low as $varepsilon = 0.5$ across agents) and high-quality matchings (up to $86%$ of the non-private optimal, outperforming even the privacy-preserving centralized maximum-weight matching baseline). |
Danassis, Panayiotis; Sakota, Marija; Filos-Ratsikas, Aris; Faltings, Boi PermLink Putting Ridesharing to the Test: Efficient and Scalable Solutions and the Power of Dynamic Vehicle Relocation Journal Article Artificial Intelligence Review, 2022, ISSN: 1573-7462. @article{danassis2022air, title = {Putting Ridesharing to the Test: Efficient and Scalable Solutions and the Power of Dynamic Vehicle Relocation}, author = {Panayiotis Danassis and Marija Sakota and Aris Filos-Ratsikas and Boi Faltings}, url = {https://doi.org/10.1007/s10462-022-10145-0 https://arxiv.org/abs/1912.08066}, doi = {10.1007/s10462-022-10145-0}, issn = {1573-7462}, year = {2022}, date = {2022-02-15}, journal = {Artificial Intelligence Review}, abstract = {We study the optimization of large-scale, real-time ridesharing systems and propose a modular design methodology, Component Algorithms for Ridesharing (CAR). We evaluate a diverse set of CARs (14 in total), focusing on the key algorithmic components of ridesharing. We take a multi-objective approach, evaluating 10 metrics related to global efficiency, complexity, passenger, and platform incentives, in settings designed to closely resemble reality in every aspect, focusing on vehicles of capacity two. To the best of our knowledge, this is the largest and most comprehensive evaluation to date. We (i) identify CARs that perform well on global, passenger, or platform metrics, (ii) demonstrate that lightweight relocation schemes can significantly improve the Quality of Service by up to $50%$, and (iii) highlight a practical, scalable, on-device CAR that works well across all metrics.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We study the optimization of large-scale, real-time ridesharing systems and propose a modular design methodology, Component Algorithms for Ridesharing (CAR). We evaluate a diverse set of CARs (14 in total), focusing on the key algorithmic components of ridesharing. We take a multi-objective approach, evaluating 10 metrics related to global efficiency, complexity, passenger, and platform incentives, in settings designed to closely resemble reality in every aspect, focusing on vehicles of capacity two. To the best of our knowledge, this is the largest and most comprehensive evaluation to date. We (i) identify CARs that perform well on global, passenger, or platform metrics, (ii) demonstrate that lightweight relocation schemes can significantly improve the Quality of Service by up to $50%$, and (iii) highlight a practical, scalable, on-device CAR that works well across all metrics. |
Danassis, Panayiotis; Erden, Zeki Doruk; Faltings, Boi PermLink Exploiting Environmental Signals to Enable Policy Correlation in Large-scale Decentralized Systems Journal Article Autonomous Agents and Multi-Agent Systems, 36 (1), pp. 13, 2022, ISSN: 1573-7454. @article{danassis2022jaamas, title = {Exploiting Environmental Signals to Enable Policy Correlation in Large-scale Decentralized Systems}, author = {Panayiotis Danassis and Zeki Doruk Erden and Boi Faltings}, url = {https://doi.org/10.1007/s10458-021-09541-7}, doi = {10.1007/s10458-021-09541-7}, issn = {1573-7454}, year = {2022}, date = {2022-02-03}, journal = {Autonomous Agents and Multi-Agent Systems}, volume = {36}, number = {1}, pages = {13}, abstract = {Can artificial agents benefit from human conventions? Human societies manage to successfully self-organize and resolve the tragedy of the commons in common-pool resources, in spite of the bleak prediction of non-cooperative game theory. On top of that, real-world problems are inherently large-scale and of low observability. One key concept that facilitates human coordination in such settings is the use of conventions. Inspired by human behavior, we investigate the learning dynamics and emergence of temporal conventions, focusing on common-pool resources. Extra emphasis was given in designing a realistic evaluation setting: (a) environment dynamics are modeled on real-world fisheries, (b) we assume decentralized learning, where agents can observe only their own history, and (c) we run large-scale simulations (up to 64 agents). Uncoupled policies and low observability make cooperation hard to achieve; as the number of agents grow, the probability of taking a correct gradient direction decreases exponentially. By introducing an arbitrary common signal (e.g., date, time, or any periodic set of numbers) as a means to couple the learning process, we show that temporal conventions can emerge and agents reach sustainable harvesting strategies. The introduction of the signal consistently improves the social welfare (by $258%$ on average, up to $3306%$), the range of environmental parameters where sustainability can be achieved (by $46%$ on average, up to $300%$), and the convergence speed in low abundance settings (by $13%$ on average, up to $53%$).}, keywords = {}, pubstate = {published}, tppubtype = {article} } Can artificial agents benefit from human conventions? Human societies manage to successfully self-organize and resolve the tragedy of the commons in common-pool resources, in spite of the bleak prediction of non-cooperative game theory. On top of that, real-world problems are inherently large-scale and of low observability. One key concept that facilitates human coordination in such settings is the use of conventions. Inspired by human behavior, we investigate the learning dynamics and emergence of temporal conventions, focusing on common-pool resources. Extra emphasis was given in designing a realistic evaluation setting: (a) environment dynamics are modeled on real-world fisheries, (b) we assume decentralized learning, where agents can observe only their own history, and (c) we run large-scale simulations (up to 64 agents). Uncoupled policies and low observability make cooperation hard to achieve; as the number of agents grow, the probability of taking a correct gradient direction decreases exponentially. By introducing an arbitrary common signal (e.g., date, time, or any periodic set of numbers) as a means to couple the learning process, we show that temporal conventions can emerge and agents reach sustainable harvesting strategies. The introduction of the signal consistently improves the social welfare (by $258%$ on average, up to $3306%$), the range of environmental parameters where sustainability can be achieved (by $46%$ on average, up to $300%$), and the convergence speed in low abundance settings (by $13%$ on average, up to $53%$). |
2021 |
Damle, Sankarshan; Triastcyn, Aleksei; Faltings, Boi; Gujar, Sujit PermLink Differentially Private Multi-Agent Constraint Optimization Conference WI-IAT ’21: IEEE/WIC/ACM International Conference on Web Intelligence, 20 , ACM, 2021. @conference{Damle2021, title = {Differentially Private Multi-Agent Constraint Optimization}, author = {Sankarshan Damle and Aleksei Triastcyn and Boi Faltings and Sujit Gujar }, url = {https://lia.epfl.ch/wp-content/uploads/2021/12/P-Gibbs-Camera-Ready-2.pdf}, doi = {https://doi.org/10.1145/3486622.3493929}, year = {2021}, date = {2021-12-17}, booktitle = {WI-IAT ’21: IEEE/WIC/ACM International Conference on Web Intelligence}, volume = {20}, publisher = {ACM}, abstract = {Several optimization scenarios involve multiple agents that desire to protect the privacy of their preferences. There are distributed algorithms for constraint optimization that provide improved privacy protection through secure multiparty computation. However, it comes at the expense of high computational complexity and does not constitute a rigorous privacy guarantee for optimization outcomes, as the result of the computation itself may compromise agents’ preferences. In this work, we show how to achieve privacy, specifically differential privacy, through the randomization of the solving process. In particular, we present P-Gibbs, which adapts the SD-Gibbs algorithm to obtain differential privacy guarantees with much higher computational efficiency. Experiments on graph coloring and meeting scheduling show the algorithm’s privacy-performance trade-off for varying privacy budgets, and the SD-Gibbs algorithm.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Several optimization scenarios involve multiple agents that desire to protect the privacy of their preferences. There are distributed algorithms for constraint optimization that provide improved privacy protection through secure multiparty computation. However, it comes at the expense of high computational complexity and does not constitute a rigorous privacy guarantee for optimization outcomes, as the result of the computation itself may compromise agents’ preferences. In this work, we show how to achieve privacy, specifically differential privacy, through the randomization of the solving process. In particular, we present P-Gibbs, which adapts the SD-Gibbs algorithm to obtain differential privacy guarantees with much higher computational efficiency. Experiments on graph coloring and meeting scheduling show the algorithm’s privacy-performance trade-off for varying privacy budgets, and the SD-Gibbs algorithm. |
Damle, Sankarshan; Faltings, Boi; Gujar, Sujit PermLink Blockchain-based Practical Multi-agent Secure Comparison and its Application in Auctions Conference WI-IAT ’21: IEEE/WIC/ACM International Conference on Web Intelligence, 20 , ACM, 2021. @conference{Damle2021b, title = {Blockchain-based Practical Multi-agent Secure Comparison and its Application in Auctions}, author = {Sankarshan Damle and Boi Faltings and Sujit Gujar}, url = {https://lia.epfl.ch/wp-content/uploads/2021/12/Auction-Camera-Ready.pdf}, doi = {https://doi.org/10.1145/3486622.3493937}, year = {2021}, date = {2021-12-17}, booktitle = {WI-IAT ’21: IEEE/WIC/ACM International Conference on Web Intelligence}, volume = {20}, publisher = {ACM}, abstract = {AI applications find widespread use in a variety of domains. For further acceptance, mostly when multiple agents interact with the system, we must aim to preserve the privacy of participants information in such applications. Towards this, the Yao’s Millionaires’ problem (YMP), i.e., to determine the richer among two millionaires’ privately, finds relevance. This work presents a novel, practical, and verifiable solution to YMP, namely, Secure Comparison Protocol (SCP). We show that SCP achieves this comparison in a constant number of rounds, without using encryption and not requiring the participants’ continuous involvement. SCP uses semi-trusted third parties - which we refer to as privacy accountants - for the comparison, who do not learn any information about the values. That is, the probability of information leak is negligible in the problem size. In SCP, we also leverage the Ethereum network for pseudo-anonymous communication, unlike computationally expensive secure channels such as Tor. We present a Secure Truthful cOmbinatorial aUction Protocol (STOUP) for single-minded bidders to demonstrate SCP’s significance. We show that STOUP, unlike previous works, preserves the privacies relevant to an auction even from the auctioneer. We demonstrate the practicality of STOUP through simulations.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } AI applications find widespread use in a variety of domains. For further acceptance, mostly when multiple agents interact with the system, we must aim to preserve the privacy of participants information in such applications. Towards this, the Yao’s Millionaires’ problem (YMP), i.e., to determine the richer among two millionaires’ privately, finds relevance. This work presents a novel, practical, and verifiable solution to YMP, namely, Secure Comparison Protocol (SCP). We show that SCP achieves this comparison in a constant number of rounds, without using encryption and not requiring the participants’ continuous involvement. SCP uses semi-trusted third parties - which we refer to as privacy accountants - for the comparison, who do not learn any information about the values. That is, the probability of information leak is negligible in the problem size. In SCP, we also leverage the Ethereum network for pseudo-anonymous communication, unlike computationally expensive secure channels such as Tor. We present a Secure Truthful cOmbinatorial aUction Protocol (STOUP) for single-minded bidders to demonstrate SCP’s significance. We show that STOUP, unlike previous works, preserves the privacies relevant to an auction even from the auctioneer. We demonstrate the practicality of STOUP through simulations. |
Chatzopoulos, Dimitris; Jain, Anurag; Gujar, Sujit; Faltings, Boi; Hui, Pan PermLink Towards Mobile Distributed Ledgers Journal Article IEEE Internet of Things Journal, 2021. @article{Chatzopoulos2021, title = {Towards Mobile Distributed Ledgers}, author = {Dimitris Chatzopoulos and Anurag Jain and Sujit Gujar and Boi Faltings and Pan Hui}, url = {https://lia.epfl.ch/wp-content/uploads/2021/12/FINAL_VERSION-11.pdf}, doi = {10.1109/JIOT.2021.3113730}, year = {2021}, date = {2021-09-20}, journal = {IEEE Internet of Things Journal}, abstract = {Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (e.g., crowdsensing). Sophisticated applications, like cryptocurrencies, need distributed ledgers to function. Distributed ledgers, such as blockchains and directed acyclic graphs (DAGs), employ consensus protocols to add data in the form of blocks. However, such protocols are designed for resourceful devices that are interconnected via the Internet. Moreover, existing distributed ledgers are not deployable to D2D ecosystems since their storage needs are continuously increasing. In this work, we introduce and analyse Mneme, a DAG-based distributed ledger that can be maintained solely by mobile devices. Mneme utilizes two novel consensus protocols: Proof-of-Context (PoC) and Proof-of-Equivalence (PoE). PoC employs users’ context to add data on Mneme. PoE is executed periodically to summarize data and produce equivalent blocks that require less storage. We analyze Mneme’s security and justify the ability of PoC and PoE to guarantee the characteristics of distributed ledgers: persistence and liveness. Furthermore, we analyze potential attacks from malicious users and prove that the probability of a successful attack is inversely proportional to the square of the number of mobile users who maintain Mneme.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (e.g., crowdsensing). Sophisticated applications, like cryptocurrencies, need distributed ledgers to function. Distributed ledgers, such as blockchains and directed acyclic graphs (DAGs), employ consensus protocols to add data in the form of blocks. However, such protocols are designed for resourceful devices that are interconnected via the Internet. Moreover, existing distributed ledgers are not deployable to D2D ecosystems since their storage needs are continuously increasing. In this work, we introduce and analyse Mneme, a DAG-based distributed ledger that can be maintained solely by mobile devices. Mneme utilizes two novel consensus protocols: Proof-of-Context (PoC) and Proof-of-Equivalence (PoE). PoC employs users’ context to add data on Mneme. PoE is executed periodically to summarize data and produce equivalent blocks that require less storage. We analyze Mneme’s security and justify the ability of PoC and PoE to guarantee the characteristics of distributed ledgers: persistence and liveness. Furthermore, we analyze potential attacks from malicious users and prove that the probability of a successful attack is inversely proportional to the square of the number of mobile users who maintain Mneme. |
Mi, Fei; Zhou, Wanhao; Cai, Fengyu; Kong, Lingjing; Huang, Minlie; Faltings, Boi PermLink Self-training Improves Pre-training for Few-shot Learning in Task-oriented Dialog Systems Conference Conference on Empirical Methods in Natural Language Processing, ACL, 2021. @conference{Mi2021, title = {Self-training Improves Pre-training for Few-shot Learning in Task-oriented Dialog Systems}, author = {Fei Mi and Wanhao Zhou and Fengyu Cai and Lingjing Kong and Minlie Huang and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2021/12/2108.12589.pdf}, year = {2021}, date = {2021-08-28}, booktitle = {Conference on Empirical Methods in Natural Language Processing}, pages = {1887-1898}, publisher = {ACL}, abstract = {As the labeling cost for different modules in task-oriented dialog (ToD) systems is expensive, a major challenge is to train different modules with the least amount of labeled data. Recently, large-scale pre-trained language models, have shown promising results for few shot learning in ToD. In this paper, we devise a self-training approach to utilize the abundant unlabeled dialog data to further improve state-of-the-art pre-trained models in few-shot learning scenarios for ToD systems. Specifically, we propose a self-training approach that iteratively labels the most confident unlabeled data to train a stronger Student model. Moreover, a new text augmentation technique (GradAug) is proposed to better train the Student by replacing non-crucial tokens using a masked language model. We conduct extensive experiments and present analyses on four downstream tasks in ToD, including intent classification, dialog state tracking, dialog act prediction, and response selection. Empirical results demonstrate that the proposed self-training approach consistently improves state-of-the-art pre-trained models (BERT, ToD-BERT) when only a small number of labeled data are available.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } As the labeling cost for different modules in task-oriented dialog (ToD) systems is expensive, a major challenge is to train different modules with the least amount of labeled data. Recently, large-scale pre-trained language models, have shown promising results for few shot learning in ToD. In this paper, we devise a self-training approach to utilize the abundant unlabeled dialog data to further improve state-of-the-art pre-trained models in few-shot learning scenarios for ToD systems. Specifically, we propose a self-training approach that iteratively labels the most confident unlabeled data to train a stronger Student model. Moreover, a new text augmentation technique (GradAug) is proposed to better train the Student by replacing non-crucial tokens using a masked language model. We conduct extensive experiments and present analyses on four downstream tasks in ToD, including intent classification, dialog state tracking, dialog act prediction, and response selection. Empirical results demonstrate that the proposed self-training approach consistently improves state-of-the-art pre-trained models (BERT, ToD-BERT) when only a small number of labeled data are available. |
Danassis, Panayiotis; Wiedemair, Florian; Faltings, Boi PermLink Improving Multi-agent Coordination by Learning to Estimate Contention Conference Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI '21 International Joint Conferences on Artificial Intelligence Organization, 2021. @conference{danassis2021ijcai, title = {Improving Multi-agent Coordination by Learning to Estimate Contention}, author = {Panayiotis Danassis and Florian Wiedemair and Boi Faltings}, editor = {Zhi-Hua Zhou}, url = {https://lia.epfl.ch/wp-content/uploads/2021/06/ijcai2021_1.pdf}, doi = {10.24963/ijcai.2021/18}, year = {2021}, date = {2021-08-19}, booktitle = {Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence}, journal = {Proceedings of the 30th International Joint Conference on Artificial Intelligence}, pages = {125--131}, publisher = {International Joint Conferences on Artificial Intelligence Organization}, series = {IJCAI '21}, abstract = {We present a multi-agent learning algorithm, ALMA-Learning, for efficient and fair allocations in large-scale systems. We circumvent the traditional pitfalls of multi-agent learning (e.g., the moving target problem, the curse of dimensionality, or the need for mutually consistent actions) by relying on the ALMA heuristic as a coordination mechanism for each stage game. ALMA-Learning is decentralized, observes only own action/reward pairs, requires no inter-agent communication, and achieves near-optimal (<5% loss) and fair coordination in a variety of synthetic scenarios and a real-world meeting scheduling problem. The lightweight nature and fast learning constitute ALMA-Learning ideal for on-device deployment.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We present a multi-agent learning algorithm, ALMA-Learning, for efficient and fair allocations in large-scale systems. We circumvent the traditional pitfalls of multi-agent learning (e.g., the moving target problem, the curse of dimensionality, or the need for mutually consistent actions) by relying on the ALMA heuristic as a coordination mechanism for each stage game. ALMA-Learning is decentralized, observes only own action/reward pairs, requires no inter-agent communication, and achieves near-optimal (<5% loss) and fair coordination in a variety of synthetic scenarios and a real-world meeting scheduling problem. The lightweight nature and fast learning constitute ALMA-Learning ideal for on-device deployment. |
Petrescu, Diana; Antognini, Diego; Faltings, Boi PermLink Multi-Step Critiquing User Interface for Recommender Systems Conference Demo Proceedings of the 15th ACM Conference on Recommender Systems Proceedings (RecSys 2021), 2021. @conference{petrescu_fastcritiquing_2021, title = {Multi-Step Critiquing User Interface for Recommender Systems}, author = {Diana Petrescu and Diego Antognini and Boi Faltings}, year = {2021}, date = {2021-07-30}, booktitle = {Demo Proceedings of the 15th ACM Conference on Recommender Systems Proceedings (RecSys 2021)}, abstract = {https://arxiv.org/pdf/2107.06416.pdf}, keywords = {}, pubstate = {published}, tppubtype = {conference} } https://arxiv.org/pdf/2107.06416.pdf |
Antognini, Diego; Faltings, Boi PermLink Fast Multi-Step Critiquing for VAE-based Recommender Systems Conference Proceedings of the 15th ACM Conference on Recommender Systems Proceedings (RecSys 2021), 2021. @conference{antognini_fastcritiquing_2021, title = {Fast Multi-Step Critiquing for VAE-based Recommender Systems}, author = {Diego Antognini and Boi Faltings}, url = {https://arxiv.org/pdf/2105.00774.pdf}, year = {2021}, date = {2021-07-06}, booktitle = {Proceedings of the 15th ACM Conference on Recommender Systems Proceedings (RecSys 2021)}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Padh, Kirtan; Antognini, Diego; Glaude, Emma Lejal; Faltings, Boi; Musat, Claudiu PermLink Addressing Fairness in Classificationwith a Model-Agnostic Multi-Objective Algorithm Conference Proceedings of the 37th Conference on Uncertainty in Artificial Intelligence (UAI 2021), 2021. @conference{kirtan2021, title = {Addressing Fairness in Classificationwith a Model-Agnostic Multi-Objective Algorithm}, author = {Kirtan Padh and Diego Antognini and Emma Lejal Glaude and Boi Faltings and Claudiu Musat}, url = {https://arxiv.org/pdf/2009.04441.pdf}, year = {2021}, date = {2021-05-12}, booktitle = {Proceedings of the 37th Conference on Uncertainty in Artificial Intelligence (UAI 2021)}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Antognini, Diego; Faltings, Boi PermLink Rationalization through Concepts Conference Findings of the 59th Annual Meeting of the Association for Computational Linguistics (ACL 2021), 2021. @conference{antognini_concept_2021, title = {Rationalization through Concepts}, author = {Diego Antognini and Boi Faltings }, url = {https://arxiv.org/pdf/2105.04837.pdf}, year = {2021}, date = {2021-05-06}, booktitle = {Findings of the 59th Annual Meeting of the Association for Computational Linguistics (ACL 2021)}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Danassis, Panayiotis; Erden, Zeki Doruk; Faltings, Boi PermLink Improved Cooperation by Exploiting a Common Signal Conference Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '21 International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2021, ISBN: 9781450383073. @conference{danassis2021aamas, title = {Improved Cooperation by Exploiting a Common Signal}, author = {Panayiotis Danassis and Zeki Doruk Erden and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2021/06/aamas2021.pdf}, isbn = {9781450383073}, year = {2021}, date = {2021-05-03}, booktitle = {Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems}, pages = {395–403}, publisher = {International Foundation for Autonomous Agents and Multiagent Systems}, address = {Richland, SC}, series = {AAMAS '21}, abstract = {Can artificial agents benefit from human conventions? Human societies manage to successfully self-organize and resolve the tragedy of the commons in common-pool resources, in spite of the bleak prediction of non-cooperative game theory. On top of that, real-world problems are inherently large-scale and of low observability. One key concept that facilitates human coordination in such settings is the use of conventions. Inspired by human behavior, we investigate the learning dynamics and emergence of temporal conventions, focusing on common-pool resources. Extra emphasis was given in designing a realistic evaluation setting: (a) environment dynamics are modeled on real-world fisheries, (b) we assume decentralized learning, where agents can observe only their own history, and (c) we run large-scale simulations (up to 64 agents).Uncoupled policies and low observability make cooperation hard to achieve; as the number of agents grow, the probability of taking a correct gradient direction decreases exponentially. By introducing an arbitrary common signal (e.g., date, time, or any periodic set of numbers) as a means to couple the learning process, we show that temporal conventions can emerge and agents reach sustainable harvesting strategies. The introduction of the signal consistently improves the social welfare (by 258% on average, up to 3306%), the range of environmental parameters where sustainability can be achieved (by 46% on average, up to 300%), and the convergence speed in low abundance settings (by 13% on average, up to 53%).}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Can artificial agents benefit from human conventions? Human societies manage to successfully self-organize and resolve the tragedy of the commons in common-pool resources, in spite of the bleak prediction of non-cooperative game theory. On top of that, real-world problems are inherently large-scale and of low observability. One key concept that facilitates human coordination in such settings is the use of conventions. Inspired by human behavior, we investigate the learning dynamics and emergence of temporal conventions, focusing on common-pool resources. Extra emphasis was given in designing a realistic evaluation setting: (a) environment dynamics are modeled on real-world fisheries, (b) we assume decentralized learning, where agents can observe only their own history, and (c) we run large-scale simulations (up to 64 agents).Uncoupled policies and low observability make cooperation hard to achieve; as the number of agents grow, the probability of taking a correct gradient direction decreases exponentially. By introducing an arbitrary common signal (e.g., date, time, or any periodic set of numbers) as a means to couple the learning process, we show that temporal conventions can emerge and agents reach sustainable harvesting strategies. The introduction of the signal consistently improves the social welfare (by 258% on average, up to 3306%), the range of environmental parameters where sustainability can be achieved (by 46% on average, up to 300%), and the convergence speed in low abundance settings (by 13% on average, up to 53%). |
Antognini, Diego; Musat, Claudiu; Faltings, Boi PermLink Interacting with Explanations through Critiquing Conference Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), 2021. @conference{antognini22021, title = {Interacting with Explanations through Critiquing}, author = {Diego Antognini and Claudiu Musat and Boi Faltings }, url = {https://arxiv.org/pdf/2005.11067.pdf}, year = {2021}, date = {2021-04-01}, booktitle = {Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021)}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Antognini, Diego; Musat, Claudiu; Faltings, Boi PermLink Multi-Dimensional Explanation of Target Variables from Documents Conference Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), 2021. @conference{antognini2021, title = {Multi-Dimensional Explanation of Target Variables from Documents}, author = {Diego Antognini and Claudiu Musat and Boi Faltings }, editor = {The 35th AAAI Conference on Artificial Intelligence (AAAI), 2021}, url = {https://arxiv.org/pdf/1909.11386.pdf}, year = {2021}, date = {2021-02-01}, booktitle = {Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021)}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Moin Hussain Moti Dimitris Chatzopoulos, Pan Hui Boi Faltings ; Gujar, Sujit PermLink Orthos: A Trustworthy AI Framework for Data Acquisition Book Chapter 12589 , pp. 100-118, Springer, 2021. @inbook{Moti2020, title = {Orthos: A Trustworthy AI Framework for Data Acquisition}, author = {Moin Hussain Moti, Dimitris Chatzopoulos, Pan Hui, Boi Faltings and Sujit Gujar}, url = {https://lia.epfl.ch/wp-content/uploads/2022/01/Orthos__A_Trustworthy_AI_Framework_For_Data_Acquisition.pdf}, year = {2021}, date = {2021-01-07}, volume = {12589}, pages = {100-118}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, abstract = {Information acquisition through crowdsensing with mobile agents is a popular way to collect data, especially in the context of smart cities where the deployment of dedicated data collectors is expensive and ineffective. It requires efficient information elicitation mechanisms to guarantee that the collected data are accurately acquired and reported. Such mechanisms can be implemented via smart contracts on blockchain to enable privacy and trust. In this work we develop Orthos, a blockchain-based trustworthy framework for spontaneous location-based crowdsensing queries without assuming any prior knowledge about them. We employ game-theoretic mechanisms to incentivize agents to report truthfully and ensure that the information is collected at the desired location while ensuring the privacy of the agents. We identify six necessary characteristics for information elicitation mechanisms to be applicable in spontaneous location-based settings and implement an existing state-of-the-art mechanism using smart contracts. Additionally, as location information is exogenous to these mechanisms, we design the Proof-of-Location protocol to ensure that agents gather the data at the desired locations. We examine the performance of Orthos on Rinkeby Ethereum testnet and conduct experiments with live audience.}, keywords = {}, pubstate = {published}, tppubtype = {inbook} } Information acquisition through crowdsensing with mobile agents is a popular way to collect data, especially in the context of smart cities where the deployment of dedicated data collectors is expensive and ineffective. It requires efficient information elicitation mechanisms to guarantee that the collected data are accurately acquired and reported. Such mechanisms can be implemented via smart contracts on blockchain to enable privacy and trust. In this work we develop Orthos, a blockchain-based trustworthy framework for spontaneous location-based crowdsensing queries without assuming any prior knowledge about them. We employ game-theoretic mechanisms to incentivize agents to report truthfully and ensure that the information is collected at the desired location while ensuring the privacy of the agents. We identify six necessary characteristics for information elicitation mechanisms to be applicable in spontaneous location-based settings and implement an existing state-of-the-art mechanism using smart contracts. Additionally, as location information is exogenous to these mechanisms, we design the Proof-of-Location protocol to ensure that agents gather the data at the desired locations. We examine the performance of Orthos on Rinkeby Ethereum testnet and conduct experiments with live audience. |
2020 |
A. Richardson, Filos-Ratsikas A; Faltings, B PermLink Budget-Bounded Incentives for Federated Learning Book Chapter Q. Yang L. Fan, Yu: Federated Learning H (Ed.): 12500 , pp. 176-188, Springer, 2020. @inbook{Richardson2020, title = {Budget-Bounded Incentives for Federated Learning}, author = {A. Richardson, A. Filos-Ratsikas and B. Faltings}, editor = {Q. Yang, L. Fan, H. Yu: Federated Learning}, url = {https://lia.epfl.ch/wp-content/uploads/2021/02/BudgetBoundedIncentivesAug18-2.pdf}, year = {2020}, date = {2020-11-26}, volume = {12500}, pages = {176-188}, publisher = {Springer}, series = {LNCS}, abstract = {We consider federated learning settings with independent, self-interested participants. As all contributions are made privately, participants may be tempted to free-ride and provide redundant or low-quality data while still enjoying the benefits of the FL model. In Federated Learning, this is especially harmful as low-quality data can degrade the quality of the FL model. Free-riding can be countered by giving incentives to participants to provide truthful data. While there are game-theoretic schemes for rewarding truthful data, they do not take into account redundancy of data with previous contributions. This creates arbitrage opportunities where participants can gain rewards for redundant data, and the federation may be forced to pay out more incentives than justified by the value of the FL model. We show how a scheme based on influence can both guarantee that the incentive budget is bounded in proportion to the value of the FL model, and that truthfully reporting data is the dominant strategy of the participants. We show that under reasonable conditions, this result holds even when the testing data is provided by participants.}, keywords = {}, pubstate = {published}, tppubtype = {inbook} } We consider federated learning settings with independent, self-interested participants. As all contributions are made privately, participants may be tempted to free-ride and provide redundant or low-quality data while still enjoying the benefits of the FL model. In Federated Learning, this is especially harmful as low-quality data can degrade the quality of the FL model. Free-riding can be countered by giving incentives to participants to provide truthful data. While there are game-theoretic schemes for rewarding truthful data, they do not take into account redundancy of data with previous contributions. This creates arbitrage opportunities where participants can gain rewards for redundant data, and the federation may be forced to pay out more incentives than justified by the value of the FL model. We show how a scheme based on influence can both guarantee that the incentive budget is bounded in proportion to the value of the FL model, and that truthfully reporting data is the dominant strategy of the participants. We show that under reasonable conditions, this result holds even when the testing data is provided by participants. |
Fei Mi Xiaoyu Lin, Boi Faltings PermLink The ACM Conference on Recommender Systems (RecSys), 2020, (RecSys 2020 best short paper award). @conference{Miii2020, title = {ADER: Adaptively Distilled Exemplar Replay Towards Continual Learning for Session-based Recommendation}, author = {Fei Mi, Xiaoyu Lin, Boi Faltings}, url = {http://liawww.epfl.ch/wp-content/uploads/publications/3383313.3412218.pdf}, year = {2020}, date = {2020-09-07}, booktitle = {The ACM Conference on Recommender Systems (RecSys)}, pages = {408-413}, note = {RecSys 2020 best short paper award}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Danassis, Panayiotis; Faltings, Boi PermLink Proceedings of the 24th European Conference on Artificial Intelligence, ECAI’20 IOS Press, 2020. @conference{danassis2020ecai, title = {Efficient Allocations in Constant Time: Towards Scalable Solutions in the Era of Large Scale Intelligent Systems}, author = {Panayiotis Danassis and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2022/03/1682_paper.pdf}, doi = {10.3233/FAIA200441}, year = {2020}, date = {2020-08-29}, booktitle = {Proceedings of the 24th European Conference on Artificial Intelligence}, journal = {Proceedings of the 24th European Conference on Artificial Intelligence}, pages = {2895 - 2896}, publisher = {IOS Press}, series = {ECAI’20}, abstract = {The next technological revolution will be interwoven to the proliferation of intelligent systems. As we bridge the gap between physical and cyber worlds, we will give rise to large-scale, multi-agent based technologies. A key challenge that cities of the future will have to face is coordination in the use of limited resources, central to which is finding an optimal allocation between agents. To truly allow for scalable solutions, we needs to shift from traditional approaches, to multi-agent solutions, ideally run on-device. We present a novel heuristic (ALMA), which exhibits such properties, for solving the assignment problem. ALMA is decentralized, requires only partial feedback, and has constant in the total problem size running time, under reasonable assumptions on the preference domain of the agents, making it ideal for an on-device implementation. We have evaluated ALMA in a variety of scenarios including synthetic and real data, time constraints, and on-line settings. In all of the cases, ALMA was able to reach high social welfare, while being orders of magnitude faster than the centralized, optimal algorithm.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } The next technological revolution will be interwoven to the proliferation of intelligent systems. As we bridge the gap between physical and cyber worlds, we will give rise to large-scale, multi-agent based technologies. A key challenge that cities of the future will have to face is coordination in the use of limited resources, central to which is finding an optimal allocation between agents. To truly allow for scalable solutions, we needs to shift from traditional approaches, to multi-agent solutions, ideally run on-device. We present a novel heuristic (ALMA), which exhibits such properties, for solving the assignment problem. ALMA is decentralized, requires only partial feedback, and has constant in the total problem size running time, under reasonable assumptions on the preference domain of the agents, making it ideal for an on-device implementation. We have evaluated ALMA in a variety of scenarios including synthetic and real data, time constraints, and on-line settings. In all of the cases, ALMA was able to reach high social welfare, while being orders of magnitude faster than the centralized, optimal algorithm. |
Mi, Fei; Faltings, Boi PermLink Memory Augmented Neural Model for Incremental Session-based Recommendation Conference Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), 2020. @conference{Mi2020, title = {Memory Augmented Neural Model for Incremental Session-based Recommendation}, author = {Fei Mi and Boi Faltings}, url = {https://www.ijcai.org/Proceedings/2020/0300.pdf }, year = {2020}, date = {2020-08-08}, booktitle = {Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020)}, pages = {2169-2176}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Fei Mi Liangwei Chen, Mengjie Zhao Minlie Huang Boi Faltings PermLink Continual Learning for Natural Language Generation in Task-oriented Dialog Systems Conference Findings of the Association for Computational Linguistics: EMNLP 2020, 2020. @conference{Miiii2020, title = {Continual Learning for Natural Language Generation in Task-oriented Dialog Systems}, author = {Fei Mi, Liangwei Chen, Mengjie Zhao, Minlie Huang, Boi Faltings}, url = {https://www.aclweb.org/anthology/2020.findings-emnlp.310}, doi = {10.18653/v1/2020.findings-emnlp.310}, year = {2020}, date = {2020-08-08}, booktitle = {Findings of the Association for Computational Linguistics: EMNLP 2020}, pages = {3461–3474}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Goel, Naman; Filos-Ratsikas, Aris; Faltings, Boi PermLink Peer-Prediction in the Presence of Outcome Dependent Lying Incentives Conference Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), 2020. @conference{Goel2020b, title = {Peer-Prediction in the Presence of Outcome Dependent Lying Incentives}, author = {Naman Goel and Aris Filos-Ratsikas and Boi Faltings}, url = {https://www.ijcai.org/Proceedings/2020/0018.pdf}, year = {2020}, date = {2020-07-11}, booktitle = {Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020)}, pages = {124-131}, abstract = {We derive conditions under which a peer-consistency mechanism can be used to elicit truthful data from non-trusted rational agents when an aggregate statistic of the collected data affects the amount of their incentives to lie. Furthermore, we discuss the relative saving that can be achieved by the mechanism, compared to the rational outcome, if no such mechanism was implemented. Our work is motivated by distributed platforms, where decentralized data oracles collect information about real-world events, based on the aggregate information provided by often self-interested participants. We compare our theoretical observations with numerical simulations on two public real datasets.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We derive conditions under which a peer-consistency mechanism can be used to elicit truthful data from non-trusted rational agents when an aggregate statistic of the collected data affects the amount of their incentives to lie. Furthermore, we discuss the relative saving that can be achieved by the mechanism, compared to the rational outcome, if no such mechanism was implemented. Our work is motivated by distributed platforms, where decentralized data oracles collect information about real-world events, based on the aggregate information provided by often self-interested participants. We compare our theoretical observations with numerical simulations on two public real datasets. |
Goel*, Naman; van Schreven*, Cyril; Filos-Ratsikas, Aris; Faltings, Boi PermLink Infochain: A Decentralized, Trustless and Transparent Oracle on Blockchain Conference Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), 2020. @conference{Goel2020c, title = {Infochain: A Decentralized, Trustless and Transparent Oracle on Blockchain}, author = {Naman Goel* and Cyril van Schreven* and Aris Filos-Ratsikas and Boi Faltings}, url = {https://www.ijcai.org/Proceedings/2020/0635.pdf}, doi = {https://doi.org/10.24963/ijcai.2020/635}, year = {2020}, date = {2020-07-11}, booktitle = {Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020)}, pages = {4604-4610}, abstract = {Blockchain based systems allow various kinds of financial transactions to be executed in a decentralized manner. However, these systems often rely on a trusted third party (oracle) to get correct information about the real-world events, which trigger the financial transactions. In this paper, we identify two biggest challenges in building decentralized, trustless and transparent oracles. The first challenge is acquiring correct information about the real-world events without relying on a trusted information provider. We show how a peer-consistency incentive mechanism can be used to acquire truthful information from an untrusted and self-interested crowd, even when the crowd has outside incentives to provide wrong informations. The second is a system design and implementation challenge. For the first time, we show how to implement a trustless and transparent oracle in Ethereum. We discuss various non-trivial issues that arise in implementing peer-consistency mechanisms in Ethereum, suggest several optimizations to reduce gas cost and provide empirical analysis.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Blockchain based systems allow various kinds of financial transactions to be executed in a decentralized manner. However, these systems often rely on a trusted third party (oracle) to get correct information about the real-world events, which trigger the financial transactions. In this paper, we identify two biggest challenges in building decentralized, trustless and transparent oracles. The first challenge is acquiring correct information about the real-world events without relying on a trusted information provider. We show how a peer-consistency incentive mechanism can be used to acquire truthful information from an untrusted and self-interested crowd, even when the crowd has outside incentives to provide wrong informations. The second is a system design and implementation challenge. For the first time, we show how to implement a trustless and transparent oracle in Ethereum. We discuss various non-trivial issues that arise in implementing peer-consistency mechanisms in Ethereum, suggest several optimizations to reduce gas cost and provide empirical analysis. |
Goel, Naman; Rutagarama, Maxime; Faltings, Boi PermLink Tackling Peer to Peer Discrimination in the Sharing Economy Conference Proceedings of the 12th ACM Web Science Conference (WebSci 2020), ACM, 2020, (Best paper award). @conference{Goel2020, title = {Tackling Peer to Peer Discrimination in the Sharing Economy}, author = {Naman Goel and Maxime Rutagarama and Boi Faltings}, url = {http://liawww.epfl.ch/wp-content/uploads/publications/goel_websci20.pdf}, doi = {https://doi.org/10.1145/3394231.3397926}, year = {2020}, date = {2020-07-07}, booktitle = {Proceedings of the 12th ACM Web Science Conference (WebSci 2020)}, pages = {355-361}, publisher = {ACM}, abstract = {Sharing economy platforms such as Airbnb and Uber face a major challenge in the form of peer-to-peer discrimination based on sensitive personal attributes such as race and gender. As shown by a recent study under controlled settings, reputation systems can eliminate social biases on these platforms by building trust between the users. However, for this to work in practice, the reputation systems must themselves be non-discriminatory. In fact, a biased reputation system will further reinforce the bias and create a vicious feedback loop. Given that the reputation scores are generally aggregates of ratings provided by human users to one another, it is not surprising that the scores often inherit the human bias. In this paper, we address the problem of making reputation systems on sharing economy platforms more fair and unbiased. We show that a game-theoretical incentive mechanism can be used to encourage users to go against common bias and provide a truthful rating about others, obtained through a more careful and deeper evaluation. In situations where an incentive mechanism can’t be implemented, we show that a simple post-processing approach can also be used to correct bias in the reputation scores, while minimizing the loss in the useful information provided by the scores. We evaluate the proposed solution on synthetic and real datasets from Airbnb.}, note = {Best paper award}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Sharing economy platforms such as Airbnb and Uber face a major challenge in the form of peer-to-peer discrimination based on sensitive personal attributes such as race and gender. As shown by a recent study under controlled settings, reputation systems can eliminate social biases on these platforms by building trust between the users. However, for this to work in practice, the reputation systems must themselves be non-discriminatory. In fact, a biased reputation system will further reinforce the bias and create a vicious feedback loop. Given that the reputation scores are generally aggregates of ratings provided by human users to one another, it is not surprising that the scores often inherit the human bias. In this paper, we address the problem of making reputation systems on sharing economy platforms more fair and unbiased. We show that a game-theoretical incentive mechanism can be used to encourage users to go against common bias and provide a truthful rating about others, obtained through a more careful and deeper evaluation. In situations where an incentive mechanism can’t be implemented, we show that a simple post-processing approach can also be used to correct bias in the reputation scores, while minimizing the loss in the useful information provided by the scores. We evaluate the proposed solution on synthetic and real datasets from Airbnb. |
Chatzopoulos, Dimitris; Gujar, Sujit; Faltings, Boi; Hui, Pan PermLink Mneme: A Mobile Distributed Ledger Conference IEEE Infocom 2020, IEEE, 2020. @conference{Chatzopoulos2020a, title = {Mneme: A Mobile Distributed Ledger}, author = {Dimitris Chatzopoulos and Sujit Gujar and Boi Faltings and Pan Hui}, url = {https://lia.epfl.ch/wp-content/uploads/2020/05/main.pdf}, year = {2020}, date = {2020-07-06}, booktitle = {IEEE Infocom 2020}, pages = {1897-1906}, publisher = {IEEE}, abstract = {Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (e.g., crowdsensing). More sophisticated applications, like cryptocurrencies, need distributed ledgers to function. Distributed ledgers, such as blockchains and directed acyclic graphs (DAGs), employ consensus protocols to add data in the form of blocks. However such protocols are designed for resourceful devices that are interconnected via the Internet. Moreover, existing distributed ledgers are not deployable to D2D ecosystems since their storage needs are continuously increasing. In this work, we introduce Mneme, a DAG-based distributed ledger that can be maintained solely by mobile devices and operates via two consensus protocols: Proof-of-Context (PoC) and Proof-of-Equivalence (PoE). PoC employs users’ context to add data on Mneme. PoE is executed periodically to summarize data and produce equivalent blocks that require less storage. We analyze the security of Mneme and justify the ability of PoC and PoE to guarantee the characteristics of distributed ledgers: persistence and liveness. Furthermore, we analyze potential attacks from malicious users and prove that the probability of a successful attack is inversely proportional to the square of the number of mobile users who maintain Mneme.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (e.g., crowdsensing). More sophisticated applications, like cryptocurrencies, need distributed ledgers to function. Distributed ledgers, such as blockchains and directed acyclic graphs (DAGs), employ consensus protocols to add data in the form of blocks. However such protocols are designed for resourceful devices that are interconnected via the Internet. Moreover, existing distributed ledgers are not deployable to D2D ecosystems since their storage needs are continuously increasing. In this work, we introduce Mneme, a DAG-based distributed ledger that can be maintained solely by mobile devices and operates via two consensus protocols: Proof-of-Context (PoC) and Proof-of-Equivalence (PoE). PoC employs users’ context to add data on Mneme. PoE is executed periodically to summarize data and produce equivalent blocks that require less storage. We analyze the security of Mneme and justify the ability of PoC and PoE to guarantee the characteristics of distributed ledgers: persistence and liveness. Furthermore, we analyze potential attacks from malicious users and prove that the probability of a successful attack is inversely proportional to the square of the number of mobile users who maintain Mneme. |