Author name cluster

Xujin Chen

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.

14 papers

1 author row

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

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

IJCAI Conference 2017 Conference Paper

Efficient Mechanism Design for Online Scheduling (Extended Abstract)

Xujin Chen
Xiaodong Hu
Tie-Yan Liu
Weidong Ma
Tao Qin
Pingzhong Tang
Changjun Wang
Bo Zheng

This work concerns the mechanism design for online scheduling in a strategic setting. In this setting, each job is owned by a self-interested agent who may misreport the release time, deadline, length, and value of her job, while we need to determine not only the schedule of the jobs, but also the payment of each agent. We focus on the design of incentive compatible (IC) mechanisms, and study the maximization of social welfare (i. e. , the aggregated value of completed jobs) by competitive analysis. We first derive two lower bounds on the competitive ratio of any deterministic IC mechanism to characterize the landscape of our research: one bound is 5, which holds for equal-length jobs; the other bound is $\frac{\kappa}{\ln\kappa}+1-o(1)$, which holds for unequal-length jobs, where $\kappa$ is the maximum ratio between lengths of any two jobs. We then propose a deterministic IC mechanism and show that such a simple mechanism works very well for two models: (1) In the preemption-restart model, the mechanism can achieve the optimal competitive ratio of 5 for equal-length jobs and a near optimal ratio of $(\frac{1}{(1-\epsilon)^2}+o(1)) \frac{\kappa}{\ln\kappa}$ for unequal-length jobs, where $0<\epsilon<1$ is a small constant; (2) In the preemption-resume model, the mechanism can achieve the optimal competitive ratio of 5 for equal-length jobs and a near optimal competitive ratio (within factor 2) for unequal-length jobs.

PDF Details

I&C Journal 2017 Journal Article

Finding connected k -subgraphs with high density

Xujin Chen
Xiaodong Hu
Changjun Wang

Given an edge-weighted connected graph G on n vertices and a positive integer k ≤ n, a subgraph of G on k vertices is called a k-subgraph in G. We design combinatorial approximation algorithms for finding a connected k-subgraph in G such that its weighted density is at least a factor Ω ( max ⁡ { 1 / k, k 2 / n 2 } ) of the maximum weighted density among all k-subgraph in G (which are not necessarily connected), where max ⁡ { 1 / k, k 2 / n 2 } ≥ n − 2 / 3 implies an O ( n 2 / 3 ) -approximation ratio. We obtain improved O ( n 2 / 5 ) -approximation for unit weights. These particularly provide the first non-trivial approximations for the heaviest/densest connected k-subgraph problem on general graphs. We also give O ( n log ⁡ n ) -approximation for the problem on general weighted interval graphs.

Details DOI

TCS Journal 2016 Journal Article

Approximation for the minimum cost doubly resolving set problem

Xujin Chen
Xiaodong Hu
Changjun Wang

Locating source of diffusion in networks is crucial for controlling and preventing epidemic risks. It has been studied under various probabilistic models. In this paper, we study source location from a deterministic point of view by modeling it as the minimum cost doubly resolving set (DRS) problem, which is a strengthening of the well-known metric dimension problem. Let G be an undirected graph on n vertices, where each vertex has a nonnegative cost. A vertex subset S of G is a doubly resolving set (DRS) of G if for every pair of vertices u, v in G, there exist x, y ∈ S such that the difference of distances (in terms of number of edges) between u and x, y is not equal to the difference of distances between v and x, y. The minimum cost DRS problem consists of finding a DRS in G with minimum total cost. We establish Θ ( ln ⁡ n ) approximability of the minimum DRS problem on general graphs for both weighted and unweighted versions. This provides the first explicit lower and upper bounds on approximation for the minimum (cost) DRS, which are nearly tight. Moreover, we design the first known strongly polynomial time exact algorithms for the minimum cost DRS problem on general wheels and trees with additional constant k ≥ 0 edges.

Details DOI

JAIR Journal 2016 Journal Article

Efficient Mechanism Design for Online Scheduling

Xujin Chen
Xiaodong Hu
Tie-Yan Liu
Weidong Ma
Tao Qin
Pingzhong Tang
Changjun Wang
Bo Zheng

This paper concerns the mechanism design for online scheduling in a strategic setting. In this setting, each job is owned by a self-interested agent who may misreport the release time, deadline, length, and value of her job, while we need to determine not only the schedule of the jobs, but also the payment of each agent. We focus on the design of incentive compatible (IC) mechanisms, and study the maximization of social welfare (i.e., the aggregated value of completed jobs) by competitive analysis. We first derive two lower bounds on the competitive ratio of any deterministic IC mechanism to characterize the landscape of our research. We then propose a deterministic IC mechanism and show that such a simple mechanism works very well for both the preemption-restart model and the preemption-resume model. We show the mechanism can achieve the optimal competitive ratio of 5 for equal-length jobs and a near optimal competitive ratio (within a constant factor) for unequal-length jobs.

PDF Details DOI

IJCAI Conference 2015 Conference Paper

Selling Reserved Instances in Cloud Computing

Changjun Wang
Weidong Ma
Tao Qin
Xujin Chen
Xiaodong Hu
Tie-Yan Liu

