EArly Rumor Detection (EARD) aims to automatically identify an early time point at which an accurate prediction of a claim can be made, based on a chronological sequence of social media posts. This task is particularly challenging in data-limited scenarios. Recently, Large Language Models (LLMs) have demonstrated impressive capabilities in natural language understanding, especially in few-shot settings. However, they are not well-suited for handling time series data and require substantial computational resources for both training and inference. In this work, we propose a novel framework that combines an autonomous agent and an LLM-based detection model, where \textitthe agent acts as a reliable decision-maker for early time point determination, while the LLM serves as a powerful rumor detector. This approach offers the first solution for few-shot EARD, necessitating only the training of a lightweight agent and allowing the LLM to remain training-free. We model EARD as a Markov Decision Process (MDP) and train the agent to learn an optimal policy for early, stable and accurate rumor detection, by imitating a set of expert trajectories curated based on the LLM’s prediction patterns over sequences. Extensive experiments on four real-world rumor detection datasets demonstrate the effectiveness of our method across various LLMs.
@inproceedings{KDD_2026,title={LLM-based Few-Shot Early Rumor Detection with Imitation Agent},booktitle={Thirty-Second SIGKDD Conference on Knowledge Discovery and Data Mining},address={Jeju, Korea},author={Zeng, Fengzhu and Shao, Qian and Cheng, Ling and Gao, Wei and Cheng, Shih-Fen and Ma, Jing and Niu, Cheng},year={2026},month=aug,}
We consider a dynamic pricing problem in network revenue management where customer behavior is predicted by a choice model, i.e., the multinomial logit (MNL) model. The problem, even in the static setting (i.e., customer demand remains unchanged over time), is highly non-concave in prices. Existing studies mostly rely on the observation that the objective function is concave in terms of purchasing probabilities, implying that the static pricing problem with linear constraints on purchasing probabilities can be efficiently solved. However, this approach is limited in handling constraints on prices, noting that such constraints could be highly relevant in some real business considerations. To address this limitation, in this work, we consider a general pricing problem that involves constraints on both prices and purchasing probabilities. To tackle the non-concavity challenge, we develop an approximation mechanism that allows solving the constrained static pricing problem through bisection and mixed-integer linear programming (MILP). We further extend the approximation method to the dynamic pricing context. Our approach involves a resource decomposition method to address the curse of dimensionality of the dynamic problem, as well as a MILP approach to solving sub-problems to near-optimality. Numerical results based on generated instances of various sizes indicate the superiority of our approximation approach in both static and dynamic settings.
@article{IJOC_2026,title={Constrained Pricing in Logit-based Revenue Management},volume={},pages={to appear},journal={INFORMS Journal on Computing},author={Shao, Qian and Mai, Tien and Cheng, Shih-Fen},year={2026},}
Pricing a global product differently across multiple regions is a common but controversial practice. Although price differentiation helps capture unique market characteristics, it also encourages parallel trade, which may affect the overall corporate performance of a global company. We study this problem with a single global business unit (GBU) and multiple local business units (LBUs). The GBU manufactures a product and sets a transfer price for supplying the product to all LBUs, and LBUs decide retail prices for their respective regional markets. Customers can purchase products in any region by comparing LBUs’ prices and other parallel-imported factors, and we construct the demand by a mixed-multinomial logit model. Therefore, each LBU needs to consider the other LBUs’ prices when setting its price, and we formulate this problem as a two-stage game-theoretic model. We verify the existence of a pure-strategy Nash equilibrium. We then develop a learning-based algorithm to find the equilibrium prices of LBUs. Our algorithm is computationally efficient with a large scale of decision-makers. Even for cases with 100 decision-makers, the pure-strategy Nash equilibrium can be obtained within 30 minutes. Numerical studies are conducted using data from the fast-moving consumer products industries. Although parallel trade is detrimental to some LBUs, the existence of parallel trade surprisingly leads to higher overall corporate profits, which is made possible by making the product available at different price points in a market. The proposed method also enables the quantitative validation of several conjectures on parallel trading practices.
@article{AOR_2025,title={Pricing Strategies in Global Channels: Considering the Effects of Parallel Trade},volume={},pages={to appear},journal={Annuals of Operations Research},author={Kao, Yuan-Mao and Yang, Yang and Cheng, Shih-Fen and Wu, Cheng-Hung},year={2025},smu={10518},doi={10.1007/s10479-025-06834-y}}
PRICAI-25
Predict Social Economic Outcomes by Transferred Knowledge with Satellite Imagery
Yang
Tang, Shih-Fen
Cheng, Yunqiang
Zhu, Zhiqiang
Zou, and Yichen
Yang
In Twenty-Second Pacific Rim International Conference on Artificial Intelligence, Nov 2025
Traditional deep learning methods and econometric model have played a crucial role in the field of data mining, particularly in the prediction of soci-oeconomic outcomes. Unfortunately, it needs large amounts of high-quality socioeconomic data for model training, which is prohibitively expensive and unaffordable. With the advancement of remote sensing technology, access to high-resolution satellite imagery has become increasingly affordable and abundant, providing a rich data source for model training. However, socio-economic information is unable to be directly extracted from them. So, in this paper, we propose a method to leverage transfer learning to predict soci-oeconomic indicators (outcomes) through satellite imagery. Specifically, we use road network types as a proxy for socioeconomic factors, which is more effectively and stably than using nightlight. We have extracted eleven dis-tinct road topological features to generate reasonable road network types. Given the unique characteristics of road networks, we have constructed and fine-tuned a hybrid pre-trained model that combines ResNet50 and Vision Transformer architectures for the transfer learning task. Through extensive experiments conducted across multiple regions, we demonstrated that our approach outperforms state-of-the-art methods in this field. This work high-lights the potential of leveraging road network types as a proxy for socioeco-nomic information and the effectiveness of our transfer learning-based framework in extracting valuable insights from satellite imagery to support socioeconomic policy decisions. The code and data will be released via github once the paper is accepted.
@inproceedings{pricai_2025,title={Predict Social Economic Outcomes by Transferred Knowledge with Satellite Imagery},booktitle={Twenty-Second Pacific Rim International Conference on Artificial Intelligence},address={Wellington, New Zealand},author={Tang, Yang and Cheng, Shih-Fen and Zhu, Yunqiang and Zou, Zhiqiang and Yang, Yichen},year={2025},month=nov,smu={10539},}
ICCL-25
Stable and Fair Cost Allocation in Platform-Enabled LCL Consolidation
Many logistics platforms enable collaboration between agents to reduce costs, but determining fair pricing remains challenging when agents have pre-existing partnerships. This paper introduces a cooperative game theory framework to model platform-mediated collaboration, modeling the platform as an additional player. We present a novel characteristic function that distinguishes between partial collaborations (existing relationships) and full collaborations (platform-enabled). Using Shapley value, we derive fair cost allocations and platform charges that reflect each participant’s contribution. We address stability concerns through an optimization model that minimizes platform subsidies while preventing profitable deviations. The framework is demonstrated through an application in freight forwarding for Less-than-Container Load (LCL) consolidation, showing how it balances participant incentives with platform revenue across varying collaboration structures and network sizes.
@inproceedings{iccl_2025,title={Stable and Fair Cost Allocation in Platform-Enabled LCL Consolidation},booktitle={Sixteenth International Conference on Computational Logistics},address={Delft/Rotterdam, Netherlands},author={Tan, Pang Jin and Cheng, Shih-Fen},year={2025},month=sep,smu={10538},}
This paper studies integrating the crowd workforce into next-day home delivery services. In this setting, both crowd drivers and contract drivers collaborate in making deliveries. Crowd drivers have limited capacity and can choose not to deliver if the presented tasks do not align with their preferences. The central question addressed is: How can the platform minimize the total task fulfilment cost, which includes payouts to crowd drivers and additional payouts to contract drivers for delivering the unselected tasks by customizing task displays to crowd drivers? To tackle this problem, we formulate it as a finite-horizon Stochastic Decision Problem, capturing crowd drivers’ utility-driven task preferences, with the option of not choosing a task based on the displayed options. An inherent challenge is approximating the non-constant marginal cost of serving orders not chosen by crowd drivers, which are then assigned to contract drivers. We address this by leveraging a common approximation technique, dividing the service region into zones. Furthermore, we devise a stochastic look-ahead strategy that tackles the curse of dimensionality issues arising in dynamic task display execution and a non-linear (problem specifically concave) boundary condition associated with the cost of hiring contract drivers. In experiments inspired by Singapore’s geography, we demonstrate that choice-based crowd shipping can reduce next-day delivery fulfilment costs by up to 16.9%.
The observed cost savings are closely tied to the task display policies and the task choice behaviors of drivers.
@article{EJOR_2025,title={Choice-based Crowdshipping for Next-day Delivery Services: A Dynamic Task Display Problem},volume={},pages={to appear},journal={European Journal of Operational Research},author={Arslan, Alp and Kilci, Firat and Cheng, Shih-Fen and Misra, Archan},year={2025},smu={10430},}
Search frictions and misallocation are common in decentralized transportation markets. Using novel trip-level data of taxis in Singapore, this paper examines the impact of real-time demand information at airport terminals on search frictions. The information reduces taxi supply misallocation, increasing deadheading speed by 16.3% and decreasing deadheading time by 10.77%, benefiting both passengers and drivers. It raises daily earnings by $3.70 USD and adds 6.2 minutes of operational time per airport-trip taxi. Spatial spillovers are primarily observed among drivers in adjacent districts. Taxis from the Budget Terminal and drivers with fewer prior airport pickups benefit more from this information.
@article{RESTAT_2025,title={Information Provision and Search Frictions: Evidence from the Taxi Industry in Singapore},volume={},pages={to appear},journal={The Review of Economics and Statistics},author={Agarwal, Sumit and Cheng, Shih-Fen and Keppo, Jussi and Wang, Long and Yang, Yang},year={2025},}
Patent
Method and System for Taxi Demand Prediction Using a Neural Network Model
The NP-hard precedence-constrained production scheduling problem (PCPSP) for mine planning chooses the ordered removal of materials from the mine pit and the next processing steps based on resource, geological, and geometrical constraints. Traditionally, it prioritizes the net present value (NPV) of profits across the lifespan of the mine. Yet, the growing shift in environmental concerns also requires shifts to more carbon-aware practices. In this paper, we use the enhanced multi-objective version of the generic PCPSP formulation by adding the NPV of carbon costs as another objective.
We then compare how the Non-dominated Sorting Genetic Algorithm II (NSGA-II) and the Pareto Envelope-based Selection Algorithm II (PESA-II) solve several real-world inspired datasets, after experimenting with the selection pressure parameter of PESA-II.
The outcome reveals that PESA-II runs faster for 75% of the datasets and gives sets of solutions that are more distributed. Meanwhile, NSGA-II consistently produces non-dominated solutions even when the apportionment of a decision variable is varied. Moreover, we assess how the uncertainty of ore tonnage at the mine site modifies the Pareto front via sensitivity analysis. We show that deviations above 15% induce a larger gap from the original.
@inproceedings{azhar_case_2024,title={Comparison of evolutionary algorithms: A case study on the multi-objective carbon-aware mine planning},booktitle={Twentith IEEE International Conference on Automation Science and Engineering},address={Bari, Italy},author={Azhar, Nurul Asyikeen Binte and Gunawan, Aldy and Cheng, Shih-Fen and Leonardi, Erwin},year={2024},month=aug,smu={9495},}
IJCAI-24
Enabling sustainable freight forwarding network via collaborative games
Freight forwarding plays a crucial role in facilitating global trade and logistics. However, as the freight forwarding market is extremely fragmented, freight forwarders often face the issue of not being able to fill the available shipping capacity. This recurrent issue motivates the creation of various freight forwarding networks that aim at exchanging capacities and demands so that the resource utilization of individual freight forwarders can be maximized. In this paper, we focus on how to design such a collaborative network based on collaborative game theory, with the Shapley value representing a fair scheme for profit sharing. Noting that the exact computation of Shapley values is intractable for large-scale real-world scenarios, we incorporate the observation that collaboration among two forwarders is only possible if their service routes and demands overlap. This leads to a new class of collaborative games called the Locally Collaborative Games (LCGs), where agents can only collaborate with their neighbors. We propose an efficient approach to compute Shapley values for LCGs, and numerically demonstrate that our approach significantly outperforms the state-of-the-art approach for a wide variety of network structures.
@inproceedings{tan_ijcai_2024,title={Enabling sustainable freight forwarding network via collaborative games},booktitle={Thirty-Third International Joint Conference on Artificial Intelligence},address={Jeju, Korea},author={Tan, Pang Jin and Cheng, Shih-Fen and Chen, Richard},year={2024},month=aug,smu={9505},}
ICAPS-24
Imitating cost-constrained behaviors in reinforcement learning
Complex planning and scheduling problems have long been solved using various optimization or heuristic approaches. In recent years, imitation learning that aims to learn from expert demonstrations has been proposed as a viable alternative to solving these problems. Generally speaking, imitation learning is designed to learn either the reward (or preference) model or directly the behavioral policy by observing the behavior of an expert. Existing work in imitation learning and inverse reinforcement learning has focused on imitation primarily in unconstrained settings (e.g., no limit on fuel consumed by the vehicle). However, in many real-world domains, the behavior of an expert is governed not only by reward (or preference) but also by constraints. For instance, decisions on self-driving delivery vehicles are dependent not only on the route preferences/rewards (depending on past demand data) but also on the fuel in the vehicle and the time available. In such problems, imitation learning is challenging as decisions are not only dictated by the reward model but are also dependent on a cost-constrained model. In this paper, we provide multiple methods that match expert distributions in the presence of trajectory cost constraints through (a) Lagrangian-based method; (b) Meta-gradients to find a good trade-off between expected return and minimizing constraint violation; and (c) Cost-violation-based alternating gradient. We empirically show that leading imitation learning approaches imitate cost-constrained behaviors poorly and our meta-gradient-based approach achieves the best performance.
@inproceedings{shao_icaps_2024,title={Imitating cost-constrained behaviors in reinforcement learning},booktitle={Thirty-Fourth International Conference on Automated Planning and Scheduling},address={Banff, Alberta, Canada},author={Shao, Qian and Varakantham, Pradeep and Cheng, Shih-Fen},year={2024},month=jun,smu={9496},}
2023
IEEE BigData-23
M^2-CNN: A macro-micro model for taxi demand prediction
Shih-Fen
Cheng, and Prabod
Rathnayaka
In 2023 IEEE International Conference on Big Data, Dec 2023
In this paper, we introduce a macro-micro model for predicting taxi demands. Our model is a composite deep learning model that integrates multiple views. Our network design specifically incorporates the spatial and temporal dependency of taxi or ride-hailing demand, unlike previous papers that also utilize deep learning models. In addition, we propose a hybrid of Long Short-Term Memory Networks and Temporal Convolutional Networks that incorporates real world time series with long sequences. Finally, we introduce a microscopic component that attempts to extract insights revealed by roaming vacant taxis. In our study, we demonstrate that our approach is competitive against a large array of approaches from the literature on the basis of detailed moving logs of more than 20,000 taxis and 12 million trips per month over a three-month period. Our analysis of the effectiveness of individual components reveals that microscopic information is essential for generating high-quality predictions.
@inproceedings{cheng_bigdata_2023,title={M$^{2}$-CNN: A macro-micro model for taxi demand prediction},booktitle={2023 IEEE International Conference on Big Data},address={Sorrento, Italy},author={Cheng, Shih-Fen and Rathnayaka, Prabod},year={2023},month=dec,smu={8543}}
IEEE SSCI-23
Designing large-scale intelligent collaborative platform for freight forwarders
In this paper, we propose to design a large-scale intelligent collaborative platform for freight forwarders. This platform is based on a mathematical programming formulation and an efficient solution approach. Forwarders are middlemen who procure container capacities from carriers and sell them to shippers to serve their transport requests. However, due to demand uncertainty, they often either over-procure or under-procure capacities. We address this with our proposed platform where forwarders can collaborate and share capacities, allowing one’s transport requests to be potentially shipped on another forwarder’s container. The result is lower total costs for all participating forwarders. The collaboration can be formulated as an integer linear program we call the Freight Forwarders’ Collaboration Problem (FFCP). It is a variant of the bin-packing problem, hence it is NP-Hard. In order to solve large-scale FFCP instances efficiently, we propose a two-step approach involving an initial greedy assignment followed by a fine-tuning step. Computational experiments have shown that our approach can offer a significant reduction of run-time between 77% and 97%, without any loss of solution quality.
@inproceedings{tan_ssci_2023,title={Designing large-scale intelligent collaborative platform for freight forwarders},booktitle={2023 IEEE Symposium Series on Computational Intelligence},address={Mexico City, Mexico},author={Tan, Pang Jin and Cheng, Shih-Fen and Chen, Richard},year={2023},month=dec,smu={8544}}
IEEE ITSC-23
Quantifying taxi drivers’ behaviors with behavioral game theory
Mengyu
Ji, Yuhong
Xu, and Shih-Fen
Cheng
In Twenty-Sixth IEEE International Conference on Intelligent Transportation Systems, Sep 2023
With their flexibility and convenience, taxis play a vital role in urban transportation systems. Understanding how human drivers make decisions in a context of uncertainty and competition is crucial for taxi fleets that depend on drivers to provide their services. As part of this paper, we propose modeling taxi drivers’ behaviors based on behavioral game theory. Based on real-world data, we demonstrate that the behavioral game theory model we select is superior to state-of-the-art baselines. These results provide a solid foundation for improving taxi fleet efficiency in the future.
@inproceedings{ji_itsc_2023,title={Quantifying taxi drivers' behaviors with behavioral game theory},booktitle={Twenty-Sixth IEEE International Conference on Intelligent Transportation Systems},address={Bilbao, Spain},author={Ji, Mengyu and Xu, Yuhong and Cheng, Shih-Fen},year={2023},month=sep,smu={8554}}
ICCL-23
Carbon-aware mine planning with a novel multi-objective framework
The logistical complication of long-term mine planning involves deciding the sequential extraction of materials from the mine pit and their subsequent processing steps based on geological, geometrical, and resource constraints. The net present value (NPV) of profit over the mine’s lifespan usually forms the sole objective for this problem, which is considered as the NP-hard precedence-constrained production scheduling problem (PCPSP) as well. However, increased pressure for more sustainable and carbon-aware industries also calls for environmental indicators to be considered. In this paper, we enhance the generic PCPSP formulation into a multi-objective optimization (MOO) problem whereby carbon cost forms an additional objective. We apply the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) to this formulation and experiment with variants to the solution generation. Our tailored application of the NSGA-II using a set of real-world inspired datasets can form an approximated Pareto front for planners to observe stipulated annual carbon emission targets. It also displays that tailored variants of the NSGA-II can produce diverse solutions that are close to the true Pareto front.
@inproceedings{azhar_iccl_2023,title={Carbon-aware mine planning with a novel multi-objective framework},booktitle={Fourteenth International Conference on Computational Logistics},address={Berlin, Germany},author={Azhar, Nurul Asyikeen and Gunawan, Aldy and Cheng, Shih-Fen and Leonardi, Erwin},year={2023},month=sep,smu={8074}}
In large scale multi-agent systems like taxi fleets, individual agents (taxi drivers) are self interested (maximizing their own profits) and this can introduce inefficiencies in the system. One such inefficiency is with regards to the "required" availability of taxis at different time periods during the day. Since a taxi driver can work for limited number of hours in a day (e.g., 8-10 hours in a city like Singapore), there is a need to optimize the specific hours, so as to maximize individual as well as social welfare. Technically, this corresponds to solving a large scale multi-stage selfish routing game with transition uncertainty. Existing work in addressing this problem is either unable to handle "driver" constraints (e.g., breaks during work hours) or not scalable. To that end, we provide a novel mechanism that builds on replicator dynamics through ideas from behavior cloning. We demonstrate that our methods provide significantly better policies than the existing approach in terms of improving individual agent revenue and overall agent availability.
@inproceedings{kumar_aamas_2023,title={Strategic planning for flexible agent availability in large taxi fleets},booktitle={Twenty-Second International Conference on Autonomous Agents and Multiagent Systems},address={London, UK},author={Kumar, Rajiv and Varakantham, Pradeep and Cheng, Shih-Fen},year={2023},month=may,smu={8072}}
Optimizing delivery routes for last-mile logistics service is challenging and has attracted the attention of many researchers. These problems are usually modeled and solved as variants of vehicle routing problems (VRPs) with challenging real-world constraints (e.g., time windows, precedence). However, despite many decades of solid research on solving these VRP instances, we still see significant gaps between optimized routes and the routes that are actually preferred by the practitioners. Most of these gaps are due to the difference between what’s being optimized, and what the practitioners actually care about, which is hard to be defined exactly in many instances. In this paper, we propose a novel hierarchical route optimizer with learnable parameters that combines the strength of both the optimization and machine learning approaches. Our hierarchical router first solves a zone-level Traveling Salesman Problem with learnable weights on various zone-level features; with the zone visit sequence fixed, we then solve the stop-level vehicle routing problem as a Shortest Hamiltonian Path problem. The Bayesian optimization approach is then introduced to allow us to adjust the weights to be assigned to different zone features used in solving the zone-level Traveling Salesman Problem. By using a real-world delivery dataset provided by the Amazon Last Mile Routing Research Challenge, we demonstrate the importance of having both the optimization and the machine learning components. We also demonstrate how we can use route-related features to identify instances that we might have difficulty with. This paves ways to further research on how we can tackle these difficult instances.
@inproceedings{shao_aamas_2023,title={Preference-aware delivery planning for last-mile logistics},booktitle={Twenty-Second International Conference on Autonomous Agents and Multiagent Systems},address={London, UK},author={Shao, Qian and Cheng, Shih-Fen},year={2023},month=may,smu={8073}}
In domains where agents interact strategically, game theory is applied widely to predict how agents would behave. However, game-theoretic predictions are based on the assumption that agents are fully rational and believe in equilibrium plays, which unfortunately are mostly not true when human decision makers are involved. To address this limitation, a number of behavioral game-theoretic models are defined to account for the limited rationality of human decision makers. The "quantal cognitive hierarchy" (QCH) model, which is one of the more recent models, is demonstrated to be the state-of-art model for predicting human behaviors in normal-form games. The QCH model assumes that agents in games can be both non-strategic (level-0) and strategic (level-k). For level-0 agents, they choose their strategies irrespective of other agents. For level-k agents, they assume that other agents would be behaving at levels less than k and best respond against them. However, an important assumption of the QCH model is that the distribution of agents’ levels follows a Poisson distribution. In this paper, we relax this assumption and design a learning-based method at the population level to iteratively estimate the empirical distribution of agents’ reasoning levels. By using a real-world dataset from the Swedish lowest unique positive integer game, we demonstrate how our refined QCH model and the iterative solution-seeking process can be used in providing a more accurate behavioral model for agents. This leads to better performance in fitting the real data and allows us to track an agent’s progress in learning to play strategically over multiple rounds.
@inproceedings{xu_aamas_2023,title={Improving quantal cognitive hierarchy model through iterative population learning},booktitle={Twenty-Second International Conference on Autonomous Agents and Multiagent Systems},address={London, UK},author={Xu, Yuhong and Cheng, Shih-Fen and Chen, Xinyu},year={2023},month=may,smu={8071}}
This paper investigates the impact of neighborhood retail amenities on taxi trip behavior. We exploit a natural experiment in Singapore where the government introduced a new policy that allows retail shops to operate in residential neighborhoods. We find that the introduction of retail amenities in residential neighborhoods leads to a significant increase in taxi trips. This increase is driven by the increase in the number of trips to and from the retail amenities. We also find that the increase in taxi trips is more pronounced during the weekends and evenings. Our findings suggest that the introduction of retail amenities in residential neighborhoods can have a significant impact on taxi trip behavior.
@article{lee_habitat_2023,title={Neighborhood retail amenities and taxi trip behavior: A natural experiment in Singapore},volume={131},pages={102714},journal={Habitat International},author={Lee, Kwan Ok and Cheng, Shih-Fen},year={2023},smu={7620},}
We study the role of ride-hailing surge factors on the allocative efficiency of taxis by combining a reduced-form estimation with structural analyses using machine-learning-based demand predictions. Where other research study the effect of entry on incumbent taxis, we use higher frequency granular data to study how location-time-specific surge factors affect taxi bookings to bound the effect of customer decisions while accounting for various confounding variables. We find that even in a unique market like Singapore, where incumbent taxi companies have app-based booking systems similar to those from ride-hailing companies like Uber, the estimated upper bound on the cross-platform substitution between ride-hailing services and taxi bookings is only 0.26. On the other hand, we show that incorporating surge price factor improves the precision of demand prediction by 12% to 15%. Our structural analyses based on a driver guidance system finds this improved accuracy in demand prediction reduces drivers’ vacant roaming times by 9.4% and increases the average number of trips per taxi by 2.6%, suggesting the price information is valuable across platforms, even if elasticities are low.
@article{agarwal_trc_2022,title={The impact of ride-hail surge factors on taxi bookings},volume={136},pages={103508},journal={Transportation Research Part C},author={Agarwal, Sumit and Charoenwong, Ben and Cheng, Shih-Fen and Keppo, Jussi},year={2022},smu={6955},}
ICCL-22
A carbon-aware planning framework for production scheduling in mining
Managing the flow of excavated materials from a mine pit and the subsequent processing steps is the logistical challenge in mining. Mine planning needs to consider various geometric and resource constraints while maximizing the net present value (NPV) of profits over a long horizon. This mine planning problem has been modelled and solved as a precedence constrained production scheduling problem (PCPSP) using heuristics, due to its NP-hardness. However, the recent push for sustainable and carbon-aware mining practices calls for new planning approaches. In this paper, we propose an efficient temporally decomposed greedy Lagrangian relaxation (TDGLR) approach to maximize profits while observing the stipulated carbon emission limit per year. With a collection of real-world-inspired mining datasets, we demonstrate how we generate approximated Pareto fronts for planners. Using this approach, they can choose mine plans that maximize profits while observing the given carbon emission target. The TDGLR was compared against a Mixed Integer Programming (MIP) model to solve a real mine dataset with the gaps not exceeding 0.3178% and averaging 0.015%. For larger instances, MIP cannot even generate feasible solutions.
@inproceedings{azhar_iccl_2022,title={A carbon-aware planning framework for production scheduling in mining},booktitle={13th International Conference on Computational Logistics},address={Barcelona, Spain},author={Azhar, Nurul Asyikeen and Gunawan, Aldy and Cheng, Shih-Fen and Leonardi, Erwin},year={2022},month=sep,smu={7566}}
Geoinformatics 2022
Taxi travel time based Geographically Weighted Regression Model (GWR) for modeling public housing prices in Singapore
Yi’An
Wang, Fangyi
Cai, Shih-Fen
Cheng, Bo
Wu, and Kai
Cao
In Twenty-Ninth International Conference on Geoinformatics, Aug 2022
In this research, a taxi travel time based Geographically Weighted Regression model (GWR) is proposed and utilized to model the public housing price in the case study of Singapore. In addition, a comparison between the proposed taxi data driven GWR and other models, such as ordinary least squares model (OLS), GWR model based on Euclidean distance and GWR model based on public transport travel time, have also been carried out. Results indicates that taxi travel time based GWR model has better fitting performance than the OLS model, and slightly better than the Euclidean distance-based GWR model, however, it is not as good as the GWR model based on public transport travel time according to the metric of Adjusted R2. These experiments indicate that the public transport travel time may has a major part to play in modeling the public housing resale prices compared to taxi travel time or driving time, and both the taxi travel time and public transport travel time can better explain the public housing resale prices in Singapore compared to Euclidean distance in the GWR modeling.
@inproceedings{wang_geoinfo_2022,title={Taxi travel time based Geographically Weighted Regression Model (GWR) for modeling public housing prices in Singapore},booktitle={Twenty-Ninth International Conference on Geoinformatics},address={Beijing, China},author={Wang, Yi'An and Cai, Fangyi and Cheng, Shih-Fen and Wu, Bo and Cao, Kai},year={2022},month=aug,smu={7708}}
AAAI-22
Multiscale generative models: Improving performance of a generative model using feedback from other dependent generative models
Changyu
Chen, Avinandan
Bose, Shih-Fen
Cheng, and Arunesh
Sinha
In Thirty-Sixth AAAI Conference on Artificial Intelligence, Feb 2022
Realistic fine-grained multi-agent simulation of real-world complex systems is crucial for many downstream tasks such as reinforcement learning. Recent work has used generative models (GANs in particular) for providing high-fidelity simulation of real-world systems. However, such generative models are often monolithic and miss out on modeling the interaction in multi-agent systems. In this work, we take a first step towards building multiple interacting generative models (GANs) that reflects the interaction in real world. We build and analyze a hierarchical set-up where a higher-level GAN is conditioned on the output of multiple lower-level GANs. We present a technique of using feedback from the higher-level GAN to improve performance of lower-level GANs. We mathematically characterize the conditions under which our technique is impactful, including understanding the transfer learning nature of our set-up. We present three distinct experiments on synthetic data, time series data, and image domain, revealing the wide applicability of our technique.
@inproceedings{chen_aaai_2022,title={Multiscale generative models: Improving performance of a generative model using feedback from other dependent generative models},booktitle={Thirty-Sixth AAAI Conference on Artificial Intelligence},address={Vancouver, BC, Canada},author={Chen, Changyu and Bose, Avinandan and Cheng, Shih-Fen and Sinha, Arunesh},year={2022},month=feb,smu={6792}}
2021
ICSS-21
Integrating empirical analysis into analytical framework: An integrated model structure for on-demand transportation
Yuliu
Su, Ying
Xu, Costas
Courcoubetis, and Shih-Fen
Cheng
In 2021 INFORMS Conference on Service Science, May 2021
On-demand transportation services have been developing in an irresistible trend since their first launch in public. These services not only transform the urban mobility landscape, but also profoundly change individuals’ travel behavior. In this paper, we propose an integrated model structure which integrates empirical analysis into a discrete choice based analytical framework to investigate a heterogeneous population’s choices on ownership, usage and transportation mode with the presence of ride-hailing. Distinguished from traditional discrete choice models where individuals’ choices are only affected by exogenous variables and are independent of other individuals’ choices, our model extends to capture the endogeneity of supply demand imbalance between ride-hailing service providers and users. Through equilibrium searching and counterfactual analysis, we further quantify the magnitude of impacts of platform operations and government policies on car demand, usage and traffic. The structure of the model and managerial insights are explained in detail.
@inproceedings{su_icss_2021,title={Integrating empirical analysis into analytical framework: An integrated model structure for on-demand transportation},booktitle={2021 INFORMS Conference on Service Science},address={Virtual},author={Su, Yuliu and Xu, Ying and Courcoubetis, Costas and Cheng, Shih-Fen},year={2021},month=may,smu={6131}}
CASE-21
Automated taxi queue management at high-demand venues
Mengyu
Ji, and Shih-Fen
Cheng
In Seventeenth IEEE International Conference on Automation Science and Engineering, Aug 2021
In this paper, we seek to identify an effective management policy that could reduce supply-demand gaps at taxi queues serving high-density locations where demand surges frequently happen. Unlike current industry practice, which relies on broadcasting to attract taxis to come and serve the queue, we propose more proactive and adaptive approaches to handle demand surges. Our design objective is to reduce the cumulative supply-demand gaps as much as we could by sending notifications to individual taxis. To address this problem, we first propose a highly effective passenger demand prediction system that is based on the real-time flight arrival information. By monitoring cumulative passenger arrivals, and control for factors such as the flight’s departure cities, we demonstrate that a simple linear regression model can accurately predict the number of passengers joining taxi queues. We then propose an optimal control strategy based on a Markov Decision Process to model the decisions of notifying individual taxis that are at different distances away from the airport. By using a real-world dataset, we demonstrate that an accurate passenger demand prediction system is crucial to the effectiveness of taxi queue management. In our numerical studies based on the real-world data, we observe that our proposed approach of optimal control with demand predictions outperforms the same control strategy, yet with Poisson demand assumption, by 43%. Against the status quo, which has no external control, we could reduce the gap by 23%. These results demonstrate that our proposed methodology has strong real-world potential.
@inproceedings{ji_case_2021,title={Automated taxi queue management at high-demand venues},booktitle={Seventeenth IEEE International Conference on Automation Science and Engineering},address={Lyon, France (Virtual)},author={Ji, Mengyu and Cheng, Shih-Fen},year={2021},month=aug,smu={6209}}
CASE-21
A Lagrangian column generation approach for the probabilistic crowdsourced logistics planning
In recent years we have increasingly seen the movement for the retail industry to move their operations online. Along the process, it has created brand new patterns for the fulfillment service, and the logistics service providers serving these retailers have no choice but to adapt. The most challenging issues faced by all logistics service providers are the highly fluctuating demands and the shortening response times. All these challenges imply that maintaining a fixed fleet will either be too costly or insufficient. One potential solution is to tap into the crowdsourced workforce. However, existing industry practices of relying on human planners or worker’s self-planning have been shown to be inefficient and laborious. In this paper, we introduce a centralized planning model for the crowdsourced logistics delivery paradigm, considering individual worker’s spatio-temporal preferences. Considering worker’s spatio-temporal preferences is important for the planner as it could significantly improve crowdsourced worker’s productivity. Our major contributions are in the formulation of the problem as a mixed-integer program and the proposal of an efficient algorithm that is based on the column generation and the Lagrangian relaxation frameworks. Such a hybrid approach allows us to overcome the difficulty encountered separately by the classical column generation and Lagrangian relaxation approaches. By using a series of real-world-inspired numerical instances, we have demonstrated the effectiveness of our approach against classical column generation and Lagrangian relaxation approaches, and a decentralized, agent-centric greedy approach. Our proposed hybrid approach is scalable to large problem instances, with reasonable solution quality, and achieves better allocation fairness.
@inproceedings{han_case_2021,title={A Lagrangian column generation approach for the probabilistic crowdsourced logistics planning},booktitle={Seventeenth IEEE International Conference on Automation Science and Engineering},address={Lyon, France (Virtual)},author={Han, Chung-Kyun and Cheng, Shih-Fen},year={2021},month=aug,smu={6210}}
AAMAS-21
Adaptive operating hours for improved performance of taxi fleets
Taxi fleets and car aggregation systems are an important component of the urban public transportation system. Taxis and cars in taxi fleets and car aggregation systems (e.g., Uber) are dependent on a large number of self-controlled and profit-driven taxi drivers, which introduces inefficiencies in the system. There are two ways in which taxi fleet performance can be optimized: (i) Operational decision making: improve assignment of taxis/cars to customers, while accounting for future demand; (ii) strategic decision making: optimize operating hours of (taxi and car) drivers. Existing research has primarily focused on the operational decisions in (i) and we focus on the strategic decisions in (ii).We first model this complex real-world decision making problem (with thousands of taxi drivers) as a multi-stage stochastic congestion game with a non-dedicated set of agents (i.e., agents start operation at a random stage and exit the game after a fixed time), where there is a dynamic population of agents (constrained by the maximum number of drivers). We provide planning and learning methods for computing the ideal operating hours in such a game, so as to improve efficiency of the overall fleet. In our experimental results, we demonstrate that our planning-based approach provides up to 16% improvement in revenue over existing method on a real-world taxi dataset. The learning-based approach further improves the performance and achieves up to 10% more revenue than the planning approach.
@inproceedings{kumar_aamas_2021,title={Adaptive operating hours for improved performance of taxi fleets},booktitle={Twentieth International Conference on Autonomous Agents and Multiagent Systems},address={London, UK (Virtual)},author={Kumar, Rajiv Ranjan and Varakantham, Pradeep and Cheng, Shih-Fen},year={2021},month=may,smu={6130}}
IJCAI-20
An exact single-agent task selection algorithm for the crowdsourced logistics
The trend of moving online in the retail industry has created great pressure for the logistics industry to catch up both in terms of volume and response time. On one hand, volume is fluctuating at greater magnitude, making peaks higher; on the other hand, customers are also expecting shorter response time. As a result, logistics service providers are pressured to expand and keep up with the demands. Expanding fleet capacity, however, is not sustainable as capacity built for the peak seasons would be mostly vacant during ordinary days. One promising solution is to engage crowdsourced workers, who are not employed full-time but would be willing to help with the deliveries if their schedules permit. The challenge, however, is to choose appropriate sets of tasks that would not cause too much disruption from their intended routes, while satisfying each delivery task’s delivery time window requirement. In this paper, we propose a decision-support algorithm to select delivery tasks for a single crowdsourced worker that best fit his/her upcoming route both in terms of additional travel time and the time window requirements at all stops along his/her route, while at the same time satisfies tasks’ delivery time windows. Our major contributions are in the formulation of the problem and the design of an efficient exact algorithm based on the branch-and-cut approach. The major innovation we introduce is the efficient generation of promising valid inequalities via our separation heuristics. In all numerical instances we study, our approach manages to reach optimality yet with much fewer computational resource requirement than the plain integer linear programming formulation. The greedy heuristic, while efficient in time, only achieves around 40-60% of the optimum in all cases. To illustrate how our solver could help in advancing the sustainability objective, we also quantify the reduction in the carbon footprint.
@inproceedings{han_ijcai_2020,title={An exact single-agent task selection algorithm for the crowdsourced logistics},booktitle={Twenty-Ninth International Joint Conference on Artificial Intelligence},address={Yokohama, Japan (Virtual)},author={Han, Chung-Kyun and Cheng, Shih-Fen},year={2021},month=jan,smu={5175}}
2020
CHIIR-20
PokeME: Applying context-driven notifications to increase worker engagement in mobile crowd-sourcing
In mobile crowd-sourcing systems, simply relying on people to opportunistically select and perform tasks typically leads to drawbacks such as low task acceptance/completion rates and undesirable spatial skews. In this paper, we utilize data from "Smart Campus", a campus-based mobile crowd-sourcing platform, to empirically study and discover whether and how various context-aware notification strategies can help overcome such drawbacks. We first study worker interactions, in the absence of any notifications, to discover some spatio-temporal properties of task acceptance and completion. Based on these insights, we then experimentally demonstrate the effectiveness of two novel, non-personal, context-driven notification strategies, comparing the outcomes to two different baselines (no-notification and random-notification). Finally, using the data from the random-notification mechanism, we derive a classification model, incorporating several novel contextual features, that can predict a worker’s responsiveness to notifications with high accuracy. Our work extends the crowd-sourcing literature by emphasizing the power of smart notifications for greater worker engagement.
@inproceedings{kandappu_chiir_2020,title={PokeME: Applying context-driven notifications to increase worker engagement in mobile crowd-sourcing},booktitle={Fifth ACM SIGIR Conference on Human Information Interaction and Retrieval},address={Vancouver, Canada (Virtual)},author={Kandappu, Thivya and Mehrotra, Abhinav and Misra, Archan and Musolesi, Mirco and Cheng, Shih-Fen and Meegahapola, Lakmal Buddika},year={2020},month=mar,smu={5109}}
The arrangement of last-mile services is playing an increasingly important role in making public transport more accessible. We study the use of ridesharing in satisfying last-mile demands with the assumption that demands are uncertain and come in batches. The most important contribution of our paper is a two-level Markov decision process framework that is capable of generating a vehicle-dispatching policy for the aforementioned service. We introduce state summarization, representative states, and sample-based cost estimation as major approximation techniques in making our approach scalable. We show that our approach converges and solution quality improves as sample size increases. We also apply our approach to a series of case studies derived from a real-world public transport data set in Singapore. By examining three distinctive demand profiles, we show that our approach performs best when the distribution is less uniform and the planning area is large. We also demonstrate that a parallel implementation can further improve the performance of our solution approach.
@article{agussurja_ts_2019,title={A state aggregation approach for stochastic multi-period last-mile ride-sharing problem},volume={53(1)},pages={148--166},journal={Transportation Science},author={Agussurja, Lucas and Cheng, Shih-Fen and Lau, Hoong Chuin},year={2019},smu={4326},}
AAMAS-19
A homophily-free community detection framework for trajectories with delayed responses
Community detection has been widely studied in the areas of social network analysis and recommendation system. However, most existing research focus on cases where relationships are explicit or depend on simultaneous appearance. In this paper, we propose to study the community detection problem where the relationships are not based on simultaneous appearance, but time-delayed appearances. In other words, we aim to capture the relationship where one individual physically follows another individual. In our attempt to capture such relationships, the major challenge is the presence of spatial homophily, i.e., individuals are attracted to locations due to their popularities and not because of communications. In tackling the community detection problem with spatial homophily and delayed responses, we make the following key contributions: (1) We introduce a four-phase framework, which by way of using quantified impacts excludes homophily. (2) To validate the framework, we generate a synthetic dataset based on a known community structure and then infer that community structure. (3) Finally, we execute this framework on a real-world dataset with more than 6,000 taxis in Singapore. Our results are also compared to those of a baseline approach without homophily-elimination.
@inproceedings{han_aamas_2019,title={A homophily-free community detection framework for trajectories with delayed responses},booktitle={Eighteenth International Conference on Autonomous Agents and Multiagent Systems},address={Montreal, Canada},author={Han, Chung-Kyun and Cheng, Shih-Fen and Varakantham, Pradeep},year={2019},month=may,smu={4798}}
By effectively reaching out to and engaging larger population of mobile users, mobile crowd-sourcing has become a strategy to perform large amount of urban tasks. The recent empirical studies have shown that compared to the pull-based approach, which expects the users to browse through the list of tasks to perform, the push-based approach that actively recommends tasks can greatly improve the overall system performance. As the efficiency of the push-based approach is achieved by incorporating worker’s mobility traces, privacy is naturally a concern. In this paper, we propose a novel, 2-stage and user-controlled obfuscation technique that provides a trade off-amenable framework that caters to multi-attribute privacy measures (considering the per-user sensitivity and global uniqueness of locations). We demonstrate the effectiveness of our approach by testing it using the real-world data collected from the well-established TA$Ker platform. More specifically, we show that one can increase its location entropy by 23% with only modest changes to the real trajectories while imposing an additional 24% (< 1 min) of detour overhead on average. Finally, we present insights derived by carefully inspecting various parameters that control the whole obfuscation process.
@article{kandappu_imwut_2018,author={Kandappu, Thivya and Misra, Archan and Cheng, Shih-Fen and Tandriansyah, Randy and Lau, Hoong Chuin},title={Obfuscation at-source: Privacy in context-aware mobile crowd-sourcing},journal={Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies},volume={2(1):16},pages={1--24},year={2018},smu={3976}}
In this article, we investigate effective ways of utilizing crowdworkers in providing various urban services. The task recommendation platform that we design can match tasks to crowdworkers based on workers’ historical trajectories and time budget limits, thus making recommendations personal and efficient. One major challenge we manage to address is the handling of crowdworker’s trajectory uncertainties. In this article, we explicitly allow multiple routine routes to be probabilistically associated with each worker. We formulate this problem as an integer linear program whose goal is to maximize the expected total utility achieved by all workers. We further exploit the separable structures of the formulation and apply the Lagrangian relaxation technique to scale up computation. Numerical experiments have been performed over the instances generated using the realistic public transit dataset in Singapore. The results show that we can find significantly better solutions than the deterministic formulation, and in most cases we can find solutions that are very close to the theoretical performance limit. To demonstrate the practicality of our approach, we deployed our recommendation engine to a campus-scale field trial, and we demonstrate that workers receiving our recommendations incur fewer detours and complete more tasks, and are more efficient against workers relying on their own planning (25% more for top workers who receive recommendations). This is achieved despite having highly uncertain worker trajectories. We also demonstrate how to further improve the robustness of the system by using a simple multi-coverage mechanism.
@article{cheng_tist_2018,author={Cheng, Shih-Fen and Chen, Cen and Kandappu, Thivya and Lau, Hoong Chuin and Misra, Archan and Jaiman, Nikita and Tandriansyah, Randy and Koh, Desmond},title={Scalable urban mobile crowdsourcing: Handling uncertainty in worker movement},journal={ACM Transactions on Intelligent Systems and Technology},volume={9(3):26},pages={1--24},year={2018},smu={3888}}
ICPADS-18
Mobility-driven BLE transmit-power adaptation for participatory data muling
This paper analyzes a human-centric framework, called SmartABLE, for easy retrieval of the sensor values from pervasively deployed smart objects in a campus-like environment. In this framework, smartphones carried by campus occupants act as data mules, opportunistically retrieving data from nearby BLE (Bluetooth Low Energy) equipped smart object sensors and relaying them to a backend repository. We focus specifically on dynamically varying the transmission power of the deployed BLE beacons, so as to extend their operational lifetime without sacrificing the frequency of sensor data retrieval. We propose a memetic algorithm-based power adaptation strategy that can handle deployments of thousands of beacons and tackles two distinct objectives: (1) maximizing BLE beacon lifetime, and (2) reducing the BLE scanning energy of the mules. Using real-world movement traces on the Singapore Management University campus, we show that the benefit of such mule movement-aware power adaptation: it provides reliably frequent retrieval of BLE sensor data, while achieving a significant (5-fold) increase in the sensor lifetime, compared to a traditional fixed-power approach.
@inproceedings{han_icpads_2018,title={Mobility-driven BLE transmit-power adaptation for participatory data muling},booktitle={IEEE Twenty-Fourth International Conference on Parallel and Distributed Systems},address={Singapore},author={Han, Chung-Kyun and Misra, Archan and Cheng, Shih-Fen},year={2018},month=dec,smu={4263}}
AAMAS-18
Taxis strike back: A field trial of the driver guidance system
Shih-Fen
Cheng, Shashi Shekhar
Jha, and Rishikeshan
Rajendram
In Seventeenth International Conference on Autonomous Agents and Multiagent Systems, May 2018
Traditional taxi fleet operators world-over have been facing intense competitions from various ride-hailing services such as Uber and Grab (specific to the Southeast Asia region). Based on our studies on the taxi industry in Singapore, we see that the emergence of Uber and Grab in the ride-hailing market has greatly impacted the taxi industry: the average daily taxi ridership for the past two years has been falling continuously, by close to 20% in total. In this work, we discuss how efficient real-time data analytics and large-scale multi-agent optimization technology could potentially help taxi drivers compete against more technologically advanced service platforms.
@inproceedings{cheng_aamas_2018,title={Taxis strike back: A field trial of the driver guidance system},booktitle={Seventeenth International Conference on Autonomous Agents and Multiagent Systems},address={Stockholm, Sweden},author={Cheng, Shih-Fen and Jha, Shashi Shekhar and Rajendram, Rishikeshan},year={2018},month=may,smu={4117}}
AAMAS-18
A driver guidance system for taxis in Singapore
Shashi Shekhar
Jha, Shih-Fen
Cheng, Rishikeshan
Rajendram, Nicholas
Wong, Firmansyah Bin Abd
Rahman, Nghia Truong
Trong, Meghna
Lowalekar, and
Pradeep Varakantham
In Seventeenth International Conference on Autonomous Agents and Multiagent Systems, May 2018
Traditional taxi fleet operators world-over have been facing intense competitions from various ride-hailing services such as Uber and Grab.Based on our studies on the taxi industry in Singapore, we see that the emergence of Uber and Grab in the ride-hailing market has greatly impacted the taxi industry: the average daily taxi ridership for the past two years has been falling continuously, by close to 20% in total. In this work, we discuss how efficient real-time data analytics and large-scale multiagent optimization technology could help taxi drivers compete against more technologically advanced service platforms. Our system has been in field trial with close to 400 drivers, and our initial results show that by following our recommendations, drivers on average save 21.5% on roaming time.
@inproceedings{jha_aamas_2018,author={Jha, Shashi Shekhar and Cheng, Shih-Fen and Rajendram, Rishikeshan and Wong, Nicholas and Rahman, Firmansyah Bin Abd and Trong, Nghia Truong and Lowalekar, Meghna and and Pradeep Varakantham},title={A driver guidance system for taxis in Singapore},booktitle={Seventeenth International Conference on Autonomous Agents and Multiagent Systems},address={Stockholm, Sweden},year={2018},month=may,smu={4118}}
IAAI-18
Upping the game of taxi driving in the age of Uber
Shashi Shekhar
Jha, Shih-Fen
Cheng, Meghna
Lowalekar, Nicholas
Wong, Rishikeshan
Rajendram, Tran Trong
Khiem, Pradeep
Varakantham, Truong Trong
Nghia, and Firmansyah
Rahman
In Thirtieth Annual Conference on Innovative Applications of Artificial Intelligence, Feb 2018
In most cities, taxis play an important role in providing point-to-point transportation service. If the taxi service is reliable, responsive, and cost-effective, past studies show that taxi-like services can be a viable choice in replacing a significant amount of private cars. However, making taxi services efficient is extremely challenging, mainly due to the fact that taxi drivers are self-interested and they operate with only local information. Although past research has demonstrated how recommendation systems could potentially help taxi drivers in improving their performance, most of these efforts are not feasible in practice. This is mostly due to the lack of both the comprehensive data coverage and an efficient recommendation engine that can scale to tens of thousands of drivers. In this paper, we propose a comprehensive working platform called the Driver Guidance System (DGS). With real-time citywide taxi data provided by our collaborator in Singapore, we demonstrate how we can combine real-time data analytics and large-scale optimization to create a guidance system that can potentially benefit tens of thousands of taxi drivers. Via a realistic agent-based simulation, we demonstrate that drivers following DGS can significantly improve their performance over ordinary drivers, regardless of the adoption ratios. We have concluded our system designing and building and have recently entered the field trial phase.
@inproceedings{jha_iaai_2018,title={Upping the game of taxi driving in the age of Uber},booktitle={Thirtieth Annual Conference on Innovative Applications of Artificial Intelligence},address={New Orleans, Louisiana, USA},author={Jha, Shashi Shekhar and Cheng, Shih-Fen and Lowalekar, Meghna and Wong, Nicholas and Rajendram, Rishikeshan and Khiem, Tran Trong and Varakantham, Pradeep and Nghia, Truong Trong and Rahman, Firmansyah},year={2018},month=feb,smu={3952}}
2017
CASPer-17
Privacy in context-aware mobile crowdsourcing systems
In Fourth International Workshop on Crowd Assisted Sensing, Pervasive Systems and Communications at Fifteenth IEEE International Conference on Pervasive Computing and Communications, Mar 2017
Mobile crowd-sourcing can become as a strategy to perform time-sensitive urban tasks (such as municipal monitoring and last mile logistics) by effectively coordinating smartphone users. The success of the mobile crowd-sourcing platform depends mainly on its effectiveness in engaging crowd-workers, and recent studies have shown that compared to the pull-based approach, which relies on crowd-workers to browse and commit to tasks they would want to perform, the push-based approach can take into consideration of worker’s daily routine, and generate highly effective recommendations. As a result, workers waste less time on detours, plan more in advance, and require much less planning effort. However, the push-based systems are not without drawbacks. The major concern is the potential privacy invasion that could result from the disclosure of individual’s mobility traces to the crowd-sourcing platform. In this paper, we first demonstrate specific threats of continuous sharing of users locations in such push-based crowd-sourcing platforms. We then propose a simple yet effective location perturbation technique that obfuscates certain user locations to achieve privacy guarantees while not affecting the quality of the recommendations the system generates.We use the mobility traces data we obtained from our urban campus to show the trade-offs between privacy guarantees and the quality of the recommendations associated with the proposed solution. We show that obfuscating even 75% of the individual trajectories will affect the user to make another extra 1.8 minutes of detour while gaining 62.5% more uncertainty of his location traces.
@inproceedings{kandappu_casper_2017,author={Kandappu, Thivya and Misra, Archan and Cheng, Shih-Fen and Lau, Hoong Chuin},title={Privacy in context-aware mobile crowdsourcing systems},booktitle={Fourth International Workshop on Crowd Assisted Sensing, Pervasive Systems and Communications at Fifteenth IEEE International Conference on Pervasive Computing and Communications},address={Hawaii, USA},year={2017},month=mar,smu={3630}}
IEEE SSCI-17
Exact and heuristic approaches for the multi-agent orienteering problem with capacity constraints
This paper introduces and addresses a new multiagent variant of the orienteering problem (OP), namely the multi-agent orienteering problem with capacity constraints (MAOPCC). Different from the existing variants of OP, MAOPCC allows a group of visitors to concurrently visit a node but limits the number of visitors simultaneously being served at each node. In this work, we solve MAOPCC in a centralized manner and optimize the total collected rewards of all agents. A branch and bound algorithm is first proposed to find an optimal MAOPCC solution. Since finding an optimal solution for MAOPCC can become intractable as the number of vertices and agents increases, a computationally efficient sequential algorithm that sacrifices the solution quality is then proposed. Finally, a probabilistic iterated local search algorithm is developed to find a sufficiently good solution in a reasonable time. Our experimental results show that the latter strikes a good tradeoff between the solution quality and the computational time incurred.
@inproceedings{wang_ssci_2017,author={Wang, Wenjie and Lau, Hoong Chuin and Cheng, Shih-Fen},title={Exact and heuristic approaches for the multi-agent orienteering problem with capacity constraints},booktitle={2017 IEEE Symposium Series on Computational Intelligence},address={Hawaii, USA},year={2017},month=nov,smu={4019}}
Consolidation lies at the heart of the last-mile logistics problem. Urban consolidation centers (UCCs) have been set up to facilitate such consolidation all over the world. To the best of our knowledge, most-if not all-of the UCCs operate on volume-based fixed-rate charges. To achieve environmental sustainability while ensuring economic sustainability in urban logistics, we propose, in this paper, a bicriteria auction mechanism for the automated assignment of last-mile delivery orders to transport resources. We formulate and solve the winner determination problem of the auction as a biobjective programming model. We then present a systematic way to generate the Pareto frontier to characterize the tradeoff between achieving economic and environmental sustainabilities in urban logistics. Finally, we demonstrate that our proposed bicriteria auction produces the solutions that significantly dominate those obtained from the fixed-rate mechanisms. Our sensitivity analysis on the willingness of carriers to participate in the UCC operation reveals that higher willingness is favorable toward achieving greater good for all, if UCC is designed to be nonprofit and self-sustaining.Note to Practitioners-One of the main issues with last-mile logistics is the low utilization of delivery trucks, resulting in unnecessarily large number of trucks carrying out the last-mile delivery. This creates congestion, worsens air pollution, and drives up the cost of the individual carriers. Consolidation of orders can reduce the total number of trucks used to perform the last-mile delivery. This can considerably improve the environmental sustainability around the delivery area and reduce the cost of the individual carrier. Without the proper mechanism, however, such consolidation is often not economically sustainable, requiring the government to continually inject subsidy. To address the issue, we propose, in this paper, a bicriteria auction that considers both the economic and environmental sustainability aspects when performing winner determination. We then present a systematic way to characterize the tradeoff between the two objectives. Finally, we show that our proposal leads to the solutions that dominate those obtained from the commonly used fixed-rate mechanisms.
@article{Handoko_tase_2016,author={Handoko, Stephanus Daniel and Lau, Hoong Chuin and Cheng, Shih-Fen},title={Achieving economic and environmental sustainability in urban consolidation center with bi-criteria auction},journal={IEEE Transactions on Automation Science and Engineering},volume={13(4)},pages={1471--1479},year={2016},smu={3362}}
WSC-16
An agent-based approach to human migration movement
How are the populations of the world likely to shift? Which countries will be impacted by sea-level rise? This paper uses a country-level agent-based dynamic network model to examine shifts in population given network relations among countries, which influences overall population change. Some of the networks considered include: alliance networks, shared language networks, economic influence networks, and proximity networks. Validation of model is done for migration probabilities between countries, as well as for country populations and distributions. The proposed framework provides a way to explore the interaction between climate change and policy factors at a global scale.
@inproceedings{lin_wsc_2016,author={Lin, Larry and Carley, Kathleen M. and Cheng, Shih-Fen},title={An agent-based approach to human migration movement},booktitle={2016 Winter Simulation Conference},address={Arlington, VA, USA},year={2016},month=dec,smu={3337}}
WSC-16
Managing egress of crowd during infrastructure disruption
Teck-Hou
Teng, Shih-Fen
Cheng, Trong Nghia
Truong, and Hoong Chuin
Lau
In a large indoor environment such as a sports arena or convention center, smooth egress of crowd after an event can be seriously affected if infrastructure such as elevators and escalators break down. In this paper, we propose a novel crowd simulator known as SIM-DISRUPT for simulating egress scenarios in non-emergency situations. To surface the impact of disrupted infrastructure on the egress of crowd, SIM-DISRUPT includes features that allow users to specify selective disruptions as well as strategies for controlling the distribution and egress choices of crowd. Using SIM-DISRUPT, we investigate effects of crowd distribution, egress choices and infrastructure disruptions on crowd egress time and measure efficacies of different egress strategies under various infrastructure disruption scenarios. A real-world inspired use case is used to demonstrate the usefulness of SIM-DISRUPT in planning egress under various operational conditions.
@inproceedings{teng_wsc_2016,author={Teng, Teck-Hou and Cheng, Shih-Fen and Truong, Trong Nghia and Lau, Hoong Chuin},title={Managing egress of crowd during infrastructure disruption},booktitle={2016 Winter Simulation Conference},address={Arlington, VA, USA},year={2016},month=dec,smu={3336}}
UbiComp-16
TASKer: Behavioral insights via campus-based experimental mobile crowd-sourcing
Thivya
Kandappu, Nikita
Jaiman, Randy
Tandriansyah, Archan
Misra, Shih-Fen
Cheng, Cen
Chen, Hoong Chuin
Lau, Deepthi
Chander, and Koustuv
Dasgupta
In 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing, Sep 2016
While mobile crowd-sourcing has become a game-changer for many urban operations, such as last mile logistics and municipal monitoring, we believe that the design of such crowdsourcing strategies must better accommodate the real-world behavioral preferences and characteristics of users. To provide a real-world testbed to study the impact of novel mobile crowd-sourcing strategies, we have designed, developed and experimented with a real-world mobile crowd-tasking platform on the SMU campus, called TAKer. We enhanced the TAKer platform to support several new features (e.g., task bundling, differential pricing and cheating analytics) and experimentally investigated these features via a two-month deployment of TA$Ker, involving 900 real users on the SMU campus who performed over 30,000 tasks. Our studies (i) show the benefits of bundling tasks as a combined package, (ii) reveal the effectiveness of differential pricing strategies and (iii) illustrate key aspects of cheating (false reporting) behavior observed among workers.
@inproceedings{kandappu_ubicomp_2016,author={Kandappu, Thivya and Jaiman, Nikita and Tandriansyah, Randy and Misra, Archan and Cheng, Shih-Fen and Chen, Cen and Lau, Hoong Chuin and Chander, Deepthi and Dasgupta, Koustuv},title={TASKer: Behavioral insights via campus-based experimental mobile crowd-sourcing},booktitle={2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing},address={Heidelberg, Germany},year={2016},month=sep,smu={3361}}
AAAI-16
Achieving stable and fair profit allocation with minimum subsidy in collaborative logistics
With the advent of e-commerce, logistics providers are faced with the challenge of handling fluctuating and sparsely distributed demand, which raises their operational costs significantly. As a result, horizontal cooperation are gaining momentum around the world. One of the major impediments, however, is the lack of stable and fair profit sharing mechanism. In this paper, we address this problem using the framework of computational cooperative games. We first present cooperative vehicle routing game as a model for collaborative logistics operations. Using the axioms of Shapley value as the conditions for fairness, we show that a stable, fair and budget balanced allocation does not exist in many instances of the game. By relaxing budget balance, we then propose an allocation scheme based on the normalized Shapley value. We show that this scheme maintains stability and fairness while requiring minimum subsidy. Finally, using numerical experiments we demonstrate the feasibility of the scheme under various settings.
@inproceedings{agussurja_aaai_2016,author={Agussurja, Lucas and Lau, Hoong Chuin and Cheng, Shih-Fen},title={Achieving stable and fair profit allocation with minimum subsidy in collaborative logistics},booktitle={Thirtieth AAAI Conference on Artificial Intelligence},address={Phoenix, AZ, USA},year={2016},month=feb,smu={3343}}
CSCW-16
Campus-scale mobile crowd-tasking: Deployment and behavioral insights
Thivya
Kandappu, Archan
Misra, Shih-Fen
Cheng, Nikita
Jaiman, Randy
Tandriansyah, Cen
Chen, Hoong Chuin
Lau, Deepthi
Chander, and Koustuv
Dasgupta
In Nineteenth ACM Conference on Computer-Supported Cooperative Work and Social Computing, Feb 2016
Honorable mention for the Best Paper Award (top 5% of all papers).
Mobile crowd-tasking markets are growing at an unprecedented rate with increasing number of smartphone users. Such platforms differ from their online counterparts in that they demand physical mobility and can benefit from smartphone processors and sensors for verification purposes. Despite the importance of such mobile crowd-tasking markets, little is known about the labor supply dynamics and mobility patterns of the users. In this paper we design, develop and experiment with a realwporld mobile crowd-tasking platform, called TAKer. Our contributions are two-fold: (a) We develop TAKer, a system that allows us to empirically study the worker responses to push vs. pull strategies for task recommendation and selection. (b) We evaluate our system via experimentation with 80 real users on our campus, over a 4 week period with a corpus of over 1000 tasks. We then provide an in-depth analysis of labor supply, worker behavior & task selection preferences (including the phenomenon of super agents who complete large portions of the tasks) and the efficacy of pushbased approaches that recommend tasks based on predicted movement patterns of individual workers.
@inproceedings{kandappu_cscw_2016,author={Kandappu, Thivya and Misra, Archan and Cheng, Shih-Fen and Jaiman, Nikita and Tandriansyah, Randy and Chen, Cen and Lau, Hoong Chuin and Chander, Deepthi and Dasgupta, Koustuv},title={Campus-scale mobile crowd-tasking: Deployment and behavioral insights},booktitle={Nineteenth ACM Conference on Computer-Supported Cooperative Work and Social Computing},address={San Francisco, CA, USA},year={2016},month=feb,smu={3181}}
2015
WSC-15
Building crowd movement model using sample-based mobility survey
Crowd simulation is a well-studied topic, yet it usually focuses on visualization. In this paper, we study a special class of crowd simulation, where individual agents have diverse backgrounds, ad hoc objectives, and non-repeating visits. Such crowd simulation is particularly useful when modeling human agents movement in leisure settings such as visiting museums or theme parks. In these settings, we are interested in accurately estimating aggregate crowd-related movement statistics. As comprehensive monitoring is usually not feasible for a large crowd, we propose to conduct mobility surveys on only a small group of sampled individuals. We demonstrate via simulation that we can effectively predict agents’ aggregate behaviors, even when the agent types are uncertain, and the sampling rate is as low as 1%. Our findings concur with prior studies in urban transportation, and show that sampled-based mobility survey would be a promising approach for improving the accuracy of crowd simulations.
@inproceedings{lin_wsc_2015,author={Lin, Larry and Cheng, Shih-Fen and Lau, Hoong Chuin},title={Building crowd movement model using sample-based mobility survey},booktitle={2015 Winter Simulation Conference},address={Huntington Beach, CA, USA},year={2015},month=dec,smu={2902}}
IAT-15
Learning and controlling network diffusion in dependent cascade models
Diffusion processes have increasingly been used to represent flow of ideas, traffic and diseases in networks. Learning and controlling the diffusion dynamics through management actions has been studied extensively in the context of independent cascade models, where diffusion on outgoing edges from a node are independent of each other. Our work, in contrast, addresses (a) learning diffusion taking management actions to alter the diffusion dynamics to achieve a desired outcome in dependent cascade models. A key characteristic of such dependent cascade models is the flow preservation at all nodes in the network. For example, traffic and people flow is preserved at each network node. As a case study, we address learning visitor mobility pattern at a theme park based on observed historical wait times at individual attractions, and use the learned model to plan management actions that reduce wait time at attractions. We test on real-world data from a theme park in Singapore and show that our learning approach can achieve an accuracy close to 80% for popular attractions, and the decision support algorithm can provide about 10-20% reduction in wait time.
@inproceedings{du_iat_2015,author={Du, Jiali and Varakantham, Pradeep and Kumar, Akshat and Cheng, Shih-Fen},title={Learning and controlling network diffusion in dependent cascade models},booktitle={2015 IEEE/WIC/ACM International Conference on Intelligent Agent Technology},address={Singapore},year={2015},month=dec,smu={2928}}
ITSC-15
Density peaks clustering approach for discovering demand hot spots in city-scale taxi fleet dataset
Dongchang
Liu, Shih-Fen
Cheng, and Yiping
Yang
In Eighteenth IEEE International Conference on Intelligent Transportation Systems, Sep 2015
In this paper, we introduce a variant of the density peaks clustering (DPC) approach for discovering demand hot spots from a low-frequency, low-quality taxi fleet operational dataset. From the literature, the DPC approach mainly uses density peaks as features to discover potential cluster centers, and this requires distances between all pairs of data points to be calculated. This implies that the DPC approach can only be applied to cases with relatively small numbers of data points. For the domain of urban taxi operations that we are interested in, we could have millions of demand points per day, and calculating all-pair distances between all demand points would be practically impossible, thus making DPC approach not applicable. To address this issue, we project all points to a density image and execute our variant of the DPC algorithm on the processed image. Experiment results show that our proposed DPC variant could get similar results as original DPC, yet with much shorter execution time and lower memory consumption. By running our DPC variant on a real-world dataset collected in Singapore, we show that there are indeed recurrent demand hot spots within the central business district that are not covered by the current taxi stand design. Our approach could be of use to both taxi fleet operator and traffic planners in guiding drivers and setting up taxi stands.
@inproceedings{liu_itsc_2015,author={Liu, Dongchang and Cheng, Shih-Fen and Yang, Yiping},title={Density peaks clustering approach for discovering demand hot spots in city-scale taxi fleet dataset},booktitle={Eighteenth IEEE International Conference on Intelligent Transportation Systems},address={Canary Islands, Spain},year={2015},month=sep,smu={2930}}
ICCL-15
Designing bus bridging services for regular egress
We are concerned with the routine crowd management problem after a major event at a known venue. Without properly design complementary transport services, such sudden crowd build-ups will overwhelm the existing infrastructure. In this paper, we introduce a novel flow-rate based model to model the dynamic movement of passengers over the transportation flow network. Based on this basic model, an integer linear programming model is proposed to solve the bus transit problem permanently. We validate our model against a real scenario in Singapore, where a newly constructed mega-stadium hosts various large events regularly. The results show that the proposed approach effectively enables routine crowd, and achieves almost 24.1% travel time reduction with an addition of 40 buses serving 18.7% of the passengers.
@inproceedings{du_iccl_2015,author={Du, Jiali and Cheng, Shih-Fen and Lau, Hoong Chuin},title={Designing bus bridging services for regular egress},booktitle={Sixth International Conference on Computational Logistics},address={Delft, The Netherlands},year={2015},month=sep,smu={2796}}
IJCAI-15
Towards city-scale mobile crowdsourcing: Task recommendations under trajectory uncertainties
In this work, we investigate the problem of large-scale mobile crowdsourcing, where workers are financially motivated to perform location-based tasks physically. Unlike current industry practice that relies on workers to manually pick tasks to perform, we automatically make task recommendation based on workers’ historical trajectories and desired time budgets. The challenge of predicting workers’ trajectories is that it is faced with uncertainties, as a worker does not take same routes every day. In this work, we depart from deterministic modeling and study the stochastic task recommendation problem where each worker is associated with several predicted routine routes with probabilities. We formulate this problem as a stochastic integer linear program whose goal is to maximize the expected total utility achieved by all workers. We further exploit the separable structures of the formulation and apply the Lagrangian relaxation technique to scale up computation. Experiments have been performed over the instances generated using the real Singapore transportation network. The results show that we can find significantly better solutions than the deterministic formulation.
@inproceedings{chen_ijcai_2015,author={Chen, Cen and Cheng, Shih-Fen and Lau, Hoong Chuin and Misra, Archan},title={Towards city-scale mobile crowdsourcing: Task recommendations under trajectory uncertainties},booktitle={Twenty-Fourth International Joint Conference on Artificial Intelligence},address={Beunos Aires, Argentina},year={2015},month=aug,smu={2815}}
AAMAS-15
Multi-agent task assignment for mobile crowdsourcing under trajectory uncertainties
In this work, we investigate the problem of mobile crowdsourcing, where workers are financially motivated to perform location-based tasks physically. Unlike current industry practice that relies on workers to manually browse and filter tasks to perform, we intend to automatically make task recommendations based on workers’ historical trajectories and desired time budgets. However, predicting workers’ trajectories is inevitably faced with uncertainties, as no one will take exactly the same route every day; yet such uncertainties are oftentimes abstracted away in the known literature. In this work, we depart from the deterministic modeling and study the stochastic task recommendation problem where each worker is associated with several predicted routine routes with probabilities. We formulate this problem as a stochastic integer linear program whose goal is to maximize the expected total utility achieved by all workers. We further exploit the separable structure of the formulation and apply the Lagrangian relaxation technique to scale up the solution approach. Experiments have been performed over the instances generated using the real Singapore transportation network. The results show that we can find significantly better solutions than the deterministic formulation.
@inproceedings{chen_aamas_2015,author={Chen, Cen and Cheng, Shih-Fen and Lau, Hoong Chuin and Misra, Archan},title={Multi-agent task assignment for mobile crowdsourcing under trajectory uncertainties},booktitle={Fourteenth International Conference on Autonomous Agents and Multi-Agent Systems},address={Istanbul, Turkey},year={2015},month=may,smu={2674}}
In this paper, we formulate and study the Multi-agent Orienteering Problem with Time-dependent Capacity Constraints (MOPTCC). MOPTCC is similar to the classical orienteering problem at single-agent level: given a limited time budget, an agent travels around the network and collects rewards by visiting different nodes, with the objective of maximizing the sum of his collected rewards. The most important feature we introduce in MOPTCC is the inclusion of multiple competing agents. All agents in MOPTCC are assumed to be self-interested, and they interact with each other when arrive at certain nodes simultaneously. As all nodes are capacitated, if a particular node receives more agents than its capacity, all agents at that node will be made to wait and agents suffer as a result (in terms of extra time needed for queueing). Due to the decentralized nature of the problem, MOPTCC cannot be solved in a centralized manner, instead, we need to seek out equilibrium solutions, and if not possible, at least approximated equilibrium solutions. The major contribution of this paper is the formulation of the problem, and our first attempt in identifying an efficient and effective equilibrium-seeking procedure for MOPTCC.
@article{chen_wias_2014,author={Chen, Cen and Cheng, Shih-Fen and Lau, Hoong Chuin},title={Multi-agent orienteering problem with time-dependent capacity constraints},journal={Web Intelligence and Agent Systems},volume={12},pages={347--358},year={2014},smu={2261}}
We introduce a class of finite-horizon dynamic optimization problems that we call multi-action stochastic dynamic programs (DPs). Their distinguishing feature is that the decision in each state is a multi-dimensional vector. These problems can in principle be solved using Bellman’s backward recursion. However, complexity of this procedure grows exponentially in the dimension of the decision vectors. This is called the curse of action-space dimensionality. To overcome this computational challenge, we propose an approximation algorithm rooted in the game theoretic paradigm of Sampled Fictitious Play (SFP). SFP solves a sequence of DPs with a one-dimensional action-space, which are exponentially smaller than the original multi-action stochastic DP. In particular, the computational effort in a fixed number of SFP iterations is linear in the dimension of the decision vectors. We show that the sequence of SFP iterates converges to a local optimum, and present a numerical case study in manufacturing where SFP is able to find solutions with objective values within 1% of the optimal objective value hundreds of times faster than the time taken by backward recursion. In this case study, SFP solutions are also better by a statistically significant margin than those found by a one-step lookahead heuristic.
@article{ghate_iie_2014,author={Ghate, Archis and Cheng, Shih-Fen and Baumert, Stephen and Reaume, Daniel and Sharma, Dushyant and Smith, Robert L.},title={Sampled fictitious play for multi-action stochastic dynamic programs},journal={IIE Transactions},volume={46(7)},pages={742--756},year={2014},smu={1982}}
HCOMP-14
TRACCS: A framework for trajectory-aware coordinated urban crowd-sourcing
We investigate the problem of large-scale mobile crowd-tasking, where a large pool of citizen crowd-workers are used to perform a variety of location-specific urban logistics tasks. Current approaches to such mobile crowd-tasking are very decentralized: a crowd-tasking platform usually provides each worker a set of available tasks close to the worker’s current location; each worker then independently chooses which tasks she wants to accept and perform. In contrast, we propose TRACCS, a more coordinated task assignment approach, where the crowd-tasking platform assigns a sequence of tasks to each worker, taking into account their expected location trajectory over a wider time horizon, as opposed to just instantaneous location. We formulate such task assignment as an optimization problem, that seeks to maximize the total payoff from all assigned tasks, subject to a maximum bound on the detour (from the expected path) that a worker will experience to complete her assigned tasks. We develop credible computationally-efficient heuristics to address this optimization problem (whose exact solution requires solving a complex integer linear program), and show, via simulations with realistic topologies and commuting patterns, that a specific heuristic (called Greedy-ILS) increases the fraction of assigned tasks by more than 20%, and reduces the average detour overhead by more than 60%, compared to the current decentralized approach.
@inproceedings{chen_hcomp_2014,author={Chen, Cen and Cheng, Shih-Fen and Gunawan, Aldy and Misra, Archan and Dasgupta, Koustuv and Chander, Deepthi},title={TRACCS: A framework for trajectory-aware coordinated urban crowd-sourcing},booktitle={Second AAAI Conference on Human Computation and Crowdsourcing},address={Pittsburgh, PA, USA},year={2014},month=nov,smu={2254}}
AAMAS-14
Mechanisms for arranging ride sharing and fare splitting for last-mile travel demands
A great challenge of city planners is to provide efficient and effective connection service to travelers using public transportation system. This is commonly known as the last-mile problem and is critical in promoting the utilization of public transportation system. In this paper, we address the last-mile problem by considering a dynamic and demand-responsive mechanism for arranging ride sharing on a non-dedicated commercial fleet (such as taxis or passenger vans). Our approach has the benefits of being dynamic, flexible, and with low setup cost. A critical issue in such ride-sharing service is how riders should be grouped and serviced, and how fares should be split. We propose two auction designs which are used to solicit individual rider’s willing payment rate and compensation rate (for extra travel, if any). We demonstrate that these two auctions are budget balanced, individually rational, and incentive compatible. A series of experimental studies based on both synthetic and real-world datasets are designed to demonstrate the pros and cons of our two proposed auction mechanisms in various settings.
@inproceedings{cheng_aamas_2014,author={Cheng, Shih-Fen and Nguyen, Duc Thien and Lau, Hoong Chuin},title={Mechanisms for arranging ride sharing and fare splitting for last-mile travel demands},booktitle={Thirteenth International Conference on Autonomous Agents and Multi-Agent Systems},address={Paris, France},year={2014},month=may,smu={2010}}
In modern production systems, it is critical to perform maintenance, calibration, installation, and upgrade tasks during planned downtime. Otherwise, the systems become unreliable and new product introductions are delayed. For reasons of safety, testing, and access, task performance often requires the vicinity of impacted equipment to be left in a specific "end state" when production halts. Therefore, planning the shutdown of a production system to balance production goals against enabling non-production tasks yields a challenging optimization problem. In this paper, we propose a mathematical formulation of this problem and a dynamic programming approach that efficiently finds optimal shutdown policies for deterministic serial production lines. An event-triggered re-optimization procedure that is based on the proposed deterministic dynamic programming approach is also introduced for handling uncertainties in the production line for the stochastic case. We demonstrate numerically that in these cases with random breakdowns and repairs, the re-optimization procedure is efficient and even obtains results that are optimal or nearly optimal.
@article{cheng_iie_2013,author={Cheng, Shih-Fen and Nicholson, Blake and Epelman, Marina A. and Reaume, Daniel and Smith, Robert L.},title={A dynamic programming approach to achieving an optimal end state along a serial production line},journal={IIE Transactions},volume={45(12)},pages={1278--1292},year={2013},smu={1659}}
WSC-13
An agent-based simulation approach to experience management in theme parks
In this paper, we illustrate how massive agent-based simulation can be used to investigate an exciting new application domain of experience management in theme parks, which covers topics like congestion control, incentive design, and revenue management. Since all visitors are heterogeneous and self-interested, we argue that a high-quality agent-based simulation is necessary for studying various problems related to experience management. As in most agent-base simulations, a sound understanding of micro-level behaviors is essential to construct high-quality models. To achieve this, we designed and conducted a first-of-its-kind real-world experiment that helps us understand how typical visitors behave in a theme-park environment. From the data collected, visitor behaviors are quantified, modeled, and eventually incorporated into a massive agent-based simulation where up to 15,000 visitor agents are modeled. Finally, we demonstrate how our agent-based simulator can be used to understand the crowd build-up and the impacts of various control policies on visitor experience.
@inproceedings{cheng_wsc_2013,author={Cheng, Shih-Fen and Lin, Larry and Du, Jiali and Lau, Hoong Chuin and Varakantham, Pradeep},title={An agent-based simulation approach to experience management in theme parks},booktitle={2013 Winter Simulation Conference},address={Washington DC, USA},year={2013},month=dec,smu={1828}}
ADT-13
Budgeted personalized incentive approaches for smoothing out congestion in resource networks
Congestion occurs when there is competition for resources by sel sh agents. In this paper, we are concerned with smoothing out congestion in a network of resources by using personalized well-timed incentives that are subject to budget constraints. To that end, we provide: (i) a mathematical formulation that computes equilibrium for the re- source sharing congestion game with incentives and budget constraints; (ii) an integrated approach that scales to larger problems by exploiting the factored network structure and approximating the attained equilibrium; (iii) an iterative best response algorithm for solving the uncon- strained version (no budget) of the resource sharing congestion game; and (iv) theoretical and empirical results (on an illustrative theme park problem) that demonstrate the usefulness of our approach.
@inproceedings{varakantham_adt_2013,author={Varakantham, Pradeep and Fu, Na and Yeoh, William and Cheng, Shih-Fen and Lau, Hoong Chuin},title={Budgeted personalized incentive approaches for smoothing out congestion in resource networks},booktitle={Third International Conference on Algorithmic Decision Theory},address={Brussels, Belgium},year={2013},month=nov,smu={1888}}
IJCAI-13
A multi-objective memetic algorithm for vehicle resource allocation in sustainable transportation planning
Sustainable supply chain management has been an increasingly important topic of research in recent years. At the strategic level, there are computational models which study supply and distribution networks with environmental considerations. At the operational level, there are, for example, routing and scheduling models which are constrained by carbon emissions. Our paper explores work in tactical planning with regards to vehicle resource allocation from distribution centers to customer locations in a multi-echelon logistics network. We formulate the bi-objective optimization problem exactly and design a memetic algorithm to efficiently derive an approximate Pareto front. We illustrate the applicability of our approach with a large realworld dataset.
@inproceedings{lau_ijcai_2013,author={Lau, Hoong Chuin and Agussurja, Lucas and Cheng, Shih-Fen and Tan, Pang Jin},title={A multi-objective memetic algorithm for vehicle resource allocation in sustainable transportation planning},booktitle={Twenty-Third International Joint Conference on Artificial Intelligence},address={Beijing, China},year={2013},month=aug,smu={1814}}
The Orienteering Problem (OP), as originally defined by Tsiligirides, is the problem of cross-countr sport in which participants get rewards from visiting a predefined set of checkpoints. As Orienteering Problem can be used to describe a wide variety of real-world problems like route planning for facility inspection, patrolling of strategic location, and reward-weighted traveling salesman problem, it has attracted continuous interests from researchers and a large number of variants and corresponding algorithms for solving them have been introduced.
@inproceedings{chen_mic_2013,author={Chen, Cen and Cheng, Shih-Fen and Lau, Hoong Chuin},title={The multi-agent orienteering problem},booktitle={Tenth Metaheuristics International Conference},address={Singapore},year={2013},month=aug,smu={1887}}
MIC-13
Interacting knapsack problem in designing resource bundles
In many real-life businesses, the service provider/seller keeps a log of the visitors’ behavior as a way to assess the efficiency of the current business/operation model and find room for improvement. For example, by tracking when visitors entering attractions in a theme park, theme park owners can detect when and where congestion may occur, thus having contingency plans to reroute the visitors accordingly. Similarly, a Cable TV service provider can track channel switching events at each household to identify uninteresting channels. Subsequently, the repertoire of channels up for subscription can evolve over time to better serve the entertainment demand of subscribers. All tracking activities can be done anonymously so as to protect the customers’ privacy. Given a large amount of data about customer behavior, we would like to succinctly represent it so that insights can be inferred more quickly and conveniently.
@inproceedings{nguyen_mic_2013,author={Nguyen, Truong Huy and Varakantham, Pradeep and Lau, Hoong Chuin and Cheng, Shih-Fen},title={Interacting knapsack problem in designing resource bundles},booktitle={Tenth Metaheuristics International Conference},address={Singapore},year={2013},month=aug,smu={1886}}
2012
IAT-12
Lagrangian relaxation for large-scale multi-agent planning
Multi-agent planning is a well-studied problem with various applications including disaster rescue, urban transportation and logistics, both for autonomous agents and for decision support to humans. Due to computational constraints, existing research typically focuses on one of two scenarios: unstructured domains with many agents where we are content with heuristic solutions, or domains with small numbers of agents or special structure where we can provide provably near-optimal solutions. By contrast, in this paper, we focus on providing provably near-optimal solutions for domains with large numbers of agents, by exploiting a common domain-general property: if individual agents each have limited influence on the overall solution quality, then we can take advantage of randomization and the resulting statistical concentration to show that each agent can safely plan based only on the average behavior of the other agents. To that end, we make two key contributions: (a) an algorithm, based on Lagrangian relaxation and randomized rounding, for solving multi-agent planning problems represented as large mixed-integer programs, (b) a proof of convergence of our algorithm to a near-optimal solution. We demonstrate the scalability of our approach with a large-scale illustrative theme park crowd management problem.
@inproceedings{gordon_iat_2012,author={Gordon, Geoffrey J. and Varakantham, Pradeep and Yeoh, William and Lau, Hoong Chuin and Aravamudhan, Ajay S. and Cheng, Shih-Fen},title={Lagrangian relaxation for large-scale multi-agent planning},booktitle={2012 IEEE/WIC/ACM International Conference on Intelligent Agent Technology},address={Macau},year={2012},month=dec,smu={4364}}
The myth that financial trading is an art has been mostly destroyed in the recent decade due to the proliferation of algorithmic trading. In equity markets, algorithmic trading has already bypass human traders in terms of traded volume. This trend seems to be irreversible, and other asset classes are also quickly becoming dominated by the machine traders. However, for asset that requires deeper understanding of physicality, like the trading of commodities, human traders still have significant edge over machines. The primary advantage of human traders in such market is the qualitative expert knowledge that requires traders to consider not just the financial information, but also a wide variety of physical constraints and information. However, due to rapid technology changes and the "invasion" of cashrich hedge funds, even this traditionally human-centric asset class is crying for help in handling increasingly complicated and volatile environment. In this paper, we propose an adaptive trading support framework that allows us to quantify expert’s knowledge to help human traders. Our method is based on a two-state switching Kalman filter, which updates its state estimation continuously with real-time information. We demonstrate the effectiveness of our approach in palm oil trading, which is becoming more and more complicated in recent years due to its new usage in producing biofuel.We show that the two-state switching Kalman filter tuned with expert domain knowledge can effectively reduce prediction errors when compared against traditional single-state econometric models. With a simple back test, we also demonstrate that even a slight decrease in the prediction errors can lead to significant improvement in the trading performance of a naive trading algorithm.
@inproceedings{lim_iat_2012,author={Lim, Yee Pin and Cheng, Shih-Fen},title={Knowledge-driven autonomous commodity trading advisor},booktitle={2012 IEEE/WIC/ACM International Conference on Intelligent Agent Technology},address={Macau},year={2012},month=dec,smu={1664}}
IAT-12
A mechanism for organizing last-mile service using non-dedicated fleet
Unprecedented pace of urbanization and rising income levels have fueled the growth of car ownership in almost all newly formed megacities. Such growth has congested the limited road space and significantly affected the quality of life in these megacities. Convincing residents to give up their cars and use public transport is the most effective way in reducing congestion; however, even with sufficient public transport capacity, the lack of last-mile (from the transport hub to the destination) travel services is the major deterrent for the adoption of public transport. Due to the dynamic nature of such travel demands, fixed-size fleets will not be a cost-effective approach in addressing last-mile demands. Instead, we propose a dynamic, incentive-based mechanism that enables taxi ridesharing for satisfying last-mile travel demands. On the demand side, travelers would register their last-mile travel demands in real-time, and they are expected to receive ride arrangements before they reach the hub; on the supply side, depending on the real-time demands, proper incentives will be computed and provided to taxi drivers willing to commit to the lastmile service. Multiple travelers will be clustered into groups according to their destinations, and travelers belonging to the same group will be assigned to a taxi, while each of them paying fares considering their destinations and also their orders in reaching destinations. In this paper, we provide mathematical formulations for demand clustering and fare distribution. If the model returns a solution, it is guaranteed to be implementable. For cases where it is not possible to satisfy all demands despite having enough capacity, we propose a two-phase approach that identifies the maximal subset of riders that can be feasibly served. Finally, we use a series of numerical examples to demonstrate the effectiveness of our approach.
@inproceedings{cheng_iat_2012,author={Cheng, Shih-Fen and Nguyen, Duc Thien and Lau, Hoong Chuin},title={A mechanism for organizing last-mile service using non-dedicated fleet},booktitle={2012 IEEE/WIC/ACM International Conference on Intelligent Agent Technology},address={Macau},year={2012},month=dec,smu={1665}}
UAI-12
Uncertain congestion games with assorted human agent populations
Congestion games model a wide variety of real-world resource congestion problems, such as selfish network routing, traffic route guidance in congested areas, taxi fleet optimization and crowd movement in busy areas. However, existing research in congestion games assumes: (a) deterministic movement of agents between resources; and (b) perfect rationality (i.e. maximizing their own expected value) of all agents. Such assumptions are not reasonable in dynamic domains where decision support has to be provided to humans. For instance, in optimizing the performance of a taxi fleet serving a city, movement of taxis can be involuntary or nondeterministic (decided by the specific customer who hires the taxi) and more importantly, taxi drivers may not follow advice provided by the decision support system (due to bounded rationality of humans). To that end, we contribute: (a) a general framework for representing congestion games under uncertainty for populations with assorted notions of rationality. (b) a scalable approach for solving the decision problem for perfectly rational agents which are in the mix with boundedly rational agents; and (c) a detailed evaluation on a synthetic and real world data set to illustrate the usefulness of our new approach with respect to key social welfare metrics in the context of an assorted human-agent population. An interesting result from our experiments on a real-world taxi fleet optimization problem is that it is better (in terms of revenue and operational efficiency) for taxi drivers to follow perfectly rational strategies irrespective of the percentage of drivers not following the advice.
@inproceedings{ahmed_uai_2012,author={Ahmed, Asrar and Varakantham, Pradeep and Cheng, Shih-Fen},title={Uncertain congestion games with assorted human agent populations},booktitle={Twenty-Eighth Conference on Uncertainty in Artificial Intelligence},address={California, USA},year={2012},month=aug,smu={1568}}
AAMAS-12
Lagrangian relaxation for large-scale multi-agent planning
Multi-agent planning is a well-studied problem with applications in various areas. Due to computational constraints, existing research typically focuses either on unstructured domains with many agents, where we are content with heuristic solutions, or domains with small numbers of agents or special structure, where we can find provably near-optimal solutions. In contrast, here we focus on provably near-optimal solutions in domains with many agents, by exploiting influence limits. To that end, we make two key contributions: (a) an algorithm, based on Lagrangian relaxation and randomized rounding, for solving multi-agent planning problems represented as large mixed-integer programs; (b) a proof of convergence of our algorithm to a near-optimal solution.
@inproceedings{gordon_aamas_2012,author={Gordon, Geoffrey J. and Varakantham, Pradeep and Yeoh, William and Lau, Hoong Chuin and Aravamudhan, Ajay S. and Cheng, Shih-Fen},title={Lagrangian relaxation for large-scale multi-agent planning},booktitle={Eleventh International Conference on Autonomous Agents and Multi-Agent Systems},address={Valencia, Spain},year={2012},month=may,smu={1565}}
ICEC-12
Niche-seeking in influence maximization with adversary
In hotly contested product categories dominated by a few powerful firms, it is quite common for weaker or late entrants to focus only on particular segments of the whole market. The rationale for such strategy is intuitive: to avoid direct confrontation with heavy-weight firms, and to concentrate in segments where these weaker firms have comparative advantages. In marketing, this is what people called "go niche or go home". The niche-building strategy may rely on "homophily", which implies that consumers in a particular market segment might possess certain set of attributes that cause them to appreciate certain products better (in other words, weaker firms would customize their products to target some particular market segments and not the mass market). On the other hand, the niche-building strategy may also rely on the network effect, which implies that consumers having social relationship would reinforce each other via their respective adoptions. In this case, weaker firms should recognize such inter-customer network and concentrate only on customers belonging to certain set of strategic clusters. In this paper, we present the model for building effective niche-seeking strategies. For simplicity, we assume that the adoption choice depends only on the network effects (in other words, a customer will choose the product that is chosen by the majority of her neighbor). The social network is directed, and there will be two firms, one with significantly more marketing budget than the other firm. Firms take turns making investment choices on which customer to convert. For both firms, their budgets are fixed over time and unused budget will not carry over to future time periods. With this model, we manage to show that a simple strategy based on the evaluation of individual customer’s "value" can effectively identify and secure niches within randomly generated scale-free networks. We also show that such niche-building strategy indeed performs better in the long run than a myopic strategy that only cares about immediate market gains.
@inproceedings{liow_icec_2012,author={Liow, Long Foong and Cheng, Shih-Fen and Lau, Hoong Chuin},title={Niche-seeking in influence maximization with adversary},booktitle={Fourteenth International Conference on Electronic Commerce},address={Singapore},year={2012},month=aug,smu={1494}}
AAAI-12
Decision support for agent populations in uncertain and congested environments
This research is motivated by large scale problems in urban transportation and labor mobility where there is congestion for resources and uncertainty in movement. In such domains, even though the individual agents do not have an identity of their own and do not explicitly interact with other agents, they effect other agents. While there has been much research in handling such implicit effects, it has primarily assumed deterministic movements of agents. We address the issue of decision support for individual agents that are identical and have involuntary movements in dynamic environments. For instance, in a taxi fleet serving a city, when a taxi is hired by a customer, its movements are uncontrolled and depend on (a) the customers requirement; and (b) the location of other taxis in the fleet. Towards addressing decision support in such problems, we make two key contributions: (a) A framework to represent the decision problem for selfish individuals in a dynamic population, where there is transitional uncertainty (involuntary movements); and (b) Two techniques (Fictitious Play for Symmetric Agent Populations, FP-SAP and Softmax based Flow Update, SMFU) that converge to equilibrium solutions.We show that our techniques (apart from providing equilibrium strategies) outperform "driver" strategies with respect to overall availability of taxis and the revenue obtained by the taxi drivers. We demonstrate this on a real world data set with 8,000 taxis and 83 zones (representing the entire area of Singapore).
@inproceedings{varakantham_aaai_2012,author={Varakantham, Pradeep and Cheng, Shih-Fen and Gordon, Geoff and Ahmed, Asrar},title={Decision support for agent populations in uncertain and congested environments},booktitle={Twenty-Sixth AAAI Conference on Artificial Intelligence},address={Toronto, Canada},year={2012},month=feb,smu={1567}}
In this paper, we evaluate whether the robustness of a market mechanism that allocates complementary resources could be improved through the aggregation of time periods in which resources are consumed. In particular, we study a multi-round combinatorial auction that is built on a general equilibrium framework. We adopt the general equilibrium framework and the particular combinatorial auction design from the literature, and we investigate the benefits and the limitation of time-period aggregation when demand-side uncertainties are introduced. By using simulation experiments on a real-life resource allocation problem from a container port, we show that, under stochastic conditions, the performance variation of the process decreases as the time frame length (time frames are obtained by aggregating time periods) increases. This is achieved without causing substantial deterioration in the mean performance. The main driver for the increase in robustness is that longer time frames result in allocations where resources are assigned in longer contiguous time blocks. The resulting resource continuity allows bidders to shift schedules upon realization of stochasticity. To demonstrate the generality of the notion that resource continuity increases allocation robustness, we perform further experiments on a decentralized variant of the classical job shop scheduling problem. The experiment results demonstrate similar benefits.
@article{cheng_wias_2012,author={Cheng, Shih-Fen and Tajan, John and Lau, Hoong Chuin},title={Robust distributed scheduling via time period aggregation},journal={Web Intelligence and Agent Systems},volume={10(3)},pages={305--318},year={2012},smu={1600}}
2011
IAT-11
TaxiSim: A multiagent simulation platform for evaluating taxi fleet operations
Shih-Fen
Cheng, and Thi Duong
Nguyen
In 2011 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, Aug 2011
Taxi service is an important mode of public transportation in most metropolitan areas since it provides door-to-door convenience in the public domain. Unfortunately, despite all the convenience taxis bring, taxi fleets are also extremely inefficient to the point that over 50% of its operation time could be spent in idling state. Improving taxi fleet operation is an extremely challenging problem, not just because of its scale, but also due to fact that taxi drivers are self-interested agents that cannot be controlled centrally. To facilitate the study of such complex and decentralized system, we propose to construct a multiagent simulation platform that would allow researchers to investigate interactions among taxis and to evaluate the impact of implementing certain management policies. The major contribution of our work is the incorporation of our analysis on the real-world driver’s behaviors. Despite the fact that taxi drivers are selfish and unpredictable, by analyzing a huge GPS dataset collected from a major taxi fleet operator, we are able to clearly demonstrate that driver’s movements are closely related to the relative attractiveness of neighboring regions. By applying this insight, we are able to design a background agent movement strategy that generates aggregate performance patterns that are very similar to the real-world ones. Finally, we demonstrate the value of such system with a real-world case study.
@inproceedings{cheng_iat_2011,author={Cheng, Shih-Fen and Nguyen, Thi Duong},title={TaxiSim: A multiagent simulation platform for evaluating taxi fleet operations},booktitle={2011 IEEE/WIC/ACM International Conference on Intelligent Agent Technology},address={Lyon, France},year={2011},month=aug,smu={1405}}
AAMAS-11
Decentralized Decision Support for an agent population in dynamic and uncertain domains
In this paper, we evaluate whether the robustness of a market mechanism that allocates complementary resources could be improved through the aggregation of time periods in which resources are consumed. In particular, we study a multi-round combinatorial auction that is built on a general equilibrium framework. We adopt the general equilibrium framework and the particular combinatorial auction design from the literature, and we investigate the benefits and the limitation of time-period aggregation when demand-side uncertainties are introduced. By using simulation experiments on a real-life resource allocation problem from a container port, we show that, under stochastic conditions, the performance variation of the process decreases as the time frame length (time frames are obtained by aggregating time periods) increases. This is achieved without causing substantial deterioration in the mean performance. The main driver for the increase in robustness is that longer time frames result in allocations where resources are assigned in longer contiguous time blocks. The resulting resource continuity allows bidders to shift schedules upon realization of stochasticity. To demonstrate the generality of the notion that resource continuity increases allocation robustness, we perform further experiments on a decentralized variant of the classical job shop scheduling problem. The experiment results demonstrate similar benefits.
@inproceedings{varakantham_aamas_2011,author={Varakantham, Pradeep and Cheng, Shih-Fen and Nguyen, Thi Duong},title={Decentralized Decision Support for an agent population in dynamic and uncertain domains},booktitle={Tenth International Joint Conference on Autonomous Agents and MultiAgent Systems},address={Taipei, Taiwan},year={2011},month=may,smu={1600}}
APFRS-11
Would position limits have made any difference to the ’Flash Crash’ on May 6, 2010
Bernard
Lee, Shih-Fen
Cheng, and Annie
Koh
In Twenty-First Asia-Pacific Futures Research Symposium, Feb 2011
On May 6, 2010, the US equity markets experienced a brief but highly unusual drop in prices across a number of stocks and indices. The Dow Jones Industrial Average (DJIA) fell by approximately 9% in a matter of minutes, and several stocks were traded down sharply before recovering a short time later. Earlier research by Lee, Cheng and Koh (2010) identified the conditions under which a "flash crash" can be triggered by systematic traders running highly similar trading strategies, especially when they are "crowding out" other liquidity providers in the market. The authors contend that the events of May 6, 2010 exhibit patterns consistent with the type of "flash crash" observed in their earlier study (2010). While some commentators assigned blame to high-frequency trading, our analysis was unable to identify a direct link to high-frequency trading per se, but rather the domination of market activities by trading strategies that are responding to the same set of market variables in similar ways, as well as various pre-existing market micro-structural safety mechanisms with unintended consequences when triggered simultaneously. The consequent lack of market participants interested in the "other side" of their trades may result in a significant liquidity withdrawal during extreme market movements. This paper describes the results of 9 different simulations created by using a large-scale computer model to reconstruct the critical elements of the market events of May 6, 2010. The resulting price distribution provides a reasonable resemblance to the descriptive statistics of the second-by-second prices of S&P500 e-Mini futures from 14:30 to 15:00 on May 6, 2010. There are no a priori assumptions made on asset price distributions, and our description of market dynamics is purely based on the structure of the market and the key types of market participants involved. This type of simulation avoids "over-fitting" historical data, and can therefore provide regulators with deeper insights on the possible drivers of the "flash crash", as well as what type of policy responses may work or may not work under comparable market circumstances in the future. Our results also lead to a natural question for policy markers: If certain prescriptive measures such as position limits have a low probability of meeting its policy objectives on a day like May 6, will there be any other more effective counter measures without unintended consequences?
@inproceedings{lee_apfrs_2011,author={Lee, Bernard and Cheng, Shih-Fen and Koh, Annie},title={Would position limits have made any difference to the 'Flash Crash' on May 6, 2010},booktitle={Twenty-First Asia-Pacific Futures Research Symposium},address={Singapore},year={2011},month=feb,}
RFM
Would price limits have made any difference to the ’Flash Crash’ on May 6, 2010
On May 6, 2010, the U.S. equity markets experienced a brief but highly unusual drop in prices across a number of stocks and indices. The Dow Jones Industrial Average (see Figure 1) fell by approximately 9% in a matter of minutes, and several stocks were traded down sharply before recovering a short time later. The authors contend that the events of May 6, 2010 exhibit patterns consistent with the type of "flash crash" observed in their earlier study (2010). This paper describes the results of nine different simulations created by using a large-scale computer model to reconstruct the critical elements of the market events of May 6, 2010. The resulting price distribution provides a reasonable resemblance to the descriptive statistics of the second-by-second prices of S&P500 E-mini futures from 2:30 to 3:00 p.m. on May 6, 2010. This type of simulation avoids "over-fitting" historical data, and can therefore provide regulators with deeper insights on the possible drivers of the "flash crash," as well as what type of policy responses may work or may not work under comparable market circumstances in the future. Our results also lead to a natural question for policy makers: If certain prescriptive measures such as position limits have a low probability of meeting their policy objectives on a day like May 6, will there be any other more effective counter measures without unintended consequences?
@article{lee_rfm_2011,author={Lee, Bernard and Cheng, Shih-Fen and Koh, Annie},title={Would price limits have made any difference to the 'Flash Crash' on May 6, 2010},journal={Review of Futures Markets},volume={19(Special IFM Issue)},pages={55--93},year={2011},smu={1392}}
2010
IAT-10
Event study method for validating agent-based trading simulations
Shih-Fen
Cheng
In 2010 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, Aug 2010
In this paper, we introduce how one can validate an event-centric trading simulation platform that is built with multi-agent technology. The issue of validation is extremely important for agent-based simulations, but unfortunately, so far there is no one universal method that would work in all domains. The primary contribution of this paper is a novel combination of event-centric simulation design and event study approach for market dynamics generation and validation. In our event-centric design, the simulation is progressed by announcing news events that affect market prices. Upon receiving these events, event-aware software agents would adjust their views on the market and act accordingly. Their actions would be based on their roles and also their private information, and collectively the market dynamics will be shaped. The generated market dynamics can then be validated by a variant of the event study approach. We demonstrate how the methodology works with several numerical experiments and conclude by highlighting the practical significance of such simulation platform.
@inproceedings{cheng_iat_2010,author={Cheng, Shih-Fen},title={Event study method for validating agent-based trading simulations},booktitle={2010 IEEE/WIC/ACM International Conference on Intelligent Agent Technology},address={Toronto, Canada},year={2010},month=aug,smu={1563}}
APFRS-10
An analysis of extreme price shocks and illiquidity among systematic trend followers
Bernard
Lee, Shih-Fen
Cheng, and Annie
Koh
In Twentieth Asia-Pacific Futures Research Symposium, Feb 2010
We construct an agent-based model to study the interplay between extreme price shocks and illiquidity in the presence of systematic traders known as trend followers. The agent-based approach is particularly attractive in modeling commodity markets because the approach allows for the explicit modeling of production, capacities, and storage constraints. Our study begins by using the price stream from a market simulation involving human participants and studies the behavior of various trend-following strategies, assuming initially that their participation will not impact the market. We notice an incremental deterioration in strategy performance as and when strategies deviate further and further from the theoretical strategy of lookback straddles (Fung and Hsieh 2001), due to the negative impacts of transaction cost and imperfect execution. Next, the trend followers are allowed to participate in the market, trading against "uninformed" computer traders making randomized bids and offers. We notice that market prices begin to break down as the percentage of trend followers in the market reaches 80%. In addition, in a market dominated by "smart traders", it becomes increasingly difficult for any of them to generate profits using what is supposed to be a "long gamma" strategy. After all, trading is a zero-sum game: It is not feasible for any "long gamma" trader to generate a consistent profit unless someone else is willing to be on the other side of his/her trades. In any such market dominated by "smart traders" with low liquidity and extreme price instability, one proposed solution (as proposed earlier by the U.S. Commodity Futures Trading Commission) is to control position size limits, by either decreasing them (in the original proposal) or increasing them (for completeness in our analysis). Based on our simulation results, we have found no evidence supporting that such a solution will be effective; in fact, doing so will only lead to erratic price behavior as well as a variety of practical issues when imposing such changes to position size limits. An alternative proposal is to intervene in the market direct/indirectly, such as by using a market maker to inject/reduce liquidity. Our simulation results show evidence that injecting and reducing liquidity by the market maker can both be effective. However, a market maker can accumulate a large negative P&L by buying in a one-sided, falling market in which it is the only bidder, or vice versa. Therefore, in practice, no market maker may volunteer to participate in any such "market rescue" efforts unless governments are willing to underwrite some of its large potential losses. In short, direct/indirect intervention by controlling liquidity is not a panacea, and there are practical limits to its effectiveness.
@inproceedings{lee_apfrs_2010,author={Lee, Bernard and Cheng, Shih-Fen and Koh, Annie},title={An analysis of extreme price shocks and illiquidity among systematic trend followers},booktitle={Twentieth Asia-Pacific Futures Research Symposium},address={Hong Kong},year={2010},month=feb,}
RFM
An analysis of extreme price shocks and illiquidity among systematic trend followers
We construct an agent-based model to study the interplay between extreme price shocks and illiquidity in the presence of systematic traders known as trend followers. The agent-based approach is particularly attractive in modeling commodity markets because the approach allows for the explicit modeling of production, capacities, and storage constraints. Our study begins by using the price stream from a market simulation involving human participants and studies the behavior of various trend-following strategies, assuming initially that their participation will not impact the market. We notice an incremental deterioration in strategy performance as and when strategies deviate further and further from the theoretical strategy of lookback straddles (Fung and Hsieh 2001), due to the negative impacts of transaction cost and imperfect execution. Next, the trend followers are allowed to participate in the market, trading against "uninformed" computer traders making randomized bids and offers. We notice that market prices begin to break down as the percentage of trend followers in the market reaches 80%. In addition, in a market dominated by "smart traders," it becomes increasingly difficult for any of them to generate profits using what is supposed to be a "long gamma" strategy. After all, trading is a zero-sum game: It is not feasible for any "long gamma" trader to generate a consistent profit unless someone else is willing to be on the other side of his/her trades. In any such market dominated by "smart traders" with low liquidity and extreme price instability, one proposed solution (as proposed earlier by the U.S. Commodity Futures Trading Commission) is to control position size limits, by either decreasing them (in the original proposal) or increasing them (for completeness in our analysis). Based on our simulation results, we have found no evidence supporting that such a solution will be effective; in fact, doing so will only lead to erratic price behavior as well as a variety of practical issues when imposing such changes to position size limits. An alternative proposal is to intervene in the market direct/indirectly, such as by using a market maker to inject/reduce liquidity. Our simulation results show evidence that injecting and reducing liquidity by the market maker can both be effective. However, a market maker can accumulate a large negative P&L by buying in a one-sided, falling market in which it is the only bidder, or vice versa. Therefore, in practice, no market maker may volunteer to participate in any such "market rescue" efforts unless governments are willing to underwrite some of its large potential losses. In short, direct/indirect intervention by controlling liquidity is not a panacea, and there are practical limits to its effectiveness.
@article{lee_rfm_2010,author={Lee, Bernard and Cheng, Shih-Fen and Koh, Annie},title={An analysis of extreme price shocks and illiquidity among systematic trend followers},journal={Review of Futures Markets},volume={18(4)},pages={385--419},year={2010},smu={1871}}
2009
ITSC-09
A service choice model for optimizing taxi service delivery
Shih-Fen
Cheng, and Xin
Qu
In Twelfth International IEEE Conference on Intelligent Transportation Systems, Oct 2009
Taxi service has undergone radical revamp in recent years. In particular, significant investments in communication system and GPS devices have improved quality of taxi services through better dispatches. In this paper, we propose to leverage on such infrastructure and build a service choice model that helps individual drivers in deciding whether to serve a specific taxi stand or not. We demonstrate the value of our model by applying it to a real-world scenario. We also highlight interesting new potential approaches that could significantly improve the quality of taxi services.
@inproceedings{cheng_itsc_2009,author={Cheng, Shih-Fen and Qu, Xin},title={A service choice model for optimizing taxi service delivery},booktitle={Twelfth International IEEE Conference on Intelligent Transportation Systems},address={St. Louis, MO},year={2009},month=oct,smu={209}}
IAAI-09
An agent-based commodity trading simulation
Shih-Fen
Cheng, and Yee Pin
Lim
In Twenty-First Annual Conference on Innovative Applications of Artificial Intelligence, Jul 2009
In this paper, an event-centric commodity trading simulation powered by the multiagent framework is presented. The purpose of this simulation platform is for training novice traders. The simulation is progressed by announcing news events that affect various aspects of the commodity supply chain. Upon receiving these events, market agents that play the roles of producers, consumers, and speculators would adjust their views on the market and act accordingly. Their actions would be based on their roles and also their private information, and collectively they shape the market dynamics. This simulation has been effectively deployed for several training sessions. We will present the underlying technologies that are employed and discuss the practical significance of such platform.
@inproceedings{cheng_iaai_2009,author={Cheng, Shih-Fen and Lim, Yee Pin},title={An agent-based commodity trading simulation},booktitle={Twenty-First Annual Conference on Innovative Applications of Artificial Intelligence},address={Pasadena, CA, USA},year={2009},month=jul,smu={838}}
2008
IAT-08
Distributing complementary resources across multiple periods with stochastic demand: Hedging via time frame aggregation
In this paper, we evaluate whether the robustness of a market mechanism that allocates complementary resources could be improved through the aggregation of time periods in which resources are consumed. In particular, we study a multi-round combinatorial auction that is built on a general equilibrium framework. We adopt the general equilibrium framework and the particular combinatorial auction design from the literature, and we investigate the benefits and the limitation of time-period aggregation when demand-side uncertainties are introduced. By using simulation experiments, we show that under stochastic conditions the performance variation of the process decreases as the time frame length (time frames are obtained by aggregating time periods) increases. This is achieved without causing deterioration in the mean performance.
@inproceedings{cheng_iat_2008,author={Cheng, Shih-Fen and Tajan, John and Lau, Hoong Chuin},title={Distributing complementary resources across multiple periods with stochastic demand: Hedging via time frame aggregation},booktitle={2008 IEEE/WIC/ACM International Conference on Intelligent Agent Technology},address={Sydney, Australia},year={2008},month=dec,smu={283}}
2007
IAT-07
Designing the market game for a commodity trading simulation
Shih-Fen
Cheng
In 2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, Nov 2007
In this paper, we propose to design a market game that (a) can be used in modeling and studying commodity trading scenarios, and (b) can be used in capturing human traders’ behaviors. Specifically, we demonstrate the usefulness of this commodity trading game in a single-commodity futures trading scenario. A pilot experiment was run with a mixture of human traders and an autonomous agent that emulates the aggregatedmarket condition, with the assumption that this autonomous agent would hint each of its action through a public announcement. We show that the information collected from this simulation can be used to extract the pattern of successful human traders. Finally, we elaborate on the potential of this market game in studying autonomous commodity trading.
@inproceedings{cheng_iat_2007,author={Cheng, Shih-Fen},title={Designing the market game for a commodity trading simulation},booktitle={2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology},address={San Jose, CA, USA},year={2007},month=nov,smu={207}}
IAT-07
Multi-period combinatorial auction mechanism for distributed resource allocation and scheduling
Hoong Chuin
Lau, Shih-Fen
Cheng, Thin Yin
Leong, Jong Han
Park, and Zhengyi
Zhao
In 2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, Nov 2007
We consider the problem of resource allocation and scheduling where information and decisions are decentralized, and our goal is to propose a market mechanism that allows resources from a central resource pool to be allocated to distributed decision makers (agents) that seek to optimize their respective scheduling goals. We propose a generic combinatorial auction mechanism that allows agents to competitively bid for the resources needed in a multi-period setting, regardless of the respective scheduling problem faced by the agent, and show how agents can design optimal bidding strategies to respond to price adjustment strategies from the auctioneer. We apply our approach to handle real-time large-scale dynamic resource coordination in a mega-scale container terminal.
@inproceedings{lau_iat_2007,author={Lau, Hoong Chuin and Cheng, Shih-Fen and Leong, Thin Yin and Park, Jong Han and Zhao, Zhengyi},title={Multi-period combinatorial auction mechanism for distributed resource allocation and scheduling},booktitle={2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology},address={San Jose, CA, USA},year={2007},month=nov,smu={208}}
We introduce a weakening of standard game-theoretic δ-dominance conditions, called dominance, which enables more aggressive pruning of candidate strategies at the cost of solution accuracy. Equilibria of a game obtained by eliminating a δ-dominated strategy are guaranteed to be approximate equilibria of the original game, with degree of approximation bounded by the dominance parameter. We can apply elimination of δ-dominated strategies iteratively, but the for which a strategy may be eliminated depends on prior eliminations. We discuss implications of this order independence, and propose greedy heuristics for determining a sequence of eliminations to reduce the game as far as possible while keeping down costs. A case study analysis of an empirical 2-player game serves to illustrate the technique, and demonstrate the utility of weaker-than-weak dominance pruning.
@inproceedings{cheng_ijcai_2007,author={Cheng, Shih-Fen and Wellman, Michael P.},title={Iterated weaker-than-weak dominance},booktitle={Twentieth International Joint Conference on Artificial Intelligence},address={Hyderabad, India},year={2007},month=jan,smu={840}}
The problem of finding optimal coordinated signal timing plans for a large number of traffic signals is a challenging problem because of the exponential growth in the number of joint timing plans that need to be explored as the network size grows. In this paper, the game-theoretic paradigm of fictitious play to iteratively search for a coordinated signal timing plan is employed, which improves a system-wide performance criterion for a traffic network. The algorithm is robustly scalable to realistic-size networks modeled with high-fidelity simulations. Results of a case study for the city of Troy, MI, where there are 75 signalized intersections, are reported. Under normal traffic conditions, savings in average travel time of more than 20% are experienced against a static timing plan, and even against an aggressively tuned automatic-signal-retiming algorithm, savings of more than 10% are achieved. The efficiency of the algorithm stems from its parallel nature. With a thousand parallel CPUs available, the algorithm finds the plan above under 10 min, while a version of a hill-climbing algorithm makes virtually no progress in the same amount of wall-clock computational time.
@article{cheng_tits_2006,author={Cheng, Shih-Fen and Epelman, Marina A. and Smith, Robert L.},title={CoSIGN: A parallel algorithm for coordinated traffic signal control},journal={IEEE Transactions on Intelligent Transportation Systems},volume={7(4)},pages={551--564},year={2006},smu={176}}
2005
AAAI-05
Approximate strategic reasoning through hierarchical reduction of large symmetric games
Michael P.
Wellman, Daniel M.
Reeves, Kevin M.
Lochner, Shih-Fen
Cheng, and Rahul
Suri
In Twentieth National Conference on Artificial Intelligence, Jul 2005
To deal with exponential growth in the size of a game with the number of agents, we propose an approximation based on a hierarchy of reduced games. The reduced game achieves savings by restricting the number of agents playing any strategy to fixed multiples. We validate the idea through experiments on randomly generated local-effect games. An extended application to strategic reasoning about a complex trading scenario motivates the approach, and demonstrates methods for game-theoretic reasoning over incompletely-specified games at multiple levels of granularity.
@inproceedings{wellman_aaai_2005,author={Wellman, Michael P. and Reeves, Daniel M. and Lochner, Kevin M. and Cheng, Shih-Fen and Suri, Rahul},title={Approximate strategic reasoning through hierarchical reduction of large symmetric games},booktitle={Twentieth National Conference on Artificial Intelligence},address={Pittsburgh, PA, USA},year={2005},month=jul,smu={1200}}
TAC-02 was the third in a series of Trading Agent Competition events fostering research in automating trading strategies by showcasing alternate approaches in an open-invitation market game. TAC presents a challenging travel-shopping scenario where agents must satisfy client preferences for complementary and substitutable goods by interacting through a variety of market types. Michigan’s entry, Walverine, bases its decisions on a competitive (Walrasian) analysis of the TAC travel economy. Using this Walrasian model, we construct a decision-theoretic formulation of the optimal bidding problem, which Walverine solves in each round of bidding for each good. Walverine’s optimal bidding approach, as well as several other features of its overall strategy, are potentially applicable in a broad class of trading environments.
@article{cheng_dss_2005,author={Cheng, Shih-Fen and Leung, Evan and Lochner, Kevin M. and O'Malley, Kevin and Reeves, Daniel M. and Schvartzman, Julian L. and Wellman, Michael P.},title={Walverine: A Walrasian trading agent},journal={Decision Support Systems},volume={39},pages={169--184},year={2005},smu={47}}
2004
GTDT-04
Notes on equilibria in symmetric games
Shih-Fen
Cheng, Daniel M.
Reeves, Yevgeniy
Vorobeychik, and Michael P.
Wellman
In Sixth Workshop on Game Theoretic and Decision Theoretic Agents (at AAMAS-04), May 2004
In a symmetric game, every player is identical with respect to the game rules. We show that a symmetric 2strategy game must have a pure-strategy Nash equilibrium. We also discuss Nash’s original paper and its generalized notion of symmetry in games. As a special case of Nash’s theorem, any finite symmetric game has a symmetric Nash equilibrium. Furthermore, symmetric infinite games with compact, convex strategy spaces and continuous, quasiconcave utility functions have symmetric pure-strategy Nash equilibria. Finally, we discuss how to exploit symmetry for more efficient methods of finding Nash equilibria.
@inproceedings{cheng_gtdt_2004,author={Cheng, Shih-Fen and Reeves, Daniel M. and Vorobeychik, Yevgeniy and Wellman, Michael P.},title={Notes on equilibria in symmetric games},booktitle={Sixth Workshop on Game Theoretic and Decision Theoretic Agents (at AAMAS-04)},address={New York City, NY, USA},year={2004},month=may,smu={1213}}
The annual trading agent competition offers agent designers a forum for evaluating programmed trading techniques in a challenging market scenario. TAC aims to spur research by enabling researchers to compare techniques on a common problem and build on each other’s ideas. A fixed set of assumptions and environment settings facilitates communication of methods and results. As a multiyear event, TAC lets researchers observe trading agents’ progress over time, in effect accelerating the evolution of an adapted population of traders. Given all the participant effort invested, it is incumbent on us to learn as much from the experience as possible. After three years of TAC, we’re ready to examine there we stand. To do this, we used data from actual TAC tournaments and some post-competition experimentation. We based our analysis almost entirely on outcomes (profits and allocations), with very little direct accounting for specific agent techniques.
@article{wellman_is_2003,author={Wellman, Michael P. and Cheng, Shih-Fen and Reeves, Daniel M. and Lochner, Kevin M.},title={Trading agents competing: Performance, progress, and market effectiveness},journal={IEEE Intelligent Systems},volume={18(6)},pages={48--53},year={2003},smu={116}}
1996
CSME-96
Computer-aided sketching of articulated gear mechanisms
Shih-Fen
Cheng, Chung-Chih
Chou, Cheng-Yu
Lin
, and Dar-Zen
Chen
In Thirteenth Chinese Society of Mechanical Engineers Annual Conference, May 1996
@inproceedings{cheng_csme_1996,author={Cheng, Shih-Fen and Chou, Chung-Chih and Lin, Cheng-Yu and Chen, Dar-Zen},title={Computer-aided sketching of articulated gear mechanisms},booktitle={Thirteenth Chinese Society of Mechanical Engineers Annual Conference},address={Taipei, Taiwan},year={1996},}