More Like this

1. Incentivizing Truthfulness Through Audits in Strategic Classification

   Estornell, Andrew ; Das, Sanmay ; Vorobeychik, Yevgeniy ( January 2021 , Proceedings of the AAAI Conference on Artificial Intelligence)

   In many societal resource allocation domains, machine learning methods are increasingly used to either score or rank agents in order to decide which ones should receive either resources (e.g., homeless services) or scrutiny (e.g., child welfare investigations) from social services agencies. An agency’s scoring function typically operates on a feature vector that contains a combination of self-reported features and information available to the agency about individuals or households. This can create incentives for agents to misrepresent their self-reported features in order to receive resources or avoid scrutiny, but agencies may be able to selectively audit agents to verify the veracity of their reports. We study the problem of optimal auditing of agents in such settings. When decisions are made using a threshold on an agent’s score, the optimal audit policy has a surprisingly simple structure, uniformly auditing all agents who could benefit from lying. While this policy can, in general be hard to compute because of the difficulty of identifying the set of agents who could benefit from lying given a complete set of reported types, we also present necessary and sufficient conditions under which it is tractable. We show that the scarce resource setting is more difficult, and exhibit an approximately optimal audit policy in this case. In addition, we show that in either setting verifying whether it is possible to incentivize exact truthfulness is hard even to approximate. However, we also exhibit sufficient conditions for solving this problem optimally, and for obtaining good approximations. 

   more » « less
2. Online Resource Allocation with Matching Constraints

   Dickerson, John ; Sankararaman, Karthik ; Sarpatwar, Kanthi ; Srinivasan, Aravind ; Wu, Kung-Lu ; Xu, Pan ( January 2019 , International Conference on Autonomous Agents and Multiagent Systems (AAMAS))

   Matching markets with historical data are abundant in many applications, e.g., matching candidates to jobs in hiring, workers to tasks in crowdsourcing markets, and jobs to servers in cloud services. In all these applications, a match consumes one or more shared and limited resources and the goal is to best utilize these to maximize a global objective. Additionally, one often has historical data and hence some statistics (usually first-order moments) of the arriving agents (e.g., candidates, workers, and jobs) can be learnt. To model these scenarios, we propose a unifying framework, called Multi- Budgeted Online Assignment with Known Adversarial Distributions. In this model,we have a set of offline servers with different deadlines and a set of online job types. At each time, a job of type j arrives. Assigning this job to a server i yields a profit w(i, j) while consuming a(i,j) -- a vector lying in [0, 1]^K -- quantities of distinct resources. The goal is to design an (online) assignment policy that maximizes the total expected profit without violating the (hard) budget constraint. We propose and theoretically analyze two linear programming (LP) based algorithms which are almost optimal among all LP-based approaches. We also propose several heuristics adapted from our algorithms and compare them to other LP-agnostic algorithms using both synthetic as well as real-time cloud scheduling and public safety datasets. Experimental results show that our proposed algorithms are effective and significantly out-perform the baselines. Moreover, we show empirically the trade-off between fairness and efficiency of our algorithms which does well even on fairness metrics without explicitly optimizing for it. 

   more » « less
3. Optimizing Network Slicing via Virtual Resource Pool Partitioning

   Pablo Caballero, Gustavo de ( June 2019 , WIOPT : Workshop on Resource Allocation, Cooperation and Competition in Wireless Networks)

   This paper focuses on optimizing resource allocation amongst a set of tenants, network slices, supporting dynamic customer loads over a set of distributed resources, e.g., base stations. The aim is to reap the benefits of statistical multiplexing resulting from flexible sharing of ‘pooled’ resources, while enabling tenants to differentiate and protect their performance from one another’s load fluctuations. To that end we consider a setting where resources are grouped into Virtual Resource Pools (VRPs) wherein resource allocation is jointly and dynam- ically managed. Specifically for each VRP we adopt a Share- Constrained Proportionally Fair (SCPF) allocation scheme where each tenant is allocated a fixed share (budget). This budget is to be distributed equally amongst its active customers which in turn are granted fractions of their associated VRP resources in proportion to customer shares. For a VRP with a single resource, this translates to the well known Generalized Processor Sharing (GPS) policy. For VRPs with multiple resources SCPF provides a flexible means to achieve load elastic allocations across tenants sharing the pool. Given tenants’ per resource shares and expected loads, this paper formulates the problem of determining optimal VRP partitions which maximize the overall expected shared weighted utility while ensuring protection guarantees. For a high load/capacity setting we exhibit this network utility function explicitly, quantifying the benefits and penalties of any VRP partition, in terms of network slices’ ability to achieve performance differentiation, load balancing, and statistical multiplexing. Although the problem is shown to be NP-Hard, a simple greedy heuristic is shown to be effective. Analysis and simulations confirm that the selection of optimal VRP partitions provide a practical avenue towards improving network utility in network slicing scenarios with dynamic loads. 

   more » « less
4. Exploiting Federated Learning Technique to Recognize Human Activities in Resource-Constrained Environment

   Ahmed Imteaj, Raghad Alabagi ( December 2021 , The 13th International Conference on Intelligent Human Computer Interaction (IHCI-2021))

   The conventional machine learning (ML) and deep learning (DL) methods use large amount of data to construct desirable prediction models in a central fusion center for recognizing human activities. However, such model training encounters high communication costs and leads to privacy infringement. To address the issues of high communication overhead and privacy leakage, we employed a widely popular distributed ML technique called Federated Learning (FL) that generates a global model for predicting human activities by combining participated agents’ local knowledge. The state-of-the-art FL model fails to maintain acceptable accuracy when there is a large number of unreliable agents who can infuse false model, or, resource-constrained agents that fails to perform an assigned computational task within a given time window. We developed an FL model for predicting human activities by monitoring agent’s contributions towards model convergence and avoiding the unreliable and resource-constrained agents from training. We assign a score to each client when it joins in a network and the score is updated based on the agent’s activities during training. We consider three mobile robots as FL clients that are heterogeneous in terms of their resources such as processing capability, memory, bandwidth, battery-life and data volume. We consider heterogeneous mobile robots for understanding the effects of real-world FL setting in presence of resource-constrained agents. We consider an agent unreliable if it repeatedly gives slow response or infuses incorrect models during training. By disregarding the unreliable and weak agents, we carry-out the local training of the FL process on selected agents. If somehow, a weak agent is selected and started showing straggler issues, we leverage asynchronous FL mechanism that aggregate the local models whenever it receives a model update from the agents. Asynchronous FL eliminates the issue of waiting for a long time to receive model updates from the weak agents. To the end, we simulate how we can track the behavior of the agents through a reward-punishment scheme and present the influence of unreliable and resource-constrained agents in the FL process. We found that FL performs slightly worse than centralized models, if there is no unreliable and resource-constrained agent. However, as the number of malicious and straggler clients increases, our proposed model performs more effectively by identifying and avoiding those agents while recognizing human activities as compared to the stateof-the-art FL and ML approaches. 

   more » « less
5. Cui Bono: Do Open Source Software Incubator Policies and Procedures Benefit the Projects or the Incubator?

   https://doi.org/10.5334/ijc.1176  

   Sen, A. ; Atkisson, C. ; Schweik, C ( April 2022 , The international journal of the commons)

   Open source software (OSS), a form of Digital or Knowledge Commons, underlies much of the technology that we use in our daily lives. The existence and continuation of OSS relies on the contribution of private resources – personal time, volunteer energy, and effort of numerous actors (e.g., software developers’ time as a common-pool resource) – to public goods, the benefits of which are enjoyed by everyone. Nonprofit organizations such as the Apache Software Foundation (ASF) attempt to aid this process by providing various collective services to OSS projects, acting as a second-order actor in the production of the public good. To this end, the ASF Incubator has created policies – essentially rules or norms – that serve to protect its interests and, as they say, increase the sustainability of the projects. Each policy requires investment by ASF (in terms of money or the use of volunteer time) or an incubating project (in terms of taking project personnel time), the benefits of which can accrue to either party. Such policies may impose additional costs on incubating projects, leading to a decreased production of the OSS public good. Using the ASF Incubator policy documents, we construct a dataset that records who – ASF or an incubating project – bears the cost and who enjoys the benefit of each policy and procedure. We can code most policy statements as costing one party and benefiting one party. The distribution of costs and benefits according to party indicates whether the second-order actor is contributing to an increase in the public good and if they are doing so sustainably. Through a two-way ANOVA, we characterize the impact of ASF policies on the production of public goods (OSS). Being a part of ASF imposes some costs on projects, but these costs may make projects more sustainable. Our analysis shows that the distribution of costs and benefits is fairly symmetric between the ASF and incubating projects. Thus, the configuration of policies or the “institutional design” of the ASF could aid in producing the OSS public good by providing services that projects require. 

   more » « less