Author name cluster

Chenhao Wang

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

25 papers

1 author row

AAMAS Conference 2026 Conference Paper

Obnoxious Facility Location Problems: Strategyproof Mechanisms Optimizing L p -Aggregated Utilities and Costs

Hau Chan
Jianan Lin
Chenhao Wang

We study the problem of locating a single obnoxious facility on the normalized line segment [0, 1] with strategic agents from a mechanism design perspective. Each agent has a preference for the undesirable location of the facility and would prefer the facility to be far away from their location. We consider the utility of the agent, defined as the distance between the agent’s location and the facility location, and the cost of each agent, equal to one minus the utility. Given this standard setting of obnoxious facility location problems, our goal is to design (group) strategyproof mechanisms to elicit agent locations truthfully and determine facility location approximately optimizing the 𝐿𝑝-aggregated utility and cost objectives, which generalizes the 𝐿𝑝-norm (𝑝 ≥ 1) of the agents’ utilities and agents’ costs to any 𝑝 ∈ [−∞, ∞], respectively. We establish upper and lower bounds on the approximation ratios of deterministic and randomized (group) strategyproof mechanisms for maximizing the 𝐿𝑝-aggregated utilities or minimizing the 𝐿𝑝-aggregated costs across the range of 𝑝-values. While there are gaps between upper and lower bounds for randomized mechanisms, our bounds for deterministic mechanisms are tight.

PDF

JAAMAS Journal 2026 Journal Article

Strategyproof facility location with prediction: minimizing the maximum cost

Hau Chan
Jianan Lin
Chenhao Wang

Abstract We study the mechanism design problem of facility location on a metric space in the learning-augmented framework, where mechanisms have access to imperfect predictions of the optimal facility locations. Our objective is to design strategyproof (SP) mechanisms that truthfully elicit agents’ preferences over facility locations and, using the given prediction, select a facility location that approximately minimizes the maximum cost among all agents. In particular, we seek SP mechanisms whose approximation guarantees depend on the prediction error: they should achieve improved performance when the prediction is accurate (the property of consistency ) while still ensuring strong worst-case guarantees when the prediction is arbitrarily inaccurate (the property of robustness ). On the real line, we characterize all deterministic SP mechanisms with consistency strictly better than 2 and bounded robustness for the maximum cost. We show that any such mechanism must coincide with the MinMaxP mechanism, which returns the prediction if it lies between the two extreme agent locations and otherwise returns the agent location closest to the prediction. For any prediction error $\eta \ge 0$, we prove that MinMaxP achieves a $(1+\min (1, \eta ))$ -approximation and that no deterministic SP mechanism can obtain a better approximation ratio. In addition, for two-dimensional spaces with the $\ell ^p$ distance, we analyze the approximation guarantees of a deterministic mechanism that applies MinMaxP independently on each coordinate, as well as a randomized mechanism that selects between two deterministic mechanisms with carefully chosen probabilities. We further extend these results to the $L_p$ -norm social cost objective on the line metric and the maximum cost objective on the tree metric. Finally, we examine the group strategyproofness of the mechanisms.

Details DOI

JBHI Journal 2025 Journal Article

Learning to Detect Sleep Micro-Events from Coarse Sleep Stage Annotations

Chenhao Wang
Yan Pei
Jing Hu
Chengyang Han
Jiahui Xu
Lisan Zhang
Feng Yu
Bo Jin

