Search Publications
Publications
2019 |
Filos-Ratsikas, Aris; Goldberg, Paul W The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches Conference Forthcoming The 51st Annual ACM Symposium on the Theory of Computing (STOC 2019), ACM, Forthcoming. @conference{Filos-Ratsikas2019, title = {The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches}, author = {Aris Filos-Ratsikas and Paul W. Goldberg}, url = {https://arxiv.org/abs/1805.12559}, year = {2019}, date = {2019-06-27}, booktitle = {The 51st Annual ACM Symposium on the Theory of Computing (STOC 2019)}, publisher = {ACM}, abstract = {We resolve the computational complexity of two problems known as NECKLACE-SPLITTING and DISCRETE HAM SANDWICH, showing that they are PPA-complete. For NECKLACE SPLITTING, this result is specific to the important special case in which two thieves share the necklace. We do this via a PPA-completeness result for an approximate version of the CONSENSUS-HALVING problem, strengthening our recent result that the problem is PPA-complete for inverse-exponential precision. At the heart of our construction is a smooth embedding of the high-dimensional Möbius strip in the CONSENSUS-HALVING problem. These results settle the status of PPA as a class that captures the complexity of "natural" problems whose definitions do not incorporate a circuit.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } We resolve the computational complexity of two problems known as NECKLACE-SPLITTING and DISCRETE HAM SANDWICH, showing that they are PPA-complete. For NECKLACE SPLITTING, this result is specific to the important special case in which two thieves share the necklace. We do this via a PPA-completeness result for an approximate version of the CONSENSUS-HALVING problem, strengthening our recent result that the problem is PPA-complete for inverse-exponential precision. At the heart of our construction is a smooth embedding of the high-dimensional Möbius strip in the CONSENSUS-HALVING problem. These results settle the status of PPA as a class that captures the complexity of "natural" problems whose definitions do not incorporate a circuit. |
Stephane Martin, Boi Faltings ; Schickel, Vincent Context-Tree Recommendation vs Matrix-Factorization: Algorithm Selection and Live Users Evaluation Conference Forthcoming Proceedings of the 31st AAAI Conference on Innovative Applications of AI, 31 , AAAI, Forthcoming. @conference{Martin2019, title = {Context-Tree Recommendation vs Matrix-Factorization: Algorithm Selection and Live Users Evaluation}, author = {Stephane Martin, Boi Faltings and Vincent Schickel}, editor = { }, url = {https://lia.epfl.ch/wp-content/uploads/2018/11/paper_iaai-1.pdf}, year = {2019}, date = {2019-01-29}, booktitle = {Proceedings of the 31st AAAI Conference on Innovative Applications of AI}, volume = {31}, publisher = {AAAI}, abstract = {We describe the selection, implementation and online evaluation of two e-commerce recommender systems developed with our partner company, Prediggo. The first one is based on the novel method of Bayesian Variable-order Markov Modeling (BVMM). The second, SSAGD, is a novel variant of the Matrix-Factorization technique (MF), which is considered state-of-the-art in the recommender literature. We discuss the offline tests we carried out to select the best MF variant, and present the results of two A/B tests performed on live ecommerce websites after the deployment of the new algorithms. Comparing the new recommenders and Prediggo’s proprietary algorithm of Ontology Filtering, we show that the BVMM significantly outperforms the two others in terms of CTR and prediction speed, and leads to a strong increase in recommendation-mediated sales. Although MF exhibits reasonably good accuracy, the BVMM is still significantly more accurate and avoids the high memory requirements of MF. This scalability is essential for its application in online businesses.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } We describe the selection, implementation and online evaluation of two e-commerce recommender systems developed with our partner company, Prediggo. The first one is based on the novel method of Bayesian Variable-order Markov Modeling (BVMM). The second, SSAGD, is a novel variant of the Matrix-Factorization technique (MF), which is considered state-of-the-art in the recommender literature. We discuss the offline tests we carried out to select the best MF variant, and present the results of two A/B tests performed on live ecommerce websites after the deployment of the new algorithms. Comparing the new recommenders and Prediggo’s proprietary algorithm of Ontology Filtering, we show that the BVMM significantly outperforms the two others in terms of CTR and prediction speed, and leads to a strong increase in recommendation-mediated sales. Although MF exhibits reasonably good accuracy, the BVMM is still significantly more accurate and avoids the high memory requirements of MF. This scalability is essential for its application in online businesses. |
Goel, Naman; Faltings, Boi Deep Bayesian Trust : A Dominant and Fair Incentive Mechanism for Crowd Conference 33rd AAAI Conference on Artificial Intelligence, 2019, AAAI, 2019. @conference{Goel2019, title = {Deep Bayesian Trust : A Dominant and Fair Incentive Mechanism for Crowd}, author = {Naman Goel and Boi Faltings}, url = {https://lia.epfl.ch/~goel/upload/doc/papers/2019/goel_aaai19.pdf}, year = {2019}, date = {2019-01-27}, booktitle = {33rd AAAI Conference on Artificial Intelligence, 2019}, publisher = {AAAI}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Goel, Naman; Faltings, Boi Crowdsourcing with Fairness, Diversity and Budget Constraints Conference Proceedings of the AAAI/ACM Conference on AI, Ethics and Society (AIES) 2019, AAAI/ACM, 2019. @conference{Goel2019b, title = {Crowdsourcing with Fairness, Diversity and Budget Constraints}, author = {Naman Goel and Boi Faltings}, url = {https://arxiv.org/abs/1810.13314}, year = {2019}, date = {2019-01-27}, booktitle = {Proceedings of the AAAI/ACM Conference on AI, Ethics and Society (AIES) 2019}, publisher = {AAAI/ACM}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Branzei, Simina; Filos-Ratsikas, Aris Walrasian Dynamics in Multi-unit Markets Conference The 33rd AAAI Conference on Artificial Intelligence (AAAI '19), AAAI AAAI Press, 2019. @conference{Branzei2019, title = {Walrasian Dynamics in Multi-unit Markets}, author = {Simina Branzei and Aris Filos-Ratsikas}, url = {https://arxiv.org/pdf/1712.08910.pdf}, year = {2019}, date = {2019-01-25}, booktitle = {The 33rd AAAI Conference on Artificial Intelligence (AAAI '19)}, publisher = {AAAI Press}, organization = {AAAI}, abstract = {In a multi-unit market, a seller brings multiple units of a good and tries to sell them to a set of buyers that have monetary endowments. While a Walrasian equilibrium does not always exist in this model, natural relaxations of the concept that retain its desirable fairness properties do exist. We study the dynamics of (Walrasian) envy-free pricing mechanisms in this environment, showing that for any such pricing mechanism, the best response dynamic starting from truth-telling converges to a pure Nash equilibrium with small loss in revenue and welfare. Moreover, we generalize these bounds to capture all the (reasonable) Nash equilibria for a large class of (monotone) pricing mechanisms. We also identify a natural mechanism, which selects the minimum Walrasian envy-free price, in which for n=2 buyers the best response dynamic con- verges from any starting profile. We conjecture convergence of the mechanism for any number of buyers and provide simulation results to support our conjecture.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } In a multi-unit market, a seller brings multiple units of a good and tries to sell them to a set of buyers that have monetary endowments. While a Walrasian equilibrium does not always exist in this model, natural relaxations of the concept that retain its desirable fairness properties do exist. We study the dynamics of (Walrasian) envy-free pricing mechanisms in this environment, showing that for any such pricing mechanism, the best response dynamic starting from truth-telling converges to a pure Nash equilibrium with small loss in revenue and welfare. Moreover, we generalize these bounds to capture all the (reasonable) Nash equilibria for a large class of (monotone) pricing mechanisms. We also identify a natural mechanism, which selects the minimum Walrasian envy-free price, in which for n=2 buyers the best response dynamic con- verges from any starting profile. We conjecture convergence of the mechanism for any number of buyers and provide simulation results to support our conjecture. |
2018 |
Chatzopoulos, Dimitris; Gujar, Sujit; Faltings, Boi; Hui, Pan Privacy Preserving and Cost Optimal Mobile Crowdsensing Using Smart Contracts on Blockchain Conference IEEE 15th International Conference on Mobile Ad Hoc and Sensor Systems (MASS), IEEE, 2018, ISSN: 2155-6814. @conference{Chatz2018, title = {Privacy Preserving and Cost Optimal Mobile Crowdsensing Using Smart Contracts on Blockchain}, author = {Dimitris Chatzopoulos and Sujit Gujar and Boi Faltings and Pan Hui}, url = {https://lia.epfl.ch/wp-content/uploads/2019/02/08567590.pdf}, doi = {10.1109/MASS.2018.00068}, issn = {2155-6814}, year = {2018}, date = {2018-10-09}, booktitle = {IEEE 15th International Conference on Mobile Ad Hoc and Sensor Systems (MASS)}, pages = {442-450}, publisher = {IEEE}, abstract = {The popularity and applicability of mobile crowdsensing applications are continuously increasing due to the widespread of mobile devices and their sensing and processing capabilities. However, we need to offer appropriate incentives to the mobile users who contribute their resources and preserve their privacy. Blockchain technologies enable semi-anonymous multi-party interactions and can be utilized in crowdsensing applications to maintain the privacy of the mobile users while ensuring first-rate crowdsensed data. In this work, we propose to use blockchain technologies and smart contracts to orchestrate the interactions between mobile crowdsensing providers and mobile users for the case of spatial crowdsensing, where mobile users need to be at specific locations to perform the tasks. Smart contracts, by operating as processes that are executed on the blockchain, are used to preserve users’ privacy and make payments. Furthermore, for the assignment of the crowdsensing tasks to the mobile users, we design a truthful, cost-optimal auction that minimizes the payments from the crowdsensing providers to the mobile users. Extensive experimental results show that the proposed privacy preserving auction outperforms state-of-the-art proposals regarding cost by ten times for high numbers of mobile users and tasks.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } The popularity and applicability of mobile crowdsensing applications are continuously increasing due to the widespread of mobile devices and their sensing and processing capabilities. However, we need to offer appropriate incentives to the mobile users who contribute their resources and preserve their privacy. Blockchain technologies enable semi-anonymous multi-party interactions and can be utilized in crowdsensing applications to maintain the privacy of the mobile users while ensuring first-rate crowdsensed data. In this work, we propose to use blockchain technologies and smart contracts to orchestrate the interactions between mobile crowdsensing providers and mobile users for the case of spatial crowdsensing, where mobile users need to be at specific locations to perform the tasks. Smart contracts, by operating as processes that are executed on the blockchain, are used to preserve users’ privacy and make payments. Furthermore, for the assignment of the crowdsensing tasks to the mobile users, we design a truthful, cost-optimal auction that minimizes the payments from the crowdsensing providers to the mobile users. Extensive experimental results show that the proposed privacy preserving auction outperforms state-of-the-art proposals regarding cost by ten times for high numbers of mobile users and tasks. |
Aris Filos-Ratsikas Soren Kristoffer Stiil Frederiksen, Paul. Goldberg W; Zhang, Jie Hardness Results for Consensus-Halving Conference 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), 117 , Leibniz International Proceedings in Informatics (LIPIcs) Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, ISBN: 978-3-95977-086-6. @conference{Filos-Ratsikas2018, title = {Hardness Results for Consensus-Halving}, author = {Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen, Paul. W Goldberg and Jie Zhang}, editor = {Igor Potapov, Paul Spirakis and James Worrell}, url = {https://arxiv.org/pdf/1609.05136.pdf}, doi = {10.4230/LIPIcs.MFCS.2018.24}, isbn = {978-3-95977-086-6}, year = {2018}, date = {2018-08-27}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, volume = {117}, pages = {24:1 - 24:16}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, abstract = {The Consensus-halving problem is the problem of dividing an object into two portions, such that each of n agents has equal valuation for the two portions. We study the epsilon-approximate version, which allows each agent to have an epsilon discrepancy on the values of the portions. It was recently proven in that the problem of computing an epsilon-approximate consensus-halving solution (for n agents and n cuts) is PPA-complete when epsilon is inverse-exponential. In this paper, we prove that when epsilon is constant, the problem is PPAD-hard and the problem remains PPAD-hard when we allow a constant number of additional cuts. Additionally, we prove that deciding whether a solution with n − 1 cuts exists for the problem is NP-hard.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } The Consensus-halving problem is the problem of dividing an object into two portions, such that each of n agents has equal valuation for the two portions. We study the epsilon-approximate version, which allows each agent to have an epsilon discrepancy on the values of the portions. It was recently proven in that the problem of computing an epsilon-approximate consensus-halving solution (for n agents and n cuts) is PPA-complete when epsilon is inverse-exponential. In this paper, we prove that when epsilon is constant, the problem is PPAD-hard and the problem remains PPAD-hard when we allow a constant number of additional cuts. Additionally, we prove that deciding whether a solution with n − 1 cuts exists for the problem is NP-hard. |
Stephane Martin, Boi Faltings ; Schickel, Vincent Enhancing Session-Based Recommendations through Sequential Modeling Conference 32nd ACM Conference on User Modeling, Adaptation and Personalization, 32 , ACM, 2018. @conference{Martin2018, title = {Enhancing Session-Based Recommendations through Sequential Modeling}, author = {Stephane Martin, Boi Faltings and Vincent Schickel}, url = {https://lia.epfl.ch/wp-content/uploads/2018/11/umap_extended_abstract_with_abstract-1.pdf}, year = {2018}, date = {2018-07-08}, booktitle = {32nd ACM Conference on User Modeling, Adaptation and Personalization}, volume = {32}, publisher = {ACM}, abstract = {Recommender systems typically determine the items they should recommend by learning models of user-preferences. Most often, those preferences are modeled as static and independent of context. In real life however, users consider items in sequence: TV series are watched episode by episode and accessories are chosen after the main appliance. Unfortunately, since sequences are more complex to model, they are often not taken into account. We developed an efficient sequence-modeling approach based on Bayesian Variable-order Markov Models and combined it with an existing content-based system, the Ontology Filtering. We tested this approach through live evaluations on two e-commerce sites. It dramatically increased performance, more than doubling the CTR and strongly increasing recommendation-mediated sales. These tests also confirm that the technique works efficiently and reliably in a production setting.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Recommender systems typically determine the items they should recommend by learning models of user-preferences. Most often, those preferences are modeled as static and independent of context. In real life however, users consider items in sequence: TV series are watched episode by episode and accessories are chosen after the main appliance. Unfortunately, since sequences are more complex to model, they are often not taken into account. We developed an efficient sequence-modeling approach based on Bayesian Variable-order Markov Models and combined it with an existing content-based system, the Ontology Filtering. We tested this approach through live evaluations on two e-commerce sites. It dramatically increased performance, more than doubling the CTR and strongly increasing recommendation-mediated sales. These tests also confirm that the technique works efficiently and reliably in a production setting. |
Goel, Naman; Yaghini, Mohammad; Faltings, Boi Non-Discriminatory Machine Learning through Convex Fairness Criteria Conference Thirty-Second AAAI Conference on Artificial Intelligence, 2018, AAAI, 2018. @conference{Goel2018, title = {Non-Discriminatory Machine Learning through Convex Fairness Criteria}, author = {Naman Goel and Mohammad Yaghini and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/publications/Goel_Naman_AAAI.pdf}, year = {2018}, date = {2018-02-07}, booktitle = {Thirty-Second AAAI Conference on Artificial Intelligence, 2018}, publisher = {AAAI}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Goran Radanovic, Boi Faltings Partial Truthfulness in Minimal Peer Prediction Mechanisms with Limited Knowledge Proceeding 32nd AAAI Conference on Artificial Intelligence 2018. @proceedings{radanovic2018a, title = {Partial Truthfulness in Minimal Peer Prediction Mechanisms with Limited Knowledge}, author = {Goran Radanovic, Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2018/01/Radanovic.pdf}, year = {2018}, date = {2018-02-04}, organization = {32nd AAAI Conference on Artificial Intelligence}, keywords = {}, pubstate = {published}, tppubtype = {proceedings} } |
Goran Radanovic Adish Singla, Andreas Krause Boi Faltings Information Gathering with Peers: Submodular Optimization with Peer-Prediction Constraints Inproceedings Proceedings of the 32nd Conference of the AAAI, 2018. @inproceedings{Radanovic2018b, title = {Information Gathering with Peers: Submodular Optimization with Peer-Prediction Constraints}, author = {Goran Radanovic, Adish Singla, Andreas Krause, Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2018/01/Radanovic-Singla.pdf }, year = {2018}, date = {2018-02-04}, booktitle = {Proceedings of the 32nd Conference of the AAAI}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
Kulev, Igor; Pu, Pearl; Faltings, Boi A Bayesian Approach to Intervention-Based Clustering Journal Article ACM Trans. Intell. Syst. Technol., 9 (4), pp. 44:1–44:23, 2018, ISSN: 2157-6904. @article{Kulev:2018:BAI:3183892.3156683, title = {A Bayesian Approach to Intervention-Based Clustering}, author = {Igor Kulev and Pearl Pu and Boi Faltings}, url = {http://doi.acm.org/10.1145/3156683 https://dl.acm.org/authorize?N677410}, doi = {10.1145/3156683}, issn = {2157-6904}, year = {2018}, date = {2018-01-01}, journal = {ACM Trans. Intell. Syst. Technol.}, volume = {9}, number = {4}, pages = {44:1--44:23}, publisher = {ACM}, address = {New York, NY, USA}, keywords = {}, pubstate = {published}, tppubtype = {article} } |
2017 |
Giannakopoulos, Athanasios; Antognini, Diego; Musat, Claudiu; Hossmann, Andreea; Baeriswyl, Michael Dataset Construction via Attention for Aspect Term Extraction with Distant Supervision Proceeding Forthcoming 7th ICDM Workshop on Sentiment Elicitation from Natural Text for Information Retrieval and Extraction (SENTIRE), Forthcoming. @proceedings{giannakopoulos2017b, title = {Dataset Construction via Attention for Aspect Term Extraction with Distant Supervision}, author = {Athanasios Giannakopoulos and Diego Antognini and Claudiu Musat and Andreea Hossmann and Michael Baeriswyl}, url = {https://lia.epfl.ch/wp-content/uploads/publications/Giannakopoulos2017b.pdf}, year = {2017}, date = {2017-11-18}, publisher = {7th ICDM Workshop on Sentiment Elicitation from Natural Text for Information Retrieval and Extraction (SENTIRE)}, abstract = {Aspect Term Extraction (ATE) detects opinionated aspect terms in sentences or text spans, with the end goal of performing aspect-based sentiment analysis. The small amount of available datasets for supervised ATE and the fact that they cover only a few domains raise the need for exploiting other data sources in new and creative ways. Publicly available review corpora contain a plethora of opinionated aspect terms and cover a larger domain spectrum. In this paper, we first propose a method for using such review corpora for creating a new dataset for ATE. Our method relies on an attention mechanism to select sentences that have a high likelihood of containing actual opinionated aspects. We thus improve the quality of the extracted aspects. We then use the constructed dataset to train a model and perform ATE with distant supervision. By evaluating on human annotated datasets, we prove that our method achieves a significantly improved performance over various unsupervised and supervised baselines. Finally, we prove that sentence selection matters when it comes to creating new datasets for ATE. Specifically, we show that, using a set of selected sentences leads to higher ATE performance compared to using the whole sentence set.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {proceedings} } Aspect Term Extraction (ATE) detects opinionated aspect terms in sentences or text spans, with the end goal of performing aspect-based sentiment analysis. The small amount of available datasets for supervised ATE and the fact that they cover only a few domains raise the need for exploiting other data sources in new and creative ways. Publicly available review corpora contain a plethora of opinionated aspect terms and cover a larger domain spectrum. In this paper, we first propose a method for using such review corpora for creating a new dataset for ATE. Our method relies on an attention mechanism to select sentences that have a high likelihood of containing actual opinionated aspects. We thus improve the quality of the extracted aspects. We then use the constructed dataset to train a model and perform ATE with distant supervision. By evaluating on human annotated datasets, we prove that our method achieves a significantly improved performance over various unsupervised and supervised baselines. Finally, we prove that sentence selection matters when it comes to creating new datasets for ATE. Specifically, we show that, using a set of selected sentences leads to higher ATE performance compared to using the whole sentence set. |
Radanovic, Boi Faltings Goran Game Theory for Data Science: Eliciting Truthful Information Book Morgan & Claypool Publishers, 2017, ISBN: 9781627057295. @book{Radanovic2017, title = {Game Theory for Data Science: Eliciting Truthful Information}, author = {Boi Faltings Goran Radanovic}, doi = {10.2200/S00788ED1V01Y201707AIM035}, isbn = {9781627057295}, year = {2017}, date = {2017-09-21}, volume = {35}, publisher = {Morgan & Claypool Publishers}, keywords = {}, pubstate = {published}, tppubtype = {book} } |
Brammert Ottens Christos Dimitrakakis, Boi Faltings DUCT: An Upper Confidence Bound Approach to Distributed Constraint Optimization Problems Journal Article ACM Transactions on Intelligent Systems and Technology (TIST), 8 (5), pp. 69:1-69:27, 2017. @article{Ottens2017, title = { DUCT: An Upper Confidence Bound Approach to Distributed Constraint Optimization Problems }, author = {Brammert Ottens , Christos Dimitrakakis , Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/publications/DUCT-TIST.pdf}, doi = {https://doi.org/10.1145/3066156}, year = {2017}, date = {2017-07-12}, journal = {ACM Transactions on Intelligent Systems and Technology (TIST)}, volume = {8}, number = {5}, pages = {69:1-69:27}, abstract = {We propose a distributed upper confidence bound approach, DUCT, for solving distributed constraint optimization problems. We compare four variants of this approach with a baseline random sampling algorithm, as well as other complete and incomplete algorithms for DCOPs. Under general assumptions, we theoretically show that the solution found by DUCT after T steps is approximately T−1-close to the optimal. Experimentally, we show that DUCT matches the optimal solution found by the well-known DPOP and O-DPOP algorithms on moderate-size problems, while always requiring less agent communication. For larger problems, where DPOP fails, we show that DUCT produces significantly better solutions than local, incomplete algorithms. Overall, we believe that DUCT is a practical, scalable algorithm for complex DCOPs.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We propose a distributed upper confidence bound approach, DUCT, for solving distributed constraint optimization problems. We compare four variants of this approach with a baseline random sampling algorithm, as well as other complete and incomplete algorithms for DCOPs. Under general assumptions, we theoretically show that the solution found by DUCT after T steps is approximately T−1-close to the optimal. Experimentally, we show that DUCT matches the optimal solution found by the well-known DPOP and O-DPOP algorithms on moderate-size problems, while always requiring less agent communication. For larger problems, where DPOP fails, we show that DUCT produces significantly better solutions than local, incomplete algorithms. Overall, we believe that DUCT is a practical, scalable algorithm for complex DCOPs. |
Fei Mi, Boi Faltings Adaptive Sequential Recommendation for Discussion Forums on MOOCs using Context Trees Conference Proceedings of the 10th International Conference on Educational Data Mining, 2017. @conference{miadaptive, title = {Adaptive Sequential Recommendation for Discussion Forums on MOOCs using Context Trees}, author = {Fei Mi, Boi Faltings}, url = {http://educationaldatamining.org/EDM2017/proc_files/papers/paper_25.pdf}, year = {2017}, date = {2017-06-28}, booktitle = {Proceedings of the 10th International Conference on Educational Data Mining}, abstract = {Massive open online courses (MOOCs) have demonstrated growing popularity and rapid development in recent years. Discussion forums have become crucial components for students and instructors to widely exchange ideas and propagate knowledge. It is important to recommend helpful information from forums to students for the benefit of the learning process. However, students or instructors update discussion forums very often, and the student preferences over forum contents shift rapidly as a MOOC progresses. So, MOOC forum recommendations need to be adaptive to these evolving forum contents and drifting student interests. These frequent changes pose a challenge to most standard recommendation methods as they have difficulty adapting to new and drifting observations. We formalize the discussion forum recommendation problem as a sequence prediction problem. Then we compare different methods, including a new method called context tree (CT), which can be effectively applied to online sequential recommendation tasks. The results show that the CT recommender performs better than other methods for MOOCs forum recommendation task. We analyze the reasons for this and demonstrate that it is because of better adaptation to changes in the domain. This highlights the importance of considering the adaptation aspect when building recommender system with drifting preferences, as well as using machine learning in general.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Massive open online courses (MOOCs) have demonstrated growing popularity and rapid development in recent years. Discussion forums have become crucial components for students and instructors to widely exchange ideas and propagate knowledge. It is important to recommend helpful information from forums to students for the benefit of the learning process. However, students or instructors update discussion forums very often, and the student preferences over forum contents shift rapidly as a MOOC progresses. So, MOOC forum recommendations need to be adaptive to these evolving forum contents and drifting student interests. These frequent changes pose a challenge to most standard recommendation methods as they have difficulty adapting to new and drifting observations. We formalize the discussion forum recommendation problem as a sequence prediction problem. Then we compare different methods, including a new method called context tree (CT), which can be effectively applied to online sequential recommendation tasks. The results show that the CT recommender performs better than other methods for MOOCs forum recommendation task. We analyze the reasons for this and demonstrate that it is because of better adaptation to changes in the domain. This highlights the importance of considering the adaptation aspect when building recommender system with drifting preferences, as well as using machine learning in general. |
Boi Faltings, Michael Schumacher L'intelligence artificielle par la pratique Book PPUR, 2017, ISBN: 978-2-88915-075-5. @book{Faltings2017, title = {L'intelligence artificielle par la pratique}, author = {Boi Faltings, Michael Schumacher}, isbn = {978-2-88915-075-5}, year = {2017}, date = {2017-02-01}, publisher = {PPUR}, keywords = {}, pubstate = {published}, tppubtype = {book} } |
Gujar, Sujit Prakash; Faltings, Boi Auction Based Mechanisms for Dynamic Task Assignments in Expert Crowdsourcing Book Chapter et al., Ceppi S (Ed.): pp. 50-65, Springer, 2017, ISBN: 978-3-319-54229-4. @inbook{Gujar2017, title = {Auction Based Mechanisms for Dynamic Task Assignments in Expert Crowdsourcing}, author = {Sujit Prakash Gujar and Boi Faltings}, editor = {S. Ceppi et al.}, url = {https://lia.epfl.ch/wp-content/uploads/publications/auction-based-mechanisms.pdf}, isbn = {978-3-319-54229-4}, year = {2017}, date = {2017-00-00}, journal = {Agent-Mediated Electronic Commerce}, pages = {50-65}, publisher = {Springer}, series = {LNBIP}, abstract = {Crowdsourcing marketplaces link large populations of workers to an even larger number of tasks. Thus, it is necessary to have mechanisms for matching workers with interesting and suitable tasks. Earlier work has addressed the problem of finding optimal workers for a given set of tasks. However, workers also have preferences and will stay with a platform only if it gives them interesting tasks. We therefore analyze several matching mechanisms that take into account workers’ preferences as well.We propose that the workers pay premiums to get preferred matches and auction-based models where preferences are expressed through variations of the payment for a task. We analyze the properties of two matching different mechanisms: Split Dynamic VCG (SDV) and e-Auction. We compare both the mechanisms with Arrival Priority Serial Dictatorship (APSD) empirically for efficiency.}, keywords = {}, pubstate = {published}, tppubtype = {inbook} } Crowdsourcing marketplaces link large populations of workers to an even larger number of tasks. Thus, it is necessary to have mechanisms for matching workers with interesting and suitable tasks. Earlier work has addressed the problem of finding optimal workers for a given set of tasks. However, workers also have preferences and will stay with a platform only if it gives them interesting tasks. We therefore analyze several matching mechanisms that take into account workers’ preferences as well.We propose that the workers pay premiums to get preferred matches and auction-based models where preferences are expressed through variations of the payment for a task. We analyze the properties of two matching different mechanisms: Split Dynamic VCG (SDV) and e-Auction. We compare both the mechanisms with Arrival Priority Serial Dictatorship (APSD) empirically for efficiency. |
2016 |
Radanovic, Goran; Faltings, Boi; Jurca, Radu Incentives for Effort in Crowdsourcing using the Peer Truth Serum Journal Article Acm Transactions on Intelligent Systems and Technology, 7 (4), pp. 48:1-28, 2016. @article{Radanvoic 2016b, title = {Incentives for Effort in Crowdsourcing using the Peer Truth Serum}, author = {Goran Radanovic and Boi Faltings and Radu Jurca}, url = {https://lia.epfl.ch/wp-content/uploads/publications/ PTS.pdf}, doi = {http://dx.doi.org/10.1145/2856102}, year = {2016}, date = {2016-00-00}, journal = {Acm Transactions on Intelligent Systems and Technology}, volume = {7}, number = {4}, pages = {48:1-28}, abstract = {Crowdsourcing is widely proposed as a method to solve large variety of judgement tasks, such as classifying website content, peer grading in online courses, or collecting real-world data. As the data reported by workers cannot be verified, there is a tendency to report random data without actually solving the task. This can be countered by making the reward for an answer depend on its consistency with answers given by other workers, an approach called peer consistency. However, it is obvious that the best strategy in such schemes is for all workers to report the same answer without solving the task. Dasgupta and Ghosh (WWW 2013) show that in some cases exerting high effort can be encouraged in the highest-paying equilibrium. In this paper we present a general mechanism that implements this idea and is applicable to most crowdsourcing settings. Furthermore, we experimentally test the novel mechanism, and validate its theoretical properties.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Crowdsourcing is widely proposed as a method to solve large variety of judgement tasks, such as classifying website content, peer grading in online courses, or collecting real-world data. As the data reported by workers cannot be verified, there is a tendency to report random data without actually solving the task. This can be countered by making the reward for an answer depend on its consistency with answers given by other workers, an approach called peer consistency. However, it is obvious that the best strategy in such schemes is for all workers to report the same answer without solving the task. Dasgupta and Ghosh (WWW 2013) show that in some cases exerting high effort can be encouraged in the highest-paying equilibrium. In this paper we present a general mechanism that implements this idea and is applicable to most crowdsourcing settings. Furthermore, we experimentally test the novel mechanism, and validate its theoretical properties. |
Chatzopoulos, Dimitris; Gujar, Sujit Prakash; Faltings, Boi; Hui, Pan LocalCoin: An ad-hoc payment scheme for areas with high connectivity: poster. Conference ACM MobiHoc 2016, ACM, 2016. @conference{Faltings2016a, title = {LocalCoin: An ad-hoc payment scheme for areas with high connectivity: poster.}, author = {Dimitris Chatzopoulos and Sujit Prakash Gujar and Boi Faltings and Pan Hui}, url = {https://lia.epfl.ch/wp-content/uploads/publications/ p365-chatzopoulos.pdf}, year = {2016}, date = {2016-00-00}, booktitle = {ACM MobiHoc 2016}, publisher = {ACM}, abstract = {The popularity of digital currencies, especially cryptocurrencies, has been continuously growing since the appearance of Bitcoin. Bitcoin is a peer-to-peer (P2P) cryptocurrency protocol enabling transactions between individuals without the need of a trusted authority. Its network is formed from resources contributed by individuals known as miners. Users of Bitcoin currency create transactions that are stored in a specialised data structure called a block chain. Bitcoin's security lies in a proof-of-work scheme, which requires high computational resources at the miners. These miners have to be synchronised with any update in the network, which produces high data traffic rates. Despite advances in mobile technology, no cryptocurrencies have been proposed for mobile devices. This is largely due to the lower processing capabilities of mobile devices when compared with conventional computers and the poorer Internet connectivity to that of the wired networking. In this work, we propose LocalCoin, an alternative cryptocurrency that requires minimal computational resources, produces low data traffic and works with off-the-shelf mobile devices. LocalCoin replaces the computational hardness that is at the root of Bitcoin's security with the social hardness of ensuring that all witnesses to a transaction are colluders. It is based on opportunistic networking rather than relying on infrastructure and incorporates characteristics of mobile networks such as users' locations and their coverage radius in order to employ an alternative proof-of-work scheme. Localcoin features (i) a lightweight proof-of-work scheme and (ii) a distributed block chain.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } The popularity of digital currencies, especially cryptocurrencies, has been continuously growing since the appearance of Bitcoin. Bitcoin is a peer-to-peer (P2P) cryptocurrency protocol enabling transactions between individuals without the need of a trusted authority. Its network is formed from resources contributed by individuals known as miners. Users of Bitcoin currency create transactions that are stored in a specialised data structure called a block chain. Bitcoin's security lies in a proof-of-work scheme, which requires high computational resources at the miners. These miners have to be synchronised with any update in the network, which produces high data traffic rates. Despite advances in mobile technology, no cryptocurrencies have been proposed for mobile devices. This is largely due to the lower processing capabilities of mobile devices when compared with conventional computers and the poorer Internet connectivity to that of the wired networking. In this work, we propose LocalCoin, an alternative cryptocurrency that requires minimal computational resources, produces low data traffic and works with off-the-shelf mobile devices. LocalCoin replaces the computational hardness that is at the root of Bitcoin's security with the social hardness of ensuring that all witnesses to a transaction are colluders. It is based on opportunistic networking rather than relying on infrastructure and incorporates characteristics of mobile networks such as users' locations and their coverage radius in order to employ an alternative proof-of-work scheme. Localcoin features (i) a lightweight proof-of-work scheme and (ii) a distributed block chain. |
Radanovic, Goran; Faltings, Boi Limiting the Influence of Low Quality Information in Community Sensing Conference Proceedings of the 15th AAMAS, 2016. @conference{Radanovic2016a, title = {Limiting the Influence of Low Quality Information in Community Sensing}, author = {Goran Radanovic and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/publications/ radanovic2016a.pdf}, year = {2016}, date = {2016-00-00}, booktitle = {Proceedings of the 15th AAMAS}, pages = {873-881}, abstract = {We consider a community of private sensors that collect mea surements of a physical phenomenon, such as air pollution, and report it to a center. The center should be able to prevent low quality reports from degrading the quality of the aggregated information, as there are numerous reasons for operators to inject false sensor data. Hence, it is necessary to track the quality of the sensors over time in order to filter out low quality and malicious reports. To achieve this, we construct a reputation system with a guaranteed bounds on negative impact that malicious sensors can cause, and we evaluate its performance on a realistic dataset.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We consider a community of private sensors that collect mea surements of a physical phenomenon, such as air pollution, and report it to a center. The center should be able to prevent low quality reports from degrading the quality of the aggregated information, as there are numerous reasons for operators to inject false sensor data. Hence, it is necessary to track the quality of the sensors over time in order to filter out low quality and malicious reports. To achieve this, we construct a reputation system with a guaranteed bounds on negative impact that malicious sensors can cause, and we evaluate its performance on a realistic dataset. |
Radanovic, Goran; Faltings, Boi Learning to Scale Payments in Crowdsourcing with PropeRBoost Conference Proceedings of the Fourth AAAI conference on Conference on Human Computation and Crowdsourcing (HCOMP'16), 2016. @conference{Radanovic2016c, title = {Learning to Scale Payments in Crowdsourcing with PropeRBoost}, author = {Goran Radanovic and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/publications/ Radanovic.pdf}, year = {2016}, date = {2016-00-00}, booktitle = {Proceedings of the Fourth AAAI conference on Conference on Human Computation and Crowdsourcing (HCOMP'16)}, abstract = {Motivating workers to provide significant effort has been recognized as an important issue in crowdsourcing. It is important not only to compensate worker effort, but also to discourage low-quality workers from participating. Several proper incentive schemes have been proposed for this purpose; they are either based on gold tasks or on peer consistency in individual tasks. As the rewards cannot become negative, these schemes have difficulty in achieving zero expected reward for random answers. We describe a novel boosting scheme, ProperRBoost, that improves the efficiency of existing incentive schemes by making a better separation between incentives for high and low quality work, and effectively discourages random answers by assigning them near minimal average rewards. We show the actual performance of the boosting scheme through simulations of various worker strategies.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Motivating workers to provide significant effort has been recognized as an important issue in crowdsourcing. It is important not only to compensate worker effort, but also to discourage low-quality workers from participating. Several proper incentive schemes have been proposed for this purpose; they are either based on gold tasks or on peer consistency in individual tasks. As the rewards cannot become negative, these schemes have difficulty in achieving zero expected reward for random answers. We describe a novel boosting scheme, ProperRBoost, that improves the efficiency of existing incentive schemes by making a better separation between incentives for high and low quality work, and effectively discourages random answers by assigning them near minimal average rewards. We show the actual performance of the boosting scheme through simulations of various worker strategies. |
Faltings, Boi; Radanovic, Goran Mechanismen zur Beschaffung korrekter Daten Journal Article Informatik Spektrum, 2016. @article{Faltings2016b, title = {Mechanismen zur Beschaffung korrekter Daten}, author = {Boi Faltings and Goran Radanovic}, url = {https://lia.epfl.ch/wp-content/uploads/publications/ Faltings15Sept.pdf}, year = {2016}, date = {2016-00-00}, journal = {Informatik Spektrum}, abstract = {,Smart Cities“ brauchen als Grundlage für Entscheidungen grosse Mengen von Daten, die häufig nicht direkt, sondern über andere Agenten erhoben werden. Es ist daher wichtig, die Qualität durch geeignete Anreize oder Kontrolle sicherzustellen. Bei Ausnutzung der Spieltheorie ist dies erstaunlicherweise selbst dann möglich, wenn die Korrektheit der Daten gar nicht kontrolliert werden kann. Wir zeigen neuartige Mechanismen zur Qualitätssicherung für zwei Arten von Agenten. Für rational handelnde Agenten berechnen wir die Belohnung für die Daten so, dass nur korrekte Daten einen positiven Betrag erwarten können. Für fehlerhafte oder absichlich falsche Daten zeigen wir einen neuen Mechanismus, der den negativen Einfluss auf das erzeugte Modell begrenzt. }, keywords = {}, pubstate = {published}, tppubtype = {article} } ,Smart Cities“ brauchen als Grundlage für Entscheidungen grosse Mengen von Daten, die häufig nicht direkt, sondern über andere Agenten erhoben werden. Es ist daher wichtig, die Qualität durch geeignete Anreize oder Kontrolle sicherzustellen. Bei Ausnutzung der Spieltheorie ist dies erstaunlicherweise selbst dann möglich, wenn die Korrektheit der Daten gar nicht kontrolliert werden kann. Wir zeigen neuartige Mechanismen zur Qualitätssicherung für zwei Arten von Agenten. Für rational handelnde Agenten berechnen wir die Belohnung für die Daten so, dass nur korrekte Daten einen positiven Betrag erwarten können. Für fehlerhafte oder absichlich falsche Daten zeigen wir einen neuen Mechanismus, der den negativen Einfluss auf das erzeugte Modell begrenzt. |
Gujar, Sujit Prakash; Faltings, Boi Online Auctions for Dynamic Assignment: Theory and Empirical Evaluation Conference Proceedings of the European Conference on Artificial Intelligence, 22 , EurAI 2016. @conference{gujar2016a, title = {Online Auctions for Dynamic Assignment: Theory and Empirical Evaluation}, author = {Sujit Prakash Gujar and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/publications/ ECAI2016GujarFaltings.pdf}, year = {2016}, date = {2016-00-00}, booktitle = {Proceedings of the European Conference on Artificial Intelligence}, volume = {22}, pages = {1035-1043}, organization = {EurAI}, abstract = {Dynamic resource assignment is a common problem in multi-agent systems.We consider scenarios in which dynamic agents have preferences about assignments and the resources that can be assigned using online auctions.We study the trade-off between the following online auction properties: (i) truthfulness, (ii) expressiveness, (iii) efficiency, and (iv) average case performance. We theoretically and empirically compare four different online auctions: (i) Arrival Priority Serial Dictatorship, (ii) Split Dynamic VCG, (iii) e-Action, and (iv) Online Ranked Competition Auction. The latter is a novel design based on the competitive secretary problem. We show that, in addition to truthfulness and algorithmic efficiency, the degree of competition also plays an important role in selecting the best algorithm for a given context.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Dynamic resource assignment is a common problem in multi-agent systems.We consider scenarios in which dynamic agents have preferences about assignments and the resources that can be assigned using online auctions.We study the trade-off between the following online auction properties: (i) truthfulness, (ii) expressiveness, (iii) efficiency, and (iv) average case performance. We theoretically and empirically compare four different online auctions: (i) Arrival Priority Serial Dictatorship, (ii) Split Dynamic VCG, (iii) e-Action, and (iv) Online Ranked Competition Auction. The latter is a novel design based on the competitive secretary problem. We show that, in addition to truthfulness and algorithmic efficiency, the degree of competition also plays an important role in selecting the best algorithm for a given context. |
2015 |
Radanovic, Goran; Faltings, Boi Incentives for Subjective Evaluations with Private Beliefs Conference Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI'15), 2015. @conference{Radanovic&Faltings:15a, title = {Incentives for Subjective Evaluations with Private Beliefs}, author = {Goran Radanovic and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/publications/ 9719-44215-1-PB.pdf}, year = {2015}, date = {2015-00-00}, booktitle = {Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI'15)}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |