More Like this

1. A Unified Model for the Two-stage Offline-then-Online Resource Allocation

   https://doi.org/10.24963/ijcai.2020/581  

   Xu, Yifan; Xu, Pan; Pan, Jianping; Tao, Jun (July 2020, The Twenty-Ninth International Joint Conference on Artificial Intelligence)

   null (Ed.)

   With the popularity of the Internet, traditional offline resource allocation has evolved into a new form, called online resource allocation. It features the online arrivals of agents in the system and the real-time decision-making requirement upon the arrival of each online agent. Both offline and online resource allocation have wide applications in various real-world matching markets ranging from ridesharing to crowdsourcing. There are some emerging applications such as rebalancing in bike sharing and trip-vehicle dispatching in ridesharing, which involve a two-stage resource allocation process. The process consists of an offline phase and another sequential online phase, and both phases compete for the same set of resources. In this paper, we propose a unified model which incorporates both offline and online resource allocation into a single framework. Our model assumes non-uniform and known arrival distributions for online agents in the second online phase, which can be learned from historical data. We propose a parameterized linear programming (LP)-based algorithm, which is shown to be at most a constant factor of 1/4 from the optimal. Experimental results on the real dataset show that our LP-based approaches outperform the LP-agnostic heuristics in terms of robustness and effectiveness. 

   more » « less
2. A Traveler Incentive Program for Promoting Community-Based Ridesharing

   https://doi.org/10.1287/trsc.2021.1121  

   Tafreshian, Amirmahdi; Masoud, Neda (January 2022, Transportation Science)

   Traffic congestion has become a serious issue around the globe, partly owing to single-occupancy commuter trips. Ridesharing can present a suitable alternative for serving commuter trips. However, there are several important obstacles that impede ridesharing systems from becoming a viable mode of transportation, including the lack of a guarantee for a ride back home as well as the difficulty of obtaining a critical mass of participants. This paper addresses these obstacles by introducing a traveler incentive program (TIP) to promote community-based ridesharing with a ride back home guarantee among commuters. The TIP program allocates incentives to (1) directly subsidize a select set of ridesharing rides and (2) encourage a small, carefully selected set of travelers to change their travel behavior (i.e., departure or arrival times). We formulate the underlying ride-matching problem as a budget-constrained min-cost flow problem and present a Lagrangian relaxation-based algorithm with a worst-case optimality bound to solve large-scale instances of this problem in polynomial time. We further propose a polynomial-time, budget-balanced version of the problem. Numerical experiments suggest that allocating subsidies to change travel behavior is significantly more beneficial than directly subsidizing rides. Furthermore, using a flat tax rate as low as 1% can double the system’s social welfare in the budget-balanced variant of the incentive program. 

   more » « less
3. Towards Continuous Access Control Validation and Forensics

   https://doi.org/10.1145/3319535.3363191  

   Xiang, Chengcheng; Wu, Yudong; Shen, Bingyu; Shen, Mingyao; Huang, Haochen; Xu, Tianyin; Zhou, Yuanyuan; Moore, Cindy; Jin, Xinxin; Sheng, Tianwei (January 2019, Proceedings of the ACM Conference on Computer and Communications Security)

   Access control is often reported to be “profoundly broken” in real- world practices due to prevalent policy misconfigurations intro- duced by system administrators (sysadmins). Given the dynamics of resource and data sharing, access control policies need to be continuously updated. Unfortunately, to err is human—sysadmins often make mistakes such as over-granting privileges when chang- ing access control policies. With today’s limited tooling support for continuous validation, such mistakes can stay unnoticed for a long time until eventually being exploited by attackers, causing catastrophic security incidents. We present P-DIFF, a practical tool for monitoring access control behavior to help sysadmins early detect unintended access control policy changes and perform postmortem forensic analysis upon security attacks. P-DIFF continuously monitors access logs and infers access control policies from them. To handle the challenge of policy evolution, we devise a novel time-changing decision tree to effectively represent access control policy changes, coupled with a new learning algorithm to infer the tree from access logs. P-DIFF provides sysadmins with the inferred policies and detected changes to assist the following two tasks: (1) validating whether the access control changes are intended or not; (2) pinpointing the historical changes responsible for a given security attack. We evaluate P-DIFF with a variety of datasets collected from five real-world systems, including two from industrial companies. P- DIFF can detect 86%–100% of access control policy changes with an average precision of 89%. For forensic analysis, P-DIFF can pinpoint the root-cause change that permits the target access in 85%–98% of the evaluated cases. 

   more » « less
4. QFlow: A Learning Approach to High QoE Video Streaming at the Wireless Edge

   https://doi.org/10.1109/TNET.2021.3106675  

   Bhattacharyya, Rajarshi; Bura, Archana; Rengarajan, Desik; Rumuly, Mason; Xia, Bainan; Shakkottai, Srinivas; Kalathil, Dileep; Mok, Ricky K.; Dhamdhere, Amogh (January 2021, IEEE/ACM Transactions on Networking)

   null (Ed.)

   The predominant use of wireless access networks is for media streaming applications. However, current access networks treat all packets identically, and lack the agility to determine which clients are most in need of service at a given time. Software reconfigurability of networking devices has seen wide adoption, and this in turn implies that agile control policies can be now instantiated on access networks. Exploiting such reconfigurability requires the design of a system that can enable a configuration, measure the impact on the application performance (Quality of Experience), and adaptively select a new configuration. Effectively, this feedback loop is a Markov Decision Process whose parameters are unknown. The goal of this work is to develop QFlow, a platform that instantiates this feedback loop, and instantiate a variety of control policies over it. We use the popular application of video streaming over YouTube as our use case. Our context is priority queueing, with the action space being that of determining which clients should be assigned to each queue at each decision period. We first develop policies based on model-based and model-free reinforcement learning. We then design an auction-based system under which clients place bids for priority service, as well as a more structured index-based policy. Through experiments, we show how these learning-based policies on QFlow are able to select the right clients for prioritization in a high-load scenario to outperform the best known solutions with over 25% improvement in QoE, and a perfect QoE score of 5 over 85% of the time. 

   more » « less
5. Mobilytics-Gym: A simulation framework for analyzing urban mobility decision strategies

   https://doi.org/10.1109/SMARTCOMP.2019.00064  

   Samal, Chinmaya; Dubey, Abhishek; Ratliff, Lillian (June 2019, 2019 IEEE International Conference on Smart Computing (SMARTCOMP))

   The rise in deep learning models in recent years has led to various innovative solutions for intelligent transportation technologies. Use of personal and on-demand mobility services puts a strain on the existing road network in a city. To mitigate this problem, city planners need a simulation framework to evaluate the effect of any incentive policy in nudging commuters towards alternate modes of travel, such as bike and car-share options. In this paper, we leverage MATSim, an agent-based simulation framework, to integrate agent preference models that capture the altruistic behavior of an agent in addition to their disutility proportional to the travel time and cost. These models are learned in a data-driven approach and can be used to evaluate the sensitivity of an agent to system-level disutility and monetary incentives given, e.g., by the transportation authority. This framework provides a standardized environment to evaluate the effectiveness of any particular incentive policy of a city, in nudging its residents towards alternate modes of transportation. We show the effectiveness of the approach and provide analysis using a case study from the Metropolitan Nashville area. 

   more » « less