Sleep micro-events, such as sleep spindles and K-complexes, are closely associated with neurological cognitive functions. While artificial intelligence (AI)-assisted sleep micro-event detection provides automated annotation to reduce reliance on labor-intensive expert labeling, current supervised approaches require precisely annotated datasets that remain scarce in clinical practice. To overcome this data bottleneck, this paper introduces a Weakly Supervised Sleep Micro-Event Detector (WSSMED) that leverages readily available coarse sleep stage annotations. The proposed WSSMED features a dual-branch architecture, consisting of a wave prototype module and a cluster module, designed to capture the fine-grained sleep micro-event patterns experts rely on for sleep staging. This framework infers expert logic from coarse annotations while mitigating performance degradation caused by annotation inconsistencies arising from inter-rater variability. Experiments conducted on two public datasets and one clinical dataset demonstrate that WSSMED achieves state-of-the-art performance in detecting sleep spindles and K-complexes, as evaluated at both sample-level and event-level in terms of precision, recall and F1-score metrics. Furthermore, subject-level evaluation demonstrates that the density and duration of micro-events detected by WSSMED-key metrics linked to cognitive function and neurological status-align more closely with expert annotations than those of other reported methods. These results highlight the clinical potential of WSSMED for reliable sleep micro-event analysis.

Details DOI

AAAI Conference 2025 Conference Paper

Mechanism Design for Connecting Regions Under Disruptions

Hau Chan
Jianan Lin
Zining Qin
Chenhao Wang

Man-made and natural disruptions such as planned constructions on roads, suspensions of bridges, and blocked roads by trees/mudslides/floods can often create obstacles that separate two connected regions. As a result, the traveling and reachability of agents from their respective regions to other regions can be affected. To minimize the impact of the obstacles and maintain agent accessibility, we initiate the problem of constructing a new pathway (e.g., a detour or new bridge) connecting the regions disconnected by obstacles from the mechanism design perspective. In the problem, each agent in their region has a private location and is required to access the other region. The cost of an agent is the distance from their location to the other region via the pathway. Our goal is to design strategyproof mechanisms that elicit truthful locations from the agents and approximately optimize the social or maximum cost of agents by determining locations in the regions for building a pathway. We provide a characterization of all strategyproof and anonymous mechanisms. For the social and maximum costs, we provide upper and lower bounds on the approximation ratios of strategyproof mechanisms.

PDF Details DOI

JBHI Journal 2024 Journal Article

DTP-Net: Learning to Reconstruct EEG Signals in Time-Frequency Domain by Multi-Scale Feature Reuse

Yan Pei
Jiahui Xu
Qianhao Chen
Chenhao Wang
Feng Yu
Lisan Zhang
Wei Luo

Electroencephalography (EEG) signals are prone to contamination by noise, such as ocular and muscle artifacts. Minimizing these artifacts is crucial for EEG-based downstream applications like disease diagnosis and brain-computer interface (BCI). This paper presents a new EEG denoising model, DTP-Net. It is a fully convolutional neural network comprising Densely-connected Temporal Pyramids (DTPs) placed between two learnable time-frequency transformations. In the time-frequency domain, DTPs facilitate efficient propagation of multi-scale features extracted from EEG signals of any length, leading to effective noise reduction. Comprehensive experiments on two public semi-simulated datasets demonstrate that the proposed DTP-Net consistently outperforms existing state-of-the-art methods on metrics including relative root mean square error (RRMSE) and signal-to-noise ratio improvement ( $\Delta$ SNR). Moreover, the proposed DTP-Net is applied to a BCI classification task, yielding an improvement of up to 5. 55% in accuracy. This confirms the potential of DTP-Net for applications in the fields of EEG-based neuroscience and neuro-engineering. An in-depth analysis further illustrates the representation learning behavior of each module in DTP-Net, demonstrating its robustness and reliability.

Details DOI

TCS Journal 2024 Journal Article

Greedy+Singleton: An efficient approximation algorithm for k-submodular knapsack maximization

Zhongzheng Tang
Jingwen Chen
Chenhao Wang

A k-submodular function takes k distinct, non-overlapping subsets of a ground set as input and outputs a value. It is a generalization of the well-known submodular function, which is the case when k = 1 and takes a single subset as input. We study the problem of maximizing a non-negative k-submodular function under a knapsack constraint. Greedy+Singleton is an algorithm that chooses the better solution between the fully greedy solution and the best single-element solution, with query complexity and running time of O ( n 2 k ). We show that Greedy+Singleton has an approximation ratio of 0. 273 for monotone functions, which improves the previous analysis of 0. 158 in the literature. Moreover, we give the first analysis of Greedy+Singleton for non-monotone k-submodular functions, and prove an approximation ratio of 0. 219.