In this paper, we study the problem of designing new mechanisms for selling reserved instances (also referred to as virtual machines) in cloud computing. Unlike the practice in today’s clouds in which users only have a few predefined options to reserve instances (i. e. , either 1-year reservation or 3-year reservation), we allow users to reserve resources for any length and from any time point in the future. Our goal is to maximize the social welfare. We propose two mechanisms, one for the case where all the jobs are tight (their lengths are exactly their reservation time intervals), and the other for the more general case where jobs are delayable and have some flexibility on their reservations. Both of the mechanisms are prompt in the sense that the acceptance and the payment for a job is determined at the very moment of its arrival. We use competitive analysis to evaluate the performance of our mechanisms, and show that both of the mechanisms have a competitive ratio of O(ln(kT)) under some mild assumption, where k (res. T) is the maximum ratio between per-instance-hour valuation (res. length) of any two jobs. We then prove that no algorithm can achieve a competitive ratio better than ln(2kT) under the same assumption. Therefore, our mechanisms are optimal within a constant factor.

PDF Details

TCS Journal 2014 Journal Article

Schedules for marketing products with negative externalities

Zhigang Cao
Xujin Chen
Changjun Wang

With the fast development of social network services, network marketing of products with externalities has been attracting more and more attention from both academia and business. The extensive study on network marketing mainly concerns with positive externalities. The focus of this paper is on the much less understood counterpart for negative externalities, where a consumer has lower incentive to buy a product as the product is possessed by more social network neighbors. For a seller who markets these products, it is desirable to have a good schedule which specifies an order of consumers he approaches. We design polynomial time algorithms that find marketing schedules for products with negative externalities. The goals are two-fold: maximizing the product sale and ensuring consumer regret-free decisions. We show that the maximization is NP-hard. Our algorithms achieve satisfactory performance guarantees, approximating the maximum within constant factors in most of the cases. Two of these algorithms provide regret-proof schedules, reaching an equilibrium state where no consumers regret their previous decisions. Our work is the first attempt to address these marketing problems from an algorithmic point of view.

Details DOI

TCS Journal 2013 Journal Article

Maximizing the minimum load: The cost of selfishness

Xujin Chen
Leah Epstein
Elena Kleiman
Rob van Stee

We consider a scheduling problem on m machines, where each job is controlled by a selfish agent. Each agent is only interested in minimizing its own cost, defined as the total load of the machine that its job is assigned to. We consider the objective of maximizing the minimum load (the value of the cover) over the machines. Unlike the regular makespan minimization problem, which was extensively studied in a game-theoretic context, this problem has not been considered in this setting before. We study the price of anarchy (poa) and the price of stability (pos). These measures are unbounded already for two uniformly related machines [11], and therefore we focus on identical machines. We show that the pos is 1, and derive tight bounds on the pure poa for m ≤ 7 and on the overall pure poa, showing that its value is exactly 1. 7. To achieve the upper bound of 1. 7, we make an unusual use of weighting functions. Finally, we show that the mixed poa grows exponentially with m for this problem. In addition, we consider a similar setting of selfish jobs with a different objective of minimizing the maximum ratio between the loads of any pair of machines in the schedule. We show that under this objective the pos is 1 and the pure poa is 2, for any m ≥ 2.

Details DOI

TCS Journal 2013 Journal Article

Reducing price of anarchy of selfish task allocation with more selfishness

Xujin Chen
Xiaodong Hu
Weidong Ma
Changjun Wang

In this paper we consider the task allocation problem from a new game theoretic perspective. We assume that tasks and machines are both controlled by selfish agents with two distinct objectives, which stands in contrast to the passive role of machines in the traditional model of selfish task allocation. To characterize the outcome of this new game where two classes of players interact, we introduce the concept of dual equilibrium. We prove that the price of anarchy with respect to dual equilibria is 1. 4, which is considerably smaller than the counterpart 2 in the traditional model. Our study shows that activating more freedom and selfishness in a game may bring about a better global outcome.

Details DOI

TCS Journal 2012 Journal Article

Pairwise cooperations in selfish ring routing for minimax linear latency

Xujin Chen
Xiaodong Hu
Weidong Ma

This paper studies the selfish routing game in ring networks with a load-dependent linear latency on each link. We adopt the asymmetric atomic routing model. Each player selfishly chooses a route to connect his source-destination pair, aiming at the lowest latency of his route, while the system objective is to minimize the maximum latency among all routes of players. The effectiveness of these routing games is often measured by the price of anarchy (PoA), the worst-case ratio between the maximum latencies in a Nash equilibrium (NE) and in a system optimum, where NE refers to a “stable state” among all players, from which no player has the incentive to deviate unilaterally. In classical setting, no cooperation is allowed and 16 stands as the current best upper bound on the PoA of such selfish ring routing. In this paper we show that the PoA is at most 10. 16 provided cooperations within pairs of players are allowed, where any two players could change their routes simultaneously if neither would experience a longer latency and at least one would experience a shorter latency.

Details DOI

TCS Journal 2011 Journal Article

Deterministic risk control for cost-effective network connections

Eduardo Álvarez-Miranda
Xujin Chen
Jie Hu
Xiaodong Hu
Alfredo Candia-Véjar

This paper considers the minimum connection problem in networks with uncertain data. In such a network it is assumed that one can establish a link e by paying a cost c e in a given interval [ c e −, c e + ] while taking a risk ( c e + − c e ) / ( c e + − c e − ) of link failure. We develop polynomial time algorithms for minimum cost network connection with paths or spanning trees under risk-sum constraints.

Details DOI