Details DOI

IJCAI Conference 2024 Conference Paper

HeterGCL: Graph Contrastive Learning Framework on Heterophilic Graph

Chenhao Wang
Yong Liu
Yan Yang
Wei Li

Graph Contrastive Learning (GCL) has attracted significant research attention due to its self-supervised ability to learn robust node representations. Unfortunately, most methods primarily focus on homophilic graphs, rendering them less effective for heterophilic graphs. In addition, the complexity of node interactions in heterophilic graphs poses considerable challenges to augmentation schemes, coding architectures, and contrastive designs for traditional GCL. In this work, we propose HeterGCL, a novel graph contrastive learning framework with structural and semantic learning to explore the true potential of GCL on heterophilic graphs. Specifically, We abandon the random augmentation scheme that leads to the destruction of the graph structure, instead introduce an adaptive neighbor aggregation strategy (ANA) to extract topology-supervised signals from neighboring nodes at different distances and explore the structural information with an adaptive local-to-global contrastive loss. In the semantic learning module, we jointly consider the original nodes' features and the similarity between nodes in the latent feature space to explore hidden associations between nodes. Experimental results on homophilic and heterophilic graphs demonstrate that HeterGCL outperforms existing self-supervised and semi-supervised baselines across various downstream tasks.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

Mechanism Design for Reducing Agent Distances to Prelocated Facilities

Hau Chan
Xinliang Fu
Minming Li
Chenhao Wang

We consider a variant of facility location problems where the facility is prelocated at a specific position to serve the agents who are located on a real line. Because the facility cannot be relocated due to various constraints (e. g. , construction costs and requirements), the social planner considers the structural modification problem of adding short-cut edges to the real line (e. g. , shuttles between pairs of locations) for improving the accessibility or reducing costs of the agents to the facility, where the cost of an agent is measured by their shortest distance to the facility possibly using the short-cut edges. We focus on the mechanism design aspects of the problems where the agents’ locations are private. We propose several strategy-proof mechanisms that elicit true agent locations and minimize the total or maximum cost of agents. We provide approximation ratios for these mechanisms and lower bounds on the approximation ratios for total or maximum cost.

PDF

NeurIPS Conference 2024 Conference Paper

RWKU: Benchmarking Real-World Knowledge Unlearning for Large Language Models

Zhuoran Jin
Pengfei Cao
Chenhao Wang
Zhitao He
Hongbang Yuan
Jiachun Li
Yubo Chen
Kang Liu

Large language models (LLMs) inevitably memorize sensitive, copyrighted, and harmful knowledge from the training corpus; therefore, it is crucial to erase this knowledge from the models. Machine unlearning is a promising solution for efficiently removing specific knowledge by post hoc modifying models. In this paper, we propose a Real-World Knowledge Unlearning benchmark (RWKU) for LLM unlearning. RWKU is designed based on the following three key factors: (1) For the task setting, we consider a more practical and challenging unlearning setting, where neither the forget corpus nor the retain corpus is accessible. (2) For the knowledge source, we choose 200 real-world famous people as the unlearning targets and show that such popular knowledge is widely present in various LLMs. (3) For the evaluation framework, we design the forget set and the retain set to evaluate the model’s capabilities across various real-world applications. Regarding the forget set, we provide four four membership inference attack (MIA) methods and nine kinds of adversarial attack probes to rigorously test unlearning efficacy. Regarding the retain set, we assess locality and utility in terms of neighbor perturbation, general ability, reasoning ability, truthfulness, factuality, and fluency. We conduct extensive experiments across two unlearning scenarios, two models and six baseline methods and obtain some meaningful findings. We release our benchmark and code publicly at http: //rwku-bench. github. io for future work.

PDF Details DOI

TCS Journal 2023 Journal Article

Facility location games with ordinal preferences

Hau Chan
Zifan Gong
Minming Li
Chenhao Wang
Yingchao Zhao

In this paper we study a novel model of facility location games with ordinal preferences. There is a set of self-interested agents and a set of heterogeneous facilities. Each agent is located on a line and has an ordinal preference over the facilities. Our goal is to design strategyproof mechanisms that elicit true information (preferences and/or locations) from the agents and locate the facilities to minimize both maximum and total cost objectives as well as to maximize both minimum and total utility objectives. For the four possible objectives, we consider the 2-facility settings in which only preferences are private, or locations are private. For each possible combination of the objectives and settings, we provide lower and upper bounds on the approximation ratios of strategyproof mechanisms, which are asymptotically tight up to a constant. Furthermore, we extend some of the results to the multiple-facility setting. Finally, we discuss the generalization of our results when the agents can misreport both locations and preferences, and the case when the approximations are defined additively.

Details DOI

AAMAS Conference 2023 Conference Paper

Mechanism Design for Improving Accessibility to Public Facilities

Hau Chan
Chenhao Wang

We consider a variant of the facility location problems where agents are located on a real line and the facility is fixed at a designated location to serve the agents. As the facility cannot be relocated due to various constraints (e. g. , construction costs and regulatory requirements), the social planner considers the structural modification problem of adding a short-cut edge to the real line for improving the accessibility or costs of the agents to the facility, where the cost of an agent is measured by their shortest distance to the facility. For a mechanism design version of the structural modification problem where the agents are assumed to have private locations, we propose several strategy-proof mechanisms to elicit truthful locations from the agents and add a short-cut edge to (approximately) minimize the total cost or maximum cost of agents. We derive the upper bounds of these mechanisms and provide lower bounds on the approximation ratios for both objectives.

PDF

JAAMAS Journal 2022 Journal Article

Budget feasible mechanisms for facility location games with strategic facilities

Minming Li
Chenhao Wang
Mengqi Zhang

Abstract This paper studies the facility location game with payments, in which customers and facilities are located at publicly known locations on a line segment, and the facilities are strategic players. Each facility has an opening-cost as her private information, and she may strategically report it. Upon receiving the reports, the government uses a mechanism to select some facilities to open and pay them. The cost/utility of each customer depends on the distance to the nearest opened facility. Under a given budget B, which constrains the total payment, we derive upper and lower bounds on the approximation ratios of truthful budget feasible mechanisms for four utilitarian and egalitarian objectives, and investigate the case when augmented budget is allowed.

Details DOI

TCS Journal 2022 Journal Article

Mechanisms for dual-role-facility location games: Truthfulness and approximability

Xujin Chen
Minming Li
Changjun Wang
Chenhao Wang
Mengqi Zhang
Yingchao Zhao

This paper studies the dual-role-facility location game with generalized service costs, in which every agent plays a dual role of facility and customer, and is associated with a facility opening cost as his private information. The agents strategically report their opening costs to a mechanism which maps the reports to a set of selected agents and payments to them. Each selected agent opens his facility, incurs his opening cost and receives the payment the mechanism sets for him. Each unselected agent incurs a services cost that is determined by the set of selected agents in a very general way. The mechanism is truthful if under it no agent has an incentive to misreport. We provide a necessary and sufficient condition for mechanisms of the game to be truthful. This characterization particularly requires an invariant service cost for each unselected agent, which is a remarkable difference from related work in literature. As applications of this truthfulness characterization, we focus on the classic metric-space setting, in which agents' service costs equal their distances to closest open facilities. We present truthful mechanisms that minimize or approximately minimize the maximum cost among all agents and the total cost of all agents, respectively. Moreover, when the total payment cannot exceed a given budget, we prove, for both cost-minimization objectives, lower and upper bounds on approximation ratios of truthful mechanisms that satisfy the budget constraint.

Details DOI

TCS Journal 2022 Journal Article

Monotone k-submodular secretary problems: Cardinality and knapsack constraints

Zhongzheng Tang
Chenhao Wang
Hau Chan

In this paper, we consider the k-submodular secretary problem, in which the items or secretaries arrive one by one in a uniformly random order, and the goal is to select k disjoint sets of items, so as to maximize the expectation of a monotone non-negative k-submodular function. A decision for each item must be made immediately and irrevocably after its arrival: accept and assign it to one of the k dimensions, or reject it. We first show that, in the unconstrained setting, there is an offline algorithm that can be transformed to a k 2 k − 1 -competitive online algorithm, which is asymptotically the best possible. For the problem with cardinality constraints, we present online algorithms with provable performance guarantees for the total size constraint and individual size constraint settings that depend on the corresponding budget parameters. For the problem under a knapsack constraint, we provide a constant-competitive online algorithm.

Details DOI

AAAI Conference 2021 System Paper

CogNet: Bridging Linguistic Knowledge, World Knowledge and Commonsense Knowledge

Chenhao Wang
Yubo Chen
Zhipeng Xue
Yang Zhou
Jun Zhao

In this paper, we present CogNet, a knowledge base (KB) dedicated to integrating three types of knowledge: (1) linguistic knowledge from FrameNet, which schematically describes situations, objects and events. (2) world knowledge from YAGO, Freebase, DBpedia and Wikidata, which provides explicit knowledge about specific instances. (3) commonsense knowledge from ConceptNet, which describes implicit general facts. To model these different types of knowledge consistently, we introduce a three-level unified frame-styled representation architecture. To integrate free-form commonsense knowledge with other structured knowledge, we propose a strategy that combines automated labeling and crowdsourced annotation. At present, CogNet integrates 1, 000+ semantic frames from linguistic KBs, 20, 000, 000+ frame instances from world KBs, as well as 90, 000+ commonsense assertions from commonsense KBs. All these data can be easily queried and explored on our online platform, and free to download in RDF format for utilization under a CC-BY-SA 4. 0 license. The demo and data are available at http: //cognet. top/.

PDF Details

AAAI Conference 2021 Conference Paper

Facility’s Perspective to Fair Facility Location Problems

Chenhao Wang
Xiaoying Wu
Minming Li
Hau Chan

We study the problem faced by a decision maker who wants to locate a set of facilities on a real line and allocate agents/items to the facilities. The items have given locations on the line, and can only be assigned to one of their closest facilities. The facilities are controlled by managers, who have additive utility over the items. An optimal solution that maximizes the (utilitarian or egalitarian) social welfare of the facilities may present a very unbalanced allocation of the items to the facilities and hence be perceived as unfair. In this paper, we are interested in fair allocation among facility managers and consider the well-studied proportionality and envy-freeness fairness notions and their relaxations. We assess the availability, existence, approximability, and the quality (price of fairness) of fair solutions, where the quality measures the system efficiency loss under a fair allocation compared to the one that maximizes the social welfare. further, we show that one can find a Pareto-optimal solution in polynomial time.

PDF Details

AAMAS Conference 2021 Conference Paper

Fairness and Efficiency in Facility Location Problems with Continuous Demands

Chenhao Wang
Mengqi Zhang

In the facility location problem with continuous demands, where customers are continuously distributed on an area, a planner wants to locate the facilities and allocate the customers to their closest facilities under the proximity rule. In this work, we focus on the fairness and system efficiency from the facility’s perspective. Each facility is assumed to have a preference (represented as valuation function) over the subsets of customers. For the fairness of facilities, we provide approximation guarantees for the proportionality and envy-freeness. For the efficiency, we study the utilitarian and egalitarian social welfare. In addition, we are interested in quantifying the possible trade-offs between meeting the fairness criteria and maximizing social welfare, measured by the price of fairness.

PDF

IJCAI Conference 2021 Conference Paper

Game-theoretic Analysis of Effort Allocation of Contributors to Public Projects

Jared Soundy
Chenhao Wang
Clay Stevens
Hau Chan

Public projects can succeed or fail for many reasons such as the feasibility of the original goal and coordination among contributors. One major reason for failure is that insufficient work leaves the project partially completed. For certain types of projects anything short of full completion is a failure (e. g. , feature request on software projects in GitHub). Therefore, project success relies heavily on individuals allocating sufficient effort. When there are multiple public projects, each contributor needs to make decisions to best allocate his/her limited effort (e. g. , time) to projects while considering the effort allocation decisions of other strategic contributors and his/her parameterized utilities based on values and costs for the projects. In this paper, we introduce a game-theoretic effort allocation model of contributors to public projects for modeling effort allocation of strategic contributors. We study the related Nash equilibrium (NE) computational problems and provide NP-hardness results for the existence of NE and polynomial-time algorithms for finding NE in restricted settings. Finally, we investigate the inefficiency of NE measured by the price of anarchy and price of stability.

PDF Details DOI

IJCAI Conference 2021 Conference Paper

Mechanism Design for Facility Location Problems: A Survey

Hau Chan
Aris Filos-Ratsikas
Bo Li
Minming Li
Chenhao Wang

The study of approximate mechanism design for facility location has been in the center of research at the intersection of artificial intelligence and economics for the last decade, largely due to its practical importance in various domains, such as social planning and clustering. At a high level, the goal is to select a number of locations on which to build a set of facilities, aiming to optimize some social objective based on the preferences of strategic agents, who might have incentives to misreport their private information. This paper presents a comprehensive survey of the significant progress that has been made since the introduction of the problem, highlighting all the different variants and methodologies, as well as the most interesting directions for future research.

PDF Details DOI

AAMAS Conference 2021 Conference Paper

Multi-Robot Task Allocation-Complexity and Approximation

Haris Aziz
Hau Chan
Ágnes Cseh
Bo Li
Fahimeh Ramezani
Chenhao Wang

Multi-robot task allocation is one of the most fundamental classes of problems in robotics and is crucial for various real-world robotic applications such as search, rescue and area exploration. We consider the Single-Task robots and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each task requires at least a certain number of robots and each robot can work on at most one task and incurs an operational cost for each task. Our aim is to consider a natural computational problem of allocating robots to complete the maximum number of tasks subject to budget constraints. We consider budget constraints of three different kinds: (1) total budget, (2) task budget, and (3) robot budget. We provide a detailed complexity analysis including results on approximations as well as polynomial-time algorithms for the general setting and important restricted settings.

PDF

IJCAI Conference 2020 Conference Paper

Budgeted Facility Location Games with Strategic Facilities

Minming Li
Chenhao Wang
Mengqi Zhang

This paper studies the facility location games with payments, where facilities are strategic players. In the game, customers and facilities are located at publicly known locations on a line segment. Each selfish facility has an opening-cost as her private information, and she may strategically report it. Upon receiving the reports, the government uses a mechanism to select some facilities to open and pay to them. The cost/utility of each customer depends on the distance to the nearest opened facility. Under a given budget B, which constrains the total payment, we derive upper and lower bounds on the approximation ratios of truthful budget feasible mechanisms for four utilitarian and egalitarian objectives, and study the case when augmented budget is allowed.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Favorite-Candidate Voting for Eliminating the Least Popular Candidate in a Metric Space

Xujin Chen
Minming Li
Chenhao Wang

We study single-candidate voting embedded in a metric space, where both voters and candidates are points in the space, and the distances between voters and candidates specify the voters’ preferences over candidates. In the voting, each voter is asked to submit her favorite candidate. Given the collection of favorite candidates, a mechanism for eliminating the least popular candidate ﬁnds a committee containing all candidates but the one to be eliminated. Each committee is associated with a social value that is the sum of the costs (utilities) it imposes (provides) to the voters. We design mechanisms for ﬁnding a committee to optimize the social value. We measure the quality of a mechanism by its distortion, deﬁned as the worst-case ratio between the social value of the committee found by the mechanism and the optimal one. We establish new upper and lower bounds on the distortion of mechanisms in this single-candidate voting, for both general metrics and well-motivated special cases.

PDF Details

TCS Journal 2020 Journal Article

The efficiency of Nash equilibria in the load balancing game with a randomizing scheduler

Xujin Chen
Xiaodong Hu
Chenhao Wang
Xiaoying Wu

We study the efficiency of Nash equilibria for the load balancing game with a randomizing scheduler. In the game, we are given a set of facilities and a set of players along with a scheduler, where each facility is associated with a linear cost function, and the players are randomly ordered by the scheduler. Each player chooses exactly one of these facilities to fulfill his task, which incurs to him a cost depending on not only the cost function of the facility he chooses and the players who choose the same facility (as in a usual load balancing game), but also his uncertain position in the uniform random ordering. From an individual perspective, each player tries to choose a facility for optimizing his own objective that is determined by a certain decision-making principle. From a system perspective, it is desirable to minimize the maximum cost among all players, which is a commonly used criterion for load balancing. We estimate the price of anarchy and price of stability for this class of load balancing games under uncertainty, provided all players follow one of the four decision-making principles, namely the bottom-out, win-or-go-home, minimum-expected-cost, and minimax-regret principles. Our results show that the efficiency loss of Nash equilibria in these decentralized environments heavily rely on player's attitude toward the uncertainty.

Details DOI

AAMAS Conference 2019 Conference Paper

Truthful Mechanisms for Location Games of Dual-Role Facilities

Xujin Chen
Minming Li
Changjun Wang
Chenhao Wang
Yingchao Zhao

This paper is devoted to the facility location games with payments, where every agent plays a dual role of facility and customer. In this game, each selfish agent is located on a publicly known location in a metric space, and can allow a facility to be opened at his place. But the opening cost is his private information and he may strategically report this opening cost. Besides, each agent also bears a service cost equal to the distance to his nearest open facility. We are concerned with designing truthful mechanisms for the game, which, given agents’ reports, output a set of agents whose facilities could be opened, and a payment to each of these agents who opens a facility. The objective is to minimize (exactly or approximately) the social cost (the total opening and service costs) or the maximum agent cost of the outcome. We characterize the normalized truthful mechanisms for this game. Concerning the minimum social-cost objective, we give an optimal truthful mechanism without regard to time complexity, and show a small gap between the best known approximation ratio of polynomial-time truthful mechanisms for the game and that of polynomial-time approximation algorithms for the counterpart of pure optimization. For the minimum maximum-cost objective, we provide an optimal truthful mechanism which runs in polynomial time. We also investigate mechanism design for the game under a budget on the total payment.

PDF

YNIMG Journal 2018 Journal Article

Dynamic functional connectivity and its behavioral correlates beyond vigilance

Amiya Patanaik
Jesisca Tandi
Ju Lynn Ong
Chenhao Wang
Juan Zhou
Michael W.L. Chee

Fluctuations in resting-state functional connectivity and global signal have been found to correspond with vigilance fluctuations, but their associations with other behavioral measures are unclear. We evaluated 52 healthy adolescents after a week of adequate sleep followed by five nights of sleep restriction to unmask inter-individual differences in cognition and mood. Resting state scans obtained at baseline only, analyzed using sliding window analysis, consistently yielded two polar dynamic functional connectivity states (DCSs) corresponding to previously reported ‘low arousal’ and ‘high arousal’ states. We found that the relative temporal preponderance of two dynamic connectivity states (DCS) in well-rested participants, indexed by a median split of participants, based on the relative time spent in these DCS, revealed highly significant group differences in vigilance at baseline and its decline following multiple nights of sleep restriction. Group differences in processing speed and working memory following manipulation but not at baseline suggest utility of DCS in predicting cognitive vulnerabilities unmasked by a stressor like sleep restriction. DCS temporal predominance was uninformative about mood and sleepiness speaking to specificity in its behavioral predictions. Global signal fluctuation provided information confined to vigilance. This appears to be related to head motion, which increases during periods of low arousal.

Details DOI