Minming Li

AAAI Conference 2026 Conference Paper

Centralized Group Equitability and Individual Envy-Freeness in the Allocation of Indivisible Items

• Ying Wang
• Jiaqian Li
• Tianze Wei
• Hau Chan
• Minming Li

We study the fair allocation of indivisible items to groups of agents from the perspectives of both the agents and a centralized allocator. In our setting, the centralized allocator aims to ensure that the allocation is fair both among the groups and between individual agents. This setting applies to many real-world scenarios, such as when a school administrator allocates resources (e.g., office spaces and supplies) to staff members within departments or when a city council allocates limited housing units to families in need across different communities. To ensure fairness between agents, we consider the classical notion of envy-freeness (EF). To ensure fairness among groups, we introduce the notion of centralized group equitability (CGEQ), which captures fairness for groups from the centralized allocator’s perspective. Because an EF or CGEQ allocation does not always exist in general, we consider their natural relaxations: envy-freeness to one item (EF1) and centralized group equitability up to one item (CGEQ1). For different classes of valuation functions of the agents and the centralized allocator, we show that allocations satisfying both EF1 and CGEQ1 always exist, and we design efficient algorithms to compute such allocations. We also consider the centralized group maximin share (CGMMS) from the centralized allocator's perspective as a group-level fairness objective with EF1 for agents, and present several results.

JAAMAS Journal 2026 Journal Article

Correction: Heterogeneous facility location games with fractional preferences and limited resources

• Jiazhu Fang
• Qizhi Fang
• Minming Li

AAAI Conference 2026 Conference Paper

Fairness and Stability for Shared Resource Allocation Problems

• Jiazhu Fang
• Qizhi Fang
• Minming Li
• Wenjing Liu

This paper investigates the problem of shared resource allocation, where a set of agents must be assigned to heterogeneous resources, with each agent allocated exactly one resource and each resource potentially shared by multiple agents. An agent’s utility for a given resource is jointly determined by the resource's type and the number of agents sharing it. We focus on two fundamental classes of monotone valuations: monotone nondecreasing and monotone nonincreasing, where an agent’s utility respectively increases or decreases with the number of agents sharing the resource. Within this shared resource framework, we examine classical notions of fairness and stability, including maximin-share fairness, envy-freeness, Nash stability, and two epistemic relaxations—epistemic envy-freeness and epistemic Nash stability—as well as swap stability. We propose formal definitions adapted to this setting and systematically analyze the relationships among these concepts. The primary contributions of this work consist of establishing existence and computational complexity results for each notion under both monotonicity assumptions and developing polynomial-time algorithms in cases where fair or stable allocations are guaranteed to exist.

AAMAS Conference 2026 Conference Paper

Mechanism Design for Efficient Task Allocation

• Zifan Gong
• Minming Li
• Houyu Zhou

Task allocation involves a group of agents contributing to various tasks and has been well-studied in resource allocation and related fields. Inmanyscenarios, tasksaredistributedacrossdifferentareas, such as medical jobs in urban and rural regions, and sometimes different tasks require different skill sets. A key challenge is the tendency of agents to choose easier tasks or more prosperous areas for their own benefit. This self-interest can create imbalances, leaving challenging tasks undone or leading to uneven resource distribution, such as the shortage of rural doctors. To address this problem, we study task allocation using a gametheoretic approach. We model the problem as task allocation games with different tasks and a group of rational, identical agents who strategically select tasks to minimize their workloads. Our goal is to design mechanisms that ensure all workloads are completed in every Nash equilibrium. We show that achieving this requires implementing positive or negative incentives. We then propose effective mechanisms that leverage both types of incentives and extend our results to scenarios with multiple tasks and heterogeneous agents.

AAAI Conference 2026 Conference Paper

Tree-Based Stochastic Optimization for Solving Large-Scale Urban Network Security Games

• Shuxin Zhuang
• Linjian Meng
• Shuxin Li
• Minming Li
• Youzhi Zhang

Urban Network Security Games (UNSGs), which model the strategic allocation of limited security resources on city road networks, are critical for urban safety. However, finding a Nash Equilibrium (NE) in large-scale UNSGs is challenging due to their massive and combinatorial action spaces. One common approach to addressing these games is the Policy-Space Response Oracle (PSRO) framework, which requires computing best responses (BR) at each iteration. However, precisely computing exact BRs is impractical in large-scale games, and employing reinforcement learning to approximate BRs inevitably introduces errors that limit the overall effectiveness of the PSRO methods. Recent advancements in leveraging non-convex stochastic optimization to approximate an NE offer a promising alternative to the burdensome BR computation. However, utilizing existing stochastic optimization techniques with an unbiased loss function for UNSGs remains challenging because the action spaces are too vast to be effectively represented by neural networks. To address these issues, we introduce Tree-based Stochastic Optimization (TSO), a framework that bridges the gap between the stochastic optimization paradigm for NE-finding and the demands of UNSGs. Specifically, we employ the tree-based action representation that maps the whole action space onto a tree structure, addressing the challenge faced by neural networks in representing actions when the action space cannot be enumerated. We then incorporate this representation into the loss function and theoretically demonstrate its equivalence to the unbiased loss function. To further enhance the quality of the converged solution, we introduce a sample-and-prune mechanism that reduces the risk of being trapped in suboptimal local optima. Extensive experimental results indicate the superiority of TSO over other baseline algorithms in addressing the UNSGs.

SODA Conference 2025 Conference Paper

A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design

• Matteo Castiglioni
• Junjie Chen
• Minming Li
• Haifeng Xu
• Song Zuo

NeurIPS Conference 2025 Conference Paper

Adaptive and Multi-scale Affinity Alignment for Hierarchical Contrastive Learning

• Jiawei Huang
• Minming Li
• Hu Ding

Contrastive self-supervised learning has emerged as a powerful paradigm for extracting meaningful representations without labels. While effective at capturing broad categorical distinctions, current methods often struggle to preserve the fine-grained and hierarchical relationships inherent in real-world data. From the perspective of semantic alignment, conventional contrastive learning aligns representations to semantic structure at a global level, treating the entire embedding space uniformly and frequently overlooking rich local structural information. In this paper, we propose \emph{Adaptive Multi-scale Affinity alignment (AMA-alignment)}, a framework that introduces localized contrastive objectives and a dynamic multi-scale optimization strategy to adaptively identify and refine poorly aligned regions within the embedding space. Although our model is inherently more complex due to its \emph{multi-scale} and \emph{adaptive} design, we provide the theoretical guarantees indicating that its convergence rate remains comparable to that of standard smooth non-convex optimization. We conduct a set of experiments on diverse benchmarks to show that AMA-alignment can effectively preserve hierarchical structure; moreover, AMA-alignment also outperforms existing contrastive methods on a range of downstream tasks.

NeurIPS Conference 2025 Conference Paper

Bootstrap Your Uncertainty: Adaptive Robust Classification Driven by Optimal-Transport

• Jiawei Huang
• Minming Li
• Hu Ding

Deep learning models often struggle with distribution shifts between training and deployment environments. Distributionally Robust Optimization (DRO) offers a promising framework by optimizing worst-case performance over a set of candidate distributions, which is called as the \emph{uncertainty set}. However, the efficacy of DRO heavily depends on the design of uncertainty set, and existing methods often perform suboptimally due to inappropriate and inflexible uncertainty sets. In this work, we first propose a novel perspective that casts entropy-regularized Wasserstein DRO as a dynamic process of distributional exploration and semantic alignment, both driven by optimal transport (OT). This unified viewpoint yields two key new techniques: \emph{semantic calibration}, which bootstraps semantically meaningful transport costs via inverse OT, and \emph{adaptive refinement}, which adjusts uncertainty set using OT-driven feedback. Together, these components form an exploration-and-feedback system, where the transport costs and uncertainty set evolve jointly during training, enabling the model to better adapt to potential distribution shifts. Moreover, we provide an in-depth analysis on this adaptive process and prove the theoretical convergence guarantee. Finally, we present our experimental results across diverse distribution shift scenarios, which demonstrate that our approach significantly outperforms existing methods, achieving state-of-the-art robustness.

IJCAI Conference 2025 Conference Paper

EFX Feasible Scheduling for Time-dependent Resources

• Jiazhu Fang
• Qizhi Fang
• Minming Li
• Wenjing Liu

In this paper, we study a fair resource scheduling problem involving the assignment of a set of interval jobs among a group of heterogeneous machines. Each job is associated with a release time, a deadline, and a processing time. A machine can process a job if the entire processing period falls within the release time and deadline of the job. Each machine can process at most one job at any given time, and different jobs yield different utilities for the machines. The goal is to find a fair and efficient schedule of the jobs. We discuss the compatibility between envy-freeness up to any item (EFX) and various efficiency concepts. Additionally, we present polynomial-time algorithms for various settings.

AAAI Conference 2025 Conference Paper

Facility Location Games with Optional Preferences: A Revisit

• Xingchen Sha
• Shuyu Bao
• Hau Chan
• Vincent Chau
• Ken C. K. Fong
• Minming Li

We study the k-facility location games with optional preferences on the line. In the games, each strategic agent has a public location preference on the k facility locations and a private optional preference on the preferred/acceptable set of facilities out of the k facilities. Our goal is to design strategyproof mechanisms to elicit agents’ optional preferences and locate k facilities to minimize the social or maximum cost of agents based on their facility preferences and public agent locations. We consider two variants of the facility location games with optional preferences: the Min variant and the Max variant where the agent’s cost is defined as their distance to the closest acceptable facility and the farthest acceptable facility, respectively. For the Min variant, we present two deterministic strategyproof mechanisms to minimize the maximum cost and social cost with k ≥ 3 facilities, achieving approximation ratios of 3 and 2n+1 respectively. We complement the results by establishing lower bounds of 3/2 and n/4 for the approximation ratios achievable by any deterministic strategyproof mechanisms for the maximum cost and social cost, respectively. We then improve our results in a special setting of the Min variant where there are exactly three facilities and present two deterministic strategyproof mechanisms to minimize the maximum cost and social cost. For the Max variant, we present an optimal deterministic strategyproof mechanism for the maximum cost and a k-approximation deterministic strategyproof mechanism for the social cost.

AAMAS Conference 2025 Conference Paper

Group-fair Facility Location Games with Externalities

• Minming Li
• Cheng Peng
• Ying Wang
• Houyu Zhou

We study facility location games with externalities where agents are located on a real line and divided into groups. The cost of an agent is affected by the facility location and their group members. The goal is to design mechanisms to locate a facility to approximately optimize group-fair objectives while eliciting the agents’ locations truthfully. We consider two types of group interactions: competitive and collaborative, and two group-fair objectives, minimizing the maximum total group cost and minimizing the maximum average group cost. For each scenario, we analyze classic mechanisms, presenting their approximation ratios, and introduce new mechanisms that achieve improved approximation ratios. Additionally, we establish tight lower bounds for each setting, demonstrating that our mechanisms are the best possible.

JAAMAS Journal 2025 Journal Article

Heterogeneous facility location games with fractional preferences and limited resources

• Jiazhu Fang
• Qizhi Fang
• Minming Li

Abstract In this paper, we study the heterogeneous facility location game with fractional preferences under resource constraints. In this model, a group of agents are positioned along the interval [0, 1], where each agent has position information and fractional preferences indicated as support weights for facilities. Our main focus is to design mechanisms that choose and locate one facility out of two facilities while motivating agents to truthfully report their information, aiming to approximately maximize the social utility, defined as the sum of utilities of all agents. Based on the types of private information held by agents, we consider three different settings. For the known-preferences setting, we provide a deterministic group strategy-proof mechanism with 2-approximation and a randomized group strategy-proof mechanism with \(\frac{4}{3}\) -approximation. We also provide lower bounds of 2 on the approximation ratio for any deterministic strategy-proof mechanism and 1. 043 for any randomized strategy-proof mechanism. For the known-positions setting and the general setting, we present a deterministic group strategy-proof mechanism with 6-approximation and a randomized strategy-proof mechanism with 4-approximation, respectively. Furthermore, we give lower bounds of 1. 554 for any deterministic strategy-proof mechanism and 1. 2 for any randomized strategy-proof mechanism in the known-positions setting. Finally, we extend the model to the scenario of choosing k facilities out of m facilities. For the known-preferences setting, we provide a 2-approximate deterministic group strategy-proof mechanism, which is also the best deterministic strategy-proof mechanism. For the known-positions setting, when \(k \ge 2\), we give a lower bound of \(2-\frac{1}{k}\) for any deterministic strategy-proof mechanism.

ECAI Conference 2025 Conference Paper

Mechanism Design for Facility Location Problems with Capacity Constraints in Bounded Location Space

• Xingchen Sha
• Hau Chan
• Vincent Chau
• Ken C. K. Fong
• Minming Li
• Wai Lun Lo

We consider the k-facility location problems with capacity constraints in bounded location space from the mechanism design perspective. In this problem, we seek to locate k capacity constrained facilities in a bounded interval (i. e. , B=[bl, br]) to serve agents, who have preferences on the ideal locations of the facilities in the interval. Our goal is to design strategyproof mechanisms to elicit agents’ true ideal locations and locate facilities that minimize the social cost and maximum cost, which are defined to be the sum and the maximum of the agents’ costs (i. e. , agents’ distances to their facilities), respectively. For the equal capacity setting without spare capacity (i. e. , all the agents can be served exactly), we provide a deterministic strategyproof mechanism. For any bounded interval (i. e. , bl, br∈R), our mechanism has approximation ratios of n-1 for the social cost and 4 for the maximum cost with k≥3 facilities and n≥3 agents. We also establish lower bounds of n/2 for the social cost by a common class of deterministic mechanisms that order agents from left to right, and 2 for the maximum cost by any deterministic mechanism. Our mechanism also achieves tight bounds for both costs with k<3 facilities. We then consider the equal capacity setting with spare capacity and the arbitrary capacity setting without spare capacity. For these two settings and any bounded interval, we provide randomized strategyproof mechanisms with approximation ratios of n/2 for the social cost and 2 for the maximum cost with any number of facilities. We complement this result by establishing lower bounds of 5/3 for the social cost and 3/2 for the maximum cost.

AAAI Conference 2025 Conference Paper

Non-stochastic Budgeted Online Pricing with Semi-Bandit Feedback

• Xiang Liu
• Hau Chan
• Minming Li
• Weiwei Wu
• Long Tran-Thanh

We consider a general non-stochastic online pricing bandit setting in a procurement scenario where a buyer with a budget wants to procure items from a fixed set of sellers to maximize the buyer's reward by dynamically offering purchasing prices to the sellers, where the sellers' costs and values at each time period can change arbitrarily and the sellers determine whether to accept the offered prices to sell the items. This setting models online pricing scenarios of procuring resources or services in multi-agent systems. We first consider the offline setting when sellers' costs and values are known in advance and investigate the best fixed-price policy in hindsight. We show that it has a tight approximation guarantee with respect to the offline optimal solutions. In the general online setting, we propose an online pricing policy, Granularity-based Pricing (GAP), which exploits underlying side-information from the feedback graph when the budget is given as the input. We show that GAP achieves an upper bound of O(n{v_{max}}{c_{min}}sqrt{B/c_{min}}ln B) on the alpha-regret where n, v_{max}, c_{min}, and B are the number, the maximum value, the minimum cost of sellers, and the budget, respectively. We then extend it to the unknown budget case by developing a variant of GAP, namely Doubling-GAP, and show its alpha-regret is at most O(n{v_{max}}{c_{min}}sqrt{B/c_{min}}ln2 B). We also provide an alpha-regret lower bound Omega(v_{max}sqrt{Bn/c_{min}}) of any online policy that is tight up to sub-linear terms. We conduct simulation experiments to show that the proposed policy outperforms the baseline algorithms.

AIJ Journal 2025 Journal Article

On the computation of mixed strategies for security games with general defending requirements

• Rufan Bai
• Haoxing Lin
• Xiaowei Wu
• Minming Li
• Weijia Jia

The Stackelberg security game is played between a defender and an attacker, where the defender needs to allocate a limited amount of resources to multiple targets in order to minimize the loss due to adversarial attacks by the attacker. While allowing targets to have different values, classic settings often assume uniform requirements for defending the targets. This enables existing results that study mixed strategies (randomized allocation algorithms) to adopt a compact representation of the mixed strategies. In this work, we initiate the study of mixed strategies for security games in which the targets can have different defending requirements. In contrast to the case of uniform defending requirements, for which an optimal mixed strategy can be computed efficiently, we show that computing the optimal mixed strategy is NP-hard for the general defending requirements setting. However, we show strong upper and lower bounds for the optimal mixed strategy defending result. Additionally, we extend our analysis to study uniform attack settings on these security games. We propose an efficient close-to-optimal Patching algorithm that computes mixed strategies using only a few pure strategies. Furthermore, we study the setting when the game is played on a network and resource sharing is enabled between neighboring targets. We show the effectiveness of our algorithm in various large real-world datasets, addressing both uniform and general defending requirements.

IJCAI Conference 2024 Conference Paper

A Complete Landscape of EFX Allocations on Graphs: Goods, Chores and Mixed Manna

• Yu Zhou
• Tianze Wei
• Minming Li
• Bo Li

We study envy-free up to any item (EFX) allocations on graphs where vertices and edges represent agents and items respectively. An agent is only interested in items that are incident to her and all other items have zero marginal values to her. Christodoulou et al. first proposed this setting and studied the case of goods. We extend this setting to the case of mixed manna where an item may be liked or disliked by its endpoint agents. In our problem, an agent has an arbitrary valuation over her incident items such that the items she likes have non-negative marginal values to her and those she dislikes have non-positive marginal values. We provide a complete study of the four notions of EFX for mixed manna in the literature, which differ by whether the removed item can have zero marginal value. We prove that an allocation that satisfies the notion of EFX where the virtually-removed item could always have zero marginal value may not exist and determining its existence is NP-complete, while one that satisfies any of the other three notions always exists and can be computed in polynomial time. We also prove that an orientation (i. e. , a special allocation where each edge must be allocated to one of its endpoint agents) that satisfies any of the four notions may not exist, and determining its existence is NP-complete.

AAAI Conference 2024 Conference Paper

Altruism in Facility Location Problems

• Houyu Zhou
• Hau Chan
• Minming Li

We study the facility location problems (FLPs) with altruistic agents who act to benefit others in their affiliated groups. Our aim is to design mechanisms that elicit true locations from the agents in different overlapping groups and place a facility to serve agents to approximately optimize a given objective based on agents' costs to the facility. Existing studies of FLPs consider myopic agents who aim to minimize their own costs to the facility. We mainly consider altruistic agents with well-motivated group costs that are defined over costs incurred by all agents in their groups. Accordingly, we define Pareto strategyproofness to account for altruistic agents and their multiple group memberships with incomparable group costs. We consider mechanisms satisfying this strategyproofness under various combinations of the planner's objectives and agents' group costs. For each of these settings, we provide upper and lower bounds of approximation ratios of the mechanisms satisfying Pareto strategyproofness.

IJCAI Conference 2024 Conference Paper

Budget Feasible Mechanisms: A Survey

• Xiang Liu
• Hau Chan
• Minming Li
• Weiwei Wu

In recent decades, the design of budget feasible mechanisms for a wide range of procurement auction settings has received significant attention in the Artificial Intelligence (AI) community. These procurement auction settings have practical applications in various domains such as federated learning, crowdsensing, edge computing, and resource allocation. In a basic procurement auction setting of these domains, a buyer with a limited budget is tasked with procuring items (\eg, goods or services) from strategic sellers, who have private information on the true costs of their items and incentives to misrepresent their items' true costs. The primary goal of budget feasible mechanisms is to elicit the true costs from sellers and determine items to procure from sellers to maximize the buyer valuation function for the items and ensure that the total payment to the sellers is no more than the budget. In this survey, we provide a comprehensive overview of key procurement auction settings and results of budget feasible mechanisms. We provide several promising future research directions.

AAMAS Conference 2024 Conference Paper

Facility Location Games with Scaling Effects

• Yu He
• Alexander Lam
• Minming Li

We take the classic facility location problem and consider a variation, in which each agent’s individual cost function is equal to their distance from the facility multiplied by a scaling factor which is determined by the facility placement. In addition to the general class of continuous scaling functions, we also provide results for piecewise linear scaling functions which can effectively approximate or model the scaling of many real world scenarios. We focus on the objectives of total and maximum cost, describing the computation of the optimal solution. We then move to the approximate mechanism design setting, observing that the agents’ preferences may no longer be single-peaked. Consequently, we characterize the conditions on scaling functions which ensure that agents have single-peaked preferences. Under these conditions, we find results on the total and maximum cost approximation ratios achievable by strategyproof and anonymous mechanisms.

AAMAS Conference 2024 Conference Paper

Facility Location Games with Task Allocation

• Zifan Gong
• Minming Li
• Houyu Zhou

Facility location games have been studied extensively but most are about locating facilities given agents’ profiles. However, in some real-life scenarios, the facility’s location may be fixed already. When there are multiple facilities the strategic agents will always go to the closest one, resulting in the remote facilities unused. In this paper, we introduce the model that includes two facilities and 𝑛 rational agents. There is one task at each facility to be done. Each agent will select one task and aims to minimize the amount of work assigned to her. Our goal is to design the allocation rules to achieve social optimality, i. e. , every Nash equilibrium guarantees that every task can be completed. We show that no allocation rule can achieve social optimality without positive/negative incentives. For negative incentives, we propose a class of allocation rules with dummy work, where social optimality can be achieved, and no worker does the dummy work. For positive incentives, we first give a simple rule that achieves social optimality and propose a more complex rule to achieve the minimum subsidy.

AAAI Conference 2024 Conference Paper

Fair Allocation of Items in Multiple Regions

• Houyu Zhou
• Tianze Wei
• Biaoshuai Tao
• Minming Li

We initiate the study of fair allocation with the set of divisible or indivisible items distributed in multiple regions. The key requirement is that each agent can only obtain items from one region. In this work, we consider two kinds of fairness concepts: envy-based notions including envy-freeness (EF) and envy-freeness up to one/any item (EF1/EFX), and share-based notions including proportionality (PROP) and proportionality up to one/any item (PROP1/PROPX). On the negative side, we show NP-hardness and inapproximability results about the aforementioned fairness notions. On the positive side, we propose several algorithms to compute the partial allocations that satisfy envy-based notions and allocations that approximate the above fairness notions.

AAMAS Conference 2024 Conference Paper

Fair and Efficient Division of a Discrete Cake with Switching Utility Loss

• Zheng Chen
• Bo Li
• Minming Li
• Guochuan Zhang

Cake cutting is a widely studied model for allocating resources with temporal or spatial structures among agents. Recently, a new line of research has emerged that focuses on the discrete variant, where the resources are indivisible and connected by a path. In some real-world applications, the resources are interdependent, and dividing the cake may reduce their effectiveness. In this paper, we introduce a model that captures the effect of division as switching utility loss and investigate the tradeoff between fairness and efficiency for various settings. Specifically, we measure fairness and efficiency using the popular notions of envy-freeness up to one item (EF1) and social welfare, respectively. The goal of our study is to understand how much social welfare must be sacrificed to ensure EF1 allocations and design polynomial-time algorithms that can compute EF1 allocations with the best possible social welfare guarantee.

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.

AAMAS Conference 2024 Conference Paper

Positive Intra-Group Externalities in Facility Location

• Ying Wang
• Houyu Zhou
• Minming Li

We study facility location games with multiple groups in one dimension where an agent’s utility is not only decided by the distance from the facility but also by their group members. The positive effect of the interactions within a group is captured by positive intra-group externalities. Our goal is to design a mechanism that is non-manipulable and respects unanimity while (approximately) optimizing an objective function. We consider three types of manipulation, misreporting only the location, misreporting only the group membership, and misreporting both, under two social objectives, the social utility and the minimum utility. For both objectives, we achieve nearly tight bounds by either designing new mechanisms or extending the existing mechanisms in terms of the first two types of manipulation. As to the negative result, we show that strategyproofness and unanimity are incompatible when each agent can misreport both the location and the group membership, which is independent of the objective functions.

IJCAI Conference 2024 Conference Paper

Public Event Scheduling with Busy Agents

• Bo Li
• Lijun Li
• Minming Li
• Ruilong Zhang

We study a public event scheduling problem, where multiple public events are scheduled to coordinate the availability of multiple agents. The availability of each agent is determined by solving a separate flexible interval job scheduling problem, where the jobs are required to be preemptively processed. The agents want to attend as many events as possible, and their agreements are considered to be the total length of time during which they can attend these events. The goal is to find a schedule for events as well as the job schedule for each agent such that the total agreement is maximized. We first show that the problem is NP-hard, and then prove that a simple greedy algorithm achieves 1/2-approximation when the whole timeline is polynomially bounded. Our method also implies a (1-1/e)-approximate algorithm for this case. Subsequently, for the general timeline case, we present an algorithmic framework that extends a 1/alpha-approximate algorithm for the one-event instance to the general case that achieves 1/(alpha+1)-approximation. Finally, we give a polynomial time algorithm that solves the one-event instance, and this implies a 1/2-approximate algorithm for the general case.

AAAI Conference 2024 Conference Paper

Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems

• Jiaqian Li
• Minming Li
• Hau Chan

We study the group-fair obnoxious facility location problems from the mechanism design perspective where agents belong to different groups and have private location preferences on the undesirable locations of the facility. Our main goal is to design strategyproof mechanisms that elicit the true location preferences from the agents and determine a facility location that approximately optimizes several group-fair objectives. We first consider the maximum total and average group cost (group-fair) objectives. For these objectives, we propose deterministic mechanisms that achieve 3-approximation ratios and provide matching lower bounds. We then provide the characterization of 2-candidate strategyproof randomized mechanisms. Leveraging the characterization, we design randomized mechanisms with improved approximation ratios of 2 for both objectives. We also provide randomized lower bounds of 5/4 for both objectives. Moreover, we investigate intergroup and intragroup fairness (IIF) objectives, addressing fairness between groups and within each group. We present a mechanism that achieves a 4-approximation for the IIF objectives and provide tight lower bounds.

AAMAS Conference 2023 Conference Paper

Altruism in Facility Location Problems

• Houyu Zhou
• Hau Chan
• Minming Li

We study the facility location problems (FLPs) with altruistic agents who act to benefit others in their affiliated groups. Our aim is to design mechanisms that elicit true locations from the agents in different overlapping groups and locate a facility to serve agents to approximately optimize a given objective based on agents’ costs to the facility. Existing studies of FLPs consider myopic agents who aim to minimize their own costs to the facility, while we mainly consider altruistic agents who consider the group costs incurred by all agents in their groups. Accordingly, we define Pareto strategyproofness to account for this new type of agents and their multiple group memberships with incomparable group costs. We consider mechanisms satisfying this strategyproofness under various combinations of the planner’s objectives and agents’ group costs. For each of these settings, we provide upper and lower bounds of approximation ratios of the mechanisms satisfying the Pareto strategyproofness.

AIJ Journal 2023 Journal Article

Budget-feasible mechanisms for proportionally selecting agents from groups

• Xiang Liu
• Hau Chan
• Minming Li
• Weiwei Wu
• Yingchao Zhao

In many social domains involving collective decision-making (e. g. , committee selection and survey sampling), it is often desirable to select individuals from different population groups to achieve proportional representation (e. g. , to represent the opinions of each group). For instance, in the selection of a committee (e. g. , to form a working group within a company), the planner would like to select agents from different groups to represent their respective groups proportionally. Typically, there are intrinsic private costs for agents to represent their groups, and the planner would like to compensate the selected agents via some form of payments, which is constrained by the planner's available budget. As the costs are unknown to the planner, the planner is required to design incentive mechanisms to elicit agents' real costs and provide payments (or monetary incentives) to the selected agents to ensure proportional representation and the total payments do not exceed the budget. Such a mechanism design setting falls into the budget-feasible mechanism design paradigm. However, existing budget-feasible mechanisms only consider all agents to be in the same group with non-proportional objectives. To study the above-mentioned setting, we consider the problem of designing budget-feasible mechanisms for selecting agents with private costs from various groups to ensure proportional representation, where the minimum proportion of the overall value of the selected agents from each group is maximized. We study this problem by first considering the setting with homogeneous agents who have identical values to the planner. Depending on agents' membership in the groups, we consider two models: a single group model where each agent belongs to only one group, and a multiple group model where each agent may belong to multiple groups. We propose novel budget-feasible proportion-representative mechanisms for these models that require different selection methods, i. e. , a novel greedy mechanism that considers all possible proportion ratios for the single group model and a novel mechanism that leverages the Max-Flow algorithm to evaluate the proportional representation for the multiple group model, to choose representative agents from each group. The proposed mechanisms guarantee theoretical properties of individual rationality, budget-feasibility, truthfulness, and approximation performance on maximizing the minimum proportional representation of each group. We also provide a matching lower bound for budget-feasible proportion-representative mechanisms. Finally, we non-trivially extend these mechanisms to the settings of heterogeneous agents who can have different values to the planner under the two models.

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.

AAMAS Conference 2023 Conference Paper

Facility Location Games with Thresholds

• Houyu Zhou
• Guochuan Zhang
• Lili Mei
• Minming Li

In classic facility location games, a facility is to be placed based on the reported locations from agents. Each agent wants to minimize the cost (distance) between her location and the facility. In real life, the cost of an agent may not strictly increase with the distance. In this paper, we introduce two types of thresholds to the agent’s cost. For the model with lower thresholds, the agent’s cost is 0 if the distance is within the threshold, otherwise it increases linearly until the value 1. Similarly, for the model with upper thresholds, the cost is 1 if the distance is beyond the threshold, otherwise it is a linear function with the value from 0 to 1. We aim to prevent the agent from misreporting her location while optimizing social objectives in both models. For the first model, we design a strategyproof mechanism optimal for the social cost objective and a strategyproof mechanism with an approximation ratio of 3 for the maximum cost objective. For the second model, we use the median mechanism for the social cost with a threshold-based approximation ratio and design a new mechanism for the maximum cost with tight bounds. We also show lower bounds for both models. Finally, we derive results for the scenario where each agent has both thresholds.

IJCAI Conference 2023 Conference Paper

Maximin-Aware Allocations of Indivisible Chores with Symmetric and Asymmetric Agents

• Tianze Wei
• Bo Li
• Minming Li

The real-world deployment of fair allocation algorithms usually involves a heterogeneous population of users, which makes it challenging for the users to get complete knowledge of the allocation except for their own bundles. Recently, a new fairness notion, maximin-awareness (MMA) was proposed and it guarantees that every agent is not the worst-off one, no matter how the items that are not allocated to this agent are distributed. We adapt and generalize this notion to the case of indivisible chores and when the agents may have arbitrary weights. Due to the inherent difficulty of MMA, we also consider its up to one and up to any relaxations. A string of results on the existence and computation of MMA related fair allocations, and their connections to existing fairness concepts is given.

AAAI Conference 2023 Conference Paper

Multi-Stage Facility Location Problems with Transient Agents

• Xuezhen Wang
• Vincent Chau
• Hau Chan
• Ken C.K. Fong
• Minming Li

We study various models for the one-dimensional multi-stage facility location problems with transient agents, where a transient agent arrives in some stage and stays for a number of consecutive stages. In the problems, we need to serve each agent in one of their stages by determining the location of the facility at each stage. In the first model, we assume there is no cost for moving the facility across the stages. We focus on optimal algorithms to minimize both the social cost objective, defined as the total distance of all agents to the facility over all stages, and the maximum cost objective, defined as the max distance of any agent to the facility over all stages. For each objective, we give a slice-wise polynomial (XP) algorithm (i.e., solvable in m^f(k) for some fixed parameter k and computable function f, where m is the input size) and show that there is a polynomial-time algorithm when a natural first-come-first-serve (FCFS) order of agent serving is enforced. We then consider the mechanism design problem, where the agents' locations and arrival stages are private, and design a group strategy-proof mechanism that achieves good approximation ratios for both objectives and settings with and without FCFS ordering. In the second model, we consider the facility's moving cost between adjacent stages under the social cost objective, which accounts for the total moving distance of the facility. Correspondingly, we design XP (and polynomial time) algorithms and a group strategy-proof mechanism for settings with or without the FCFS ordering.

JAIR Journal 2023 Journal Article

Stackelberg Security Games with Contagious Attacks on a Network: Reallocation to the Rescue

• Rufan Bai
• Haoxing Lin
• Xinyu Yang
• Xiaowei Wu
• Minming Li
• Weijia Jia

In the classic network security games, the defender distributes defending resources to the nodes of the network, and the attacker attacks a node, with the objective of maximizing the damage caused. In this paper, we consider the network defending problem against contagious attacks, e.g., the attack at a node u spreads to the neighbors of u and can cause damage at multiple nodes. Existing works that study shared resources assume that the resource allocated to a node can be shared or duplicated between neighboring nodes. However, in the real world, sharing resource naturally leads to a decrease in defending power of the source node, especially when defending against contagious attacks. Therefore, we study the model in which resources allocated to a node can only be transferred to its neighboring nodes, which we refer to as a reallocation process. We show that the problem of computing optimal defending strategy is NP-hard even for some very special cases. For positive results, we give a mixed integer linear program formulation for the problem and a bi-criteria approximation algorithm. Our experimental results demonstrate that the allocation and reallocation strategies our algorithm computes perform well in terms of minimizing the damage due to contagious attacks.

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.

TCS Journal 2022 Journal Article

Efficient algorithms for ride-hitching in UAV travelling

• Songhua Li
• Minming Li
• Lingjie Duan
• Victor C.S. Lee

The unmanned aerial vehicle (UAV) has emerged as a promising solution to provide delivery and other mobile services to customers rapidly, yet it drains its stored energy quickly when travelling on the way and (even if solar-powered) it takes time for recharging on the way before reaching the destination. To address this issue, existing works focus more on UAV's offline path planning with designated system vehicles providing charging service. Nevertheless, in some emergency cases and rural areas where system vehicles are not available, public vehicles can provide more cost-saving and feasible service in UAV travelling. In this paper, we explore how a single UAV can save flying distance by exploiting public vehicles for the purpose of minimizing the overall travel time of the UAV, which is from the perspective of online algorithm. For the offline setting where the information of future vehicles is known far ahead of time, we present an O ( n 2 ) -time shortest-path-like optimal solution by delicately transforming the problem into a graph capturing both time and energy constraints. For the online setting where public vehicles appear in real-time and only inform the UAV of their trip information some certain time Δt beforehand, we first construct lower bounds on the competitive ratio for different Δt. Then, we propose two online algorithms, including a greedy algorithm MyopicHitching that greedily hitches truck rides and an improved algorithm Δt-Adaptive that further tolerates a waiting time in hitching a ride. Our theoretical analysis shows that Δt-Adaptive is asymptotically optimal in the sense that its ratio approaches the proposed lower bounds as Δt increases.

AAMAS Conference 2022 Conference Paper

Facility Location With Approval Preferences: Strategyproofness and Fairness

• Edith Elkind
• Minming Li
• Houyu Zhou

We develop a formal model of multiwinner facility location with approval preferences in one dimension: there is a set of facilities, a set of potential locations, and the goal is to build k facilities at these locations. Agents have approval preferences over ‘facility, location’ pairs, and may misreport their preferences if they can benefit from doing so. We consider both unit-demand agents and agents with additive demands, and the social objectives of coverage and utilitarian welfare. We ask whether these social objectives can be satisfied in a computationally efficient and strategyproof way. We also initiate the study of proportional representation in the context of facility location. We show that the axiom of justified representation, which is used to capture proportionality in multiwinner voting with approval preferences, is not well-suited for the facility location setting, and provide a relaxation of this axiom that can handle incompatibilities and may be of broader interest.

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.

IJCAI Conference 2022 Conference Paper

Mixed Strategies for Security Games with General Defending Requirements

• Rufan Bai
• Haoxing Lin
• Xinyu Yang
• Xiaowei Wu
• Minming Li
• Weijia Jia

The Stackelberg security game is played between a defender and an attacker, where the defender needs to allocate a limited amount of resources to multiple targets in order to minimize the loss due to adversarial attack by the attacker. While allowing targets to have different values, classic settings often assume uniform requirements to defend the targets. This enables existing results that study mixed strategies (randomized allocation algorithms) to adopt a compact representation of the mixed strategies. In this work, we initiate the study of mixed strategies for the security games in which the targets can have different defending requirements. In contrast to the case of uniform defending requirement, for which an optimal mixed strategy can be computed efficiently, we show that computing the optimal mixed strategy is NP-hard for the general defending requirements setting. However, we show that strong upper and lower bounds for the optimal mixed strategy defending result can be derived. We propose an efficient close-to-optimal Patching algorithm that computes mixed strategies that use only few pure strategies. We also study the setting when the game is played on a network and resource sharing is enabled between neighboring targets. Our experimental results demonstrate the effectiveness of our algorithm in several large real-world datasets.

ICML Conference 2022 Conference Paper

Selling Data To a Machine Learner: Pricing via Costly Signaling

• Junjie Chen
• Minming Li
• Haifeng Xu

We consider a new problem of selling data to a machine learner who looks to purchase data to train his machine learning model. A key challenge in this setup is that neither the seller nor the machine learner knows the true quality of data. When designing a revenue-maximizing mechanism, a data seller faces the tradeoff between the cost and precision of data quality estimation. To address this challenge, we study a natural class of mechanisms that price data via costly signaling. Motivated by the assumption of i. i. d. data points as in classic machine learning models, we first consider selling homogeneous data and derive an optimal selling mechanism. We then turn to the sale of heterogeneous data, motivated by the sale of multiple data sets, and show that 1) on the negative side, it is NP-hard to approximate the optimal mechanism within a constant ratio e/(e+1) + o(1); while 2) on the positive side, there is a 1/k-approximate algorithm, where k is the number of the machine learner’s private types.

AAMAS Conference 2022 Conference Paper

Strategy-Proof House Allocation with Existing Tenants over Social Networks

• Bo You
• Ludwig Dierks
• Taiki Todo
• Minming Li
• Makoto Yokoo

Mechanism design over social networks, whose goal is to incentivize agents to diffuse the information of a mechanism to their followers, as well as to report their true preferences, is one of the new trends in market design. In this paper, we reconsider the traditional house allocation problem with existing tenants from the perspective of mechanism design over social networks. Since our model is a generalization of the networked housing market investigated by Kawasaki et al. [9], no mechanism simultaneously satisfies strategy-proofness, individual rationality and Pareto efficiency for general social network structures. We therefore examine the cases where the social network has a tree structure. We first show that even for the restricted structure, a weaker welfare requirement called non-wastefulness is not achievable by any strategy-proof and individually rational mechanism. We then show that a non-trivial modification of You Request My House - I Get Your Turn mechanism (YRMH-IGYT) is individually rational, strategy-proof, and weakly non-wasteful. Furthermore, it chooses an allocation in the strict core for neighbors and satisfies weak group strategy-proofness.

IJCAI Conference 2022 Conference Paper

Strategyproof Mechanisms for Group-Fair Facility Location Problems

• Houyu Zhou
• Minming Li
• Hau Chan

We study the facility location problems where agents are located on a real line and divided into groups based on criteria such as ethnicity or age. Our aim is to design mechanisms to locate a facility to approximately minimize the costs of groups of agents to the facility fairly while eliciting the agents' locations truthfully. We first explore various well-motivated group fairness cost objectives for the problems and show that many natural objectives have an unbounded approximation ratio. We then consider minimizing the maximum total group cost and minimizing the average group cost objectives. For these objectives, we show that existing classical mechanisms (e. g. , median) and new group-based mechanisms provide bounded approximation ratios, where the group-based mechanisms can achieve better ratios. We also provide lower bounds for both objectives. To measure fairness between groups and within each group, we study a new notion of intergroup and intragroup fairness (IIF). We consider two IIF objectives and provide mechanisms with tight approximation ratios.

AAAI Conference 2021 Conference Paper

Budget Feasible Mechanisms Over Graphs

• Xiang Liu
• Weiwei Wu
• Minming Li
• Wanyuan Wang

This paper studies the budget-feasible mechanism design over graphs, where a buyer wishes to procure items from sellers, and all participants (the buyer and sellers) can only directly interact with their neighbors during the auction campaign. The problem for the buyer is to use the limited budget to incentivize sellers to propagate auction information to their neighbors, thereby more sellers will be informed of the auction and more item value will be procured. An impossibility result shows that the large-market assumption is necessary. We propose efficient budget-feasible diffusion mechanisms for large markets that simultaneously guarantee individual rationality, budget-feasibility, strong budget-balance, incentivecompatibility to report private costs and diffuse auction information. Moreover, the proposed mechanisms achieve logarithmic approximation that the total procured value is within a logarithmic factor of the optimal solution. Compared to most related budget-feasible mechanisms, which do not take the individual interactions among sellers into account, our mechanisms can incentivize sellers to further propagate auction information to other potential sellers. Meanwhile, existing related diffusion mechanisms only focus on seller-centric auctions and fail to satisfy the budget-feasibility of the buyer.

IJCAI Conference 2021 Conference Paper

Budget-feasible Mechanisms for Representing Groups of Agents Proportionally

• Xiang Liu
• Hau Chan
• Minming Li
• Weiwei Wu

In this paper, we consider the problem of designing budget-feasible mechanisms for selecting agents with private costs from various groups to ensure proportional representation, where the minimum proportion of the selected agents from each group is maximized. Depending on agents' membership in the groups, we consider two main models: single group setting where each agent belongs to only one group, and multiple group setting where each agent may belong to multiple groups. We propose novel budget-feasible proportion-representative mechanisms for these models, which can select representative agents from different groups. The proposed mechanisms guarantee theoretical properties of individual rationality, budget-feasibility, truthfulness, and approximation performance on proportional representation.

AAAI Conference 2021 Conference Paper

Defending against Contagious Attacks on a Network with Resource Reallocation

• Rufan Bai
• Haoxing Lin
• Xinyu Yang
• Xiaowei Wu
• Minming Li
• Weijia Jia

In classic network security games, the defender distributes defending resources to the nodes of the network, and the attacker attacks a node, with the objective to maximize the damage caused. Existing models assume that the attack at node u causes damage only at u. However, in many real-world security scenarios, the attack at a node u spreads to the neighbors of u and can cause damage at multiple nodes, e. g. , for the outbreak of a virus. In this paper, we consider the network defending problem against contagious attacks. Existing works that study shared resources assume that the resource allocated to a node can be shared or duplicated between neighboring nodes. However, in real world, sharing resource naturally leads to a decrease in defending power of the source node, especially when defending against contagious attacks. To this end, we study the model in which resources allocated to a node can only be transferred to its neighboring nodes, which we refer to as a reallocation process. We show that this more general model is difficult in two aspects: (1) even for a fixed allocation of resources, we show that computing the optimal reallocation is NP-hard; (2) for the case when reallocation is not allowed, we show that computing the optimal allocation (against contagious attack) is also NP-hard. For positive results, we give a mixed integer linear program formulation for the problem and a bi-criteria approximation algorithm. Our experimental results demonstrate that the allocation and reallocation strategies our algorithm computes perform well in terms of minimizing the damage due to contagious attacks. *Funded by the Science and Technology Development Fund, Macau SAR (File no. SKLIOTSC-2018-2020), the Start-up Research Grant of University of Macau (File no. SRG2020-00020- IOTSC). This work was supported in part by the Science and Technology Development Fund, Macau SAR under File no. 0060/2019/A1, and in part by Research Grant of University of Macau under Grant MYRG2018-00237-FST. † City University of Hong Kong Shenzhen Research Institute, Shenzhen, P. R. China. The work described in this paper was partially sponsored by Project 11771365 supported by NSFC. ‡ BNU-UIC Institute of Artificial Intelligence and Future Networks, Beijing Normal University (Zhuhai), Guangdong, China. The work was partially supported by Chinese National Research Fund (NSFC) Key Project No. 61532013; NSFC grant No. 61872239; and Guangdong Provincial Key Lab of AI and Multimodal Data Processing at BNU-HKBU UIC. Copyright © 2021, Association for the Advancement of Artificial Intelligence (www. aaai. org). All rights reserved.

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.

NeurIPS Conference 2021 Conference Paper

Fair Scheduling for Time-dependent Resources

• Bo Li
• Minming Li
• Ruilong Zhang

We study a fair resource scheduling problem, where a set of interval jobs are to be allocated to heterogeneous machines controlled by intellectual agents. Each job is associated with release time, deadline, and processing time such that it can be processed if its complete processing period is between its release time and deadline. The machines gain possibly different utilities by processing different jobs, and all jobs assigned to the same machine should be processed without overlap. We consider two widely studied solution concepts, namely, maximin share fairness and envy-freeness. For both criteria, we discuss the extent to which fair allocations exist and present constant approximation algorithms for various settings.

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.

JAIR Journal 2021 Journal Article

Two-facility Location Games with Minimum Distance Requirement

• Xinping Xu
• Bo Li
• Minming Li
• Lingjie Duan

We study the mechanism design problem of a social planner for locating two facilities on a line interval [0, 1], where a set of n strategic agents report their locations and a mechanism determines the locations of the two facilities. We consider the requirement of a minimum distance 0 ≤ d ≤ 1 between the two facilities. Given the two facilities are heterogeneous, we model the cost/utility of an agent as the sum of his distances to both facilities. In the heterogeneous two-facility location game to minimize the social cost, we show that the optimal solution can be computed in polynomial time and prove that carefully choosing one optimal solution as output is strategyproof. We also design a strategyproof mechanism minimizing the maximum cost. Given the two facilities are homogeneous, we model the cost/utility of an agent as his distance to the closer facility. In the homogeneous two-facility location game for minimizing the social cost, we show that any deterministic strategyproof mechanism has unbounded approximation ratio. Moreover, in the obnoxious heterogeneous two-facility location game for maximizing the social utility, we propose new deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound (7 − d)/6 for any deterministic strategyproof mechanism. We also design a strategyproof mechanism maximizing the minimum utility. In the obnoxious homogeneous two-facility location game for maximizing the social utility, we propose deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound 4/3. Besides, in the two-facility location game with triple-preference, where each facility may be favorable, obnoxious, indifferent for any agent, we further motivate agents to report both their locations and preferences towards the two facilities truthfully, and design a deterministic group strategyproof mechanism with an approximation ratio 4.

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.

AAAI Conference 2020 Conference Paper

Defending with Shared Resources on a Network

• Minming Li
• Long Tran-Thanh
• Xiaowei Wu

In this paper we consider a defending problem on a network. In the model, the defender holds a total defending resource of R, which can be distributed to the nodes of the network. The defending resource allocated to a node can be shared by its neighbors. There is a weight associated with every edge that represents the efficiency defending resources are shared between neighboring nodes. We consider the setting when each attack can affect not only the target node, but its neighbors as well. Assuming that nodes in the network have different treasures to defend and different defending requirements, the defender aims at allocating the defending resource to the nodes to minimize the loss due to attack. We give polynomial time exact algorithms for two important special cases of the network defending problem. For the case when an attack can only affect the target node, we present an LP-based exact algorithm. For the case when defending resources cannot be shared, we present a max-flow-based exact algorithm. We show that the general problem is NP-hard, and we give a 2approximation algorithm based on LP-rounding. Moreover, by giving a matching lower bound of 2 on the integrality gap on the LP relaxation, we show that our rounding is tight.

TCS Journal 2020 Journal Article

Facility location games with optional preference

• Zhihuai Chen
• Ken C.K. Fong
• Minming Li
• Kai Wang
• Hongning Yuan
• Yong Zhang

In this paper, we study the optional preference model of the facility location game problem with two heterogeneous facilities on a line. The preference of each agent is one of the two facilities or both facilities, and the cost of each agent is a function of the distances to the facilities that the agent prefers. We consider two cost functions: Minimum Distance and Maximum Distance functions. Aiming at minimizing the maximum cost or the social cost of agents, we propose different strategyproof mechanisms without monetary transfers and derive both lower and upper bounds of the approximation ratios with respect to strategyproof mechanisms. In the variant of Minimum Distance, we propose a 2-approximation deterministic strategyproof mechanism for the maximum cost objective, and prove a lower bound of 4/3, while for the social cost objective we propose a ( n / 2 +1)-approximation deterministic strategyproof mechanism and prove a lower bound of 2, also a lower bound of 3/2 for randomized mechanisms. In the variant of Maximum Distance, we propose an optimal deterministic strategyproof mechanism for the maximum cost objective and a 2-approximation deterministic strategyproof mechanism for the social cost objective.

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 finds 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 finding a committee to optimize the social value. We measure the quality of a mechanism by its distortion, defined 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.

TCS Journal 2020 Journal Article

Flow shop for dual CPUs in dynamic voltage scaling

• Vincent Chau
• Xin Chen
• Ken C.K. Fong
• Minming Li
• Kai Wang

We study the following flow shop scheduling problem on two processors. We are given n jobs with a common deadline D, where each job j has workload p i, j on processor i and a set of processors which can vary their speed dynamically. Job j can be executed on the second processor if the execution of job j is completed on the first processor. Our objective is to find a feasible schedule such that all jobs are completed by the common deadline D with minimized energy consumption. For this model, we present a linear program for the discrete speed case, where the processor can only run at specific speeds in S = { s 1, s 2, ⋯, s q } and the job execution order is fixed. We also provide a m α − 1 -approximation algorithm for the arbitrary order case and for continuous speed model where m is the number of processors and α is a parameter of the processor. We then introduce a new variant of flow shop scheduling problem called sense-and-aggregate model motivated by data aggregation in wireless sensor networks where the base station needs to receive data from sensors and then compute a single aggregate result. In this model, the first processor will receive unit size data from sensors and the second processor is responsible for calculating the aggregate result. The second processor can decide when to aggregate and the workload that needs to be done to aggregate x data will be f ( x ) and another unit size data will be generated as the result of the partial aggregation which will then be used in the next round aggregation. Our objective is to find a schedule such that all data are received and aggregated by the deadline with minimum energy consumption. We present an O ( n 5 ) dynamic programming algorithm when f ( x ) = x and a greedy algorithm when f ( x ) = x − 1. Finally, we investigate the performance of the flowshop problem when the order of jobs is fixed by comparing it to the approximation algorithm with an arbitrary order. We show experimentally that the approximation ratio is close to 1 when there are few machines and when there are more jobs.

TCS Journal 2020 Journal Article

Minimizing the cost of batch calibrations

• Vincent Chau
• Minming Li
• Elaine Yinling Wang
• Ruilong Zhang
• Yingchao Zhao

We study the scheduling problem with calibrations. We are given a set of n jobs that need to be scheduled on a set of m machines. However, a machine can schedule jobs only if a calibration has been performed beforehand and the machine is considered as valid during a fixed time period of T, after which it must be recalibrated before running more jobs. In this paper, we investigate the batch calibrations; calibrations occur in batch and at the same moment. It is then not possible to perform any calibrations during a period of T. We consider different cost function depending on the number of machines we calibrate at a given time, i. e. , the cost function is denoted as f ( x ) where x is the number of calibrations in the batch. Moreover, jobs have release time, deadline, and unit processing time. The objective is to schedule all jobs with the minimum cost of calibrations. We give a dynamic program to solve the case with an arbitrary cost function. Then, we propose several faster approximation algorithms for different cost functions: an optimal algorithm when f ( x ) = b, a 3-approximation algorithm when f ( x ) = x and a ( m + b ) / ( b + 1 ) -approximation algorithm when f ( x ) = x + b. The running time of these algorithms are O ( n 2 ).

JAAMAS Journal 2020 Journal Article

Strategic facility location problems with linear single-dipped and single-peaked preferences

• Itai Feigenbaum
• Minming Li
• Shaokun Zou

Abstract We consider the design of mechanisms for locating facilities on an interval. There are multiple agents on the interval, each receiving a utility determined by their distances to the facilities. The objectives considered are maximization of social welfare (sum of utilities) and egalitarian welfare (minimum utility). Agents can misreport their locations, and so we require the mechanisms to be strategyproof—no agent should be able to benefit from misreporting; subject to strategyproofness, we attempt to design mechanisms that are approximately optimal (have small worst-case approximation ratios). The novelty of our work is the consideration of models in which single-dipped and single-peaked preferences exist simultaneously. We consider two models. In the first model, there is a single facility, and agents may disagree about its nature: some agents prefer to be near the facility, while others prefer to be far from it. In the second model, there are two facilities: a desirable facility that all agents want near, and an undesirable facility that all agents want far. We design a variety of approximately optimal strategyproof mechanisms for both models, and prove several lower bounds as well. For the social welfare objective, we provide best-possible deterministic strategyproof mechanisms in the first model and the second model. We then provide improved randomized strategyproof mechanisms for each model, as well as a non-tight lower bound on the worst-case approximation ratio attainable by such mechanisms for the first model. For the egalitarian welfare objective, we provide a lower bound on randomized strategyproof mechanisms for the first model, as well as an optimal (non-approximate) strategyproof mechanism for the second model. All of our mechanisms are also group strategyproof: no coalition of agents can unanimously benefit from misreporting.

IJCAI Conference 2020 Conference Paper

Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio

• Minming Li
• Pinyan Lu
• Yuhao Yao
• Jialin Zhang

In this paper, we study the two-facility location game with optional preference where the acceptable set of facilities for each agent could be different and an agent's cost is his distance to the closest facility within his acceptable set. The objective is to minimize the total cost of all agents while achieving strategyproofness. For general metrics, we design a deterministic strategyproof mechanism for the problem with approximation ratio of 1+2alpha, where alpha is the approximation ratio of the optimization version. In particular, for the setting on a line, we improve the earlier best ratio of n/2+1 to a ratio of 2. 75.

AAMAS Conference 2019 Conference Paper

Facility Location Games with Externalities

• Minming Li
• Lili Mei
• Yi Xu
• Guochuan Zhang
• Yingchao Zhao

Facility location games study the scenario where a facility is to be placed based on the reported information from agents. In the society where there are relationships between agents, it is quite natural that one agent’s gain will affect other agents’ gain (either increase for a collaborator or decrease for a competitor). By using externality to represent this type of agent interaction, for the first time we introduce it into the facility location games in this paper. Namely, we study the extension where agents’ utilities will be affected by other agents. We derive necessary and sufficient conditions for well known existing mechanisms and also prove strong lower bounds.

AAMAS Conference 2019 Conference Paper

Heterogeneous Two-facility Location Games with Minimum Distance Requirement

• Lingjie Duan
• Bo Li
• Minming Li
• Xinping Xu

We study the mechanism design problem of a social planner for locating two heterogeneous facilities on a line interval [0, 1], where a set of 𝑛 strategic agents report their locations and a mechanism determines the locations of the two facilities. Unlike prior work on two-facility location games, we consider the requirement of the minimum distance 𝑑 between the two facilities. As the two facilities are heterogeneous and have additive effects on agents, we model that the cost of an agent is the sum of his distances to both facilities and the social cost is the total cost of all agents. In the twofacility location game to minimize the social cost, we show that the optimal solution can be computed in polynomial time and prove that carefully choosing one optimal solution as output is strategyproof. In the obnoxious two-facility location game for maximizing the social utility, a mechanism outputting the optimal solution is not strategyproof and we propose new deterministic group strategyproof mechanisms with provable approximation ratios. Moreover, we establish a lower bound 7−𝑑 6 for the approximation ratio achievable by deterministic strategyproof mechanisms. Finally, we study the two-facility location game with triple-preference, where each of the two facilities may be favorable, obnoxious, indifferent for any agent. We further allow each agent to misreport his location and preference towards the two facilities and design a deterministic group strategyproof mechanism with approximation ratio 4. * The authorship follows alphabetical order. † The work described in this paper was supported by the Singapore Ministry of Education Academic Research Fund Tier 2 under Grant MOE2016-T2-1-173. ‡ Part of this work was done when B. Li was visiting City University of Hong Kong. The work described in this paper was supported by NSF CAREER Award No. 1553385. S M. Li is also from City University of Hong Kong Shenzhen Research Institute, Shenzhen, P. R. China. The work described in this paper was supported by a grant from Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CityU 11200518) and was partially sponsored by Project 11771365 supported by NSFC. ¶ X. Xu is the corresponding author. Proc. of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), N. Agmon, M. E. Taylor, E. Elkind, M. Veloso (eds.), May 13–17, 2019, Montreal, Canada. © 2019 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). All rights reserved.

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.

AAMAS Conference 2019 Conference Paper

Well-behaved Online Load Balancing Against Strategic Jobs

• Bo Li
• Minming Li
• Xiaowei Wu

In the online load balancing problem on related machines, we have a set of jobs (with different sizes) arriving online, and we need to assign each job to a machine immediately upon its arrival, so as to minimize the makespan, i. e. , the maximum completion time. In classic mechanism design problems, we assume that the jobs are controlled by selfish agents, with the sizes being their private information. Each job (agent) aims at minimizing its own cost, which is its completion time plus the payment charged by the mechanism. Truthful mechanisms guaranteeing that every job minimizes its cost by reporting its true size have been well-studied [Aspnes et al. JACM 1997, Feldman et al. EC 2017]. In this paper, we study truthful online load balancing mechanisms that are well-behaved [Epstein et al. , MOR 2016]. Wellbehavior is important as it guarantees fairness between machines, and implies truthfulness in some cases when machines are controlled by selfish agents. Unfortunately, existing truthful online load balancing mechanisms are not well-behaved. We first show that to guarantee producing a well-behaved schedule, any online algorithm (even non-truthful) has a competitive ratio at least Ω( √ m), wherem is the number of machines. Then we propose a mechanism that guarantees truthfulness of the online jobs, and produces a schedule that is almost well-behaved. We show that our algorithm has a competitive ratio of O(logm). Moreover, for the case when the sizes of online jobs are bounded, the competitive ratio of our algorithm improves to O(1). Interestingly, we show several cases for which our mechanism is actually truthful against selfish machines.

IJCAI Conference 2018 Conference Paper

Budget-feasible Procurement Mechanisms in Two-sided Markets

• Weiwei Wu
• Xiang Liu
• Minming Li

This paper considers the mechanism design problem in two-sided markets where multiple strategic buyers come with budgets to procure as much value of items as possible from the strategic sellers. Each seller holds an item with public value and is allowed to bid its private cost. Buyers could claim their budgets, not necessarily the true ones. The goal is to seek budget-feasible mechanisms that ensure sellers are rewarded enough payment and buyers' budgets are not exceeded. Our main contribution is a random mechanism that guarantees various desired theoretical guarantees like the budget feasibility, the truthfulness on the sellers' side and the buyers' side simultaneously, and constant approximation to the optimal total procured value of buyers.

AAAI Conference 2018 Conference Paper

Facility Location Games With Fractional Preferences

• Chi Kit Ken Fong
• Minming Li
• Pinyan Lu
• Taiki Todo
• Makoto Yokoo

In this paper, we propose a fractional preference model for the facility location game with two facilities that serve the similar purpose on a line where each agent has his location information as well as fractional preference to indicate how well they prefer the facilities. The preference for each facility is in the range of [0, L] such that the sum of the preference for all facilities is equal to 1. The utility is measured by subtracting the sum of the cost of both facilities from the total length L where the cost of facilities is defined as the multiplication of the fractional preference and the distance between the agent and the facilities. We first show that the lower bound for the objective of minimizing total cost is at least Ω(n 1 3 ). Hence, we use the utility function to analyze the agents’ satification. Our objective is to place two facilities on [0, L] to maximize the social utility or the minimum utility. For each objective function, we propose deterministic strategy-proof mechanisms. For the objective of maximizing the social utility, we present an optimal deterministic strategy-proof mechanism in the case where agents can only misreport their locations. In the case where agents can only misreport their preferences, we present a 2approximation deterministic strategy-proof mechanism. Finally, we present a 4-approximation deterministic strategyproof mechanism and a randomized strategy-proof mechanism with an approximation ratio of 2 where agents can misreport both the preference and location information. Moreover, we also give a lower-bound of 1. 06. For the objective of maximizing the minimum utility, we give a lower-bound of 1. 5 and present a 2-approximation deterministic strategyproof mechanism where agents can misreport both the preference and location.

JAAMAS Journal 2017 Journal Article

Facility location with double-peaked preferences

• Aris Filos-Ratsikas
• Minming Li
• Qiang Zhang

Abstract We study the problem of locating a single facility on a real line based on the reports of self-interested agents, when agents have double-peaked preferences, with the peaks being on opposite sides of their locations. We observe that double-peaked preferences capture real-life scenarios and thus complement the well-studied notion of single-peaked preferences. As a motivating example, assume that the government plans to build a primary school along a street; an agent with single-peaked preferences would prefer having the school built exactly next to her house. However, while that would make it very easy for her children to go to school, it would also introduce several problems, such as noise or parking congestion in the morning. A 5-min walking distance would be sufficiently far for such problems to no longer be much of a factor and at the same time sufficiently close for the school to be easily accessible by the children on foot. There are two positions (symmetrically) in each direction and those would be the agent’s two peaks of her double-peaked preference. Motivated by natural scenarios like the one described above, we mainly focus on the case where peaks are equidistant from the agents’ locations and discuss how our results extend to more general settings. We show that most of the results for single-peaked preferences do not directly apply to this setting, which makes the problem more challenging. As our main contribution, we present a simple truthful-in-expectation mechanism that achieves an approximation ratio of \(1+b/c\) for both the social and the maximum cost, where b is the distance of the agent from the peak and c is the minimum cost of an agent. For the latter case, we provide a 3 / 2 lower bound on the approximation ratio of any truthful-in-expectation mechanism. We also study deterministic mechanisms under some natural conditions, proving lower bounds and approximation guarantees. We prove that among a large class of reasonable strategyproof mechanisms, there is no deterministic mechanism that outperforms our truthful-in-expectation mechanism. In order to obtain this result, we first characterize mechanisms for two agents that satisfy two simple properties; we use the same characterization to prove that no mechanism in this class can be group-strategyproof.

AAMAS Conference 2017 Conference Paper

Mechanism Design for Ontology Alignment

• Piotr Krysta
• Minming Li
• TERRY R. PAYNE
• Nan Zhi

The aim of the ontology alignment problem is to find meaningful correspondences between two ontologies represented as collections of entities. This problem can be modelled as a novel mechanism design problem on an edge-weighted bipartite graph, where each side of the graph holds each agent’s private entities, and the objective is to maximise the agents’ social welfare. Having studied implementation in dominant strategies with and without payments, we report on findings that for truthful mechanisms, these problems need to be solved optimally. We also study greedy allocation rules with a first-price payment rule, and implementation in pure, mixed & Bayesian Nash equilibria, and have found tight bounds on the price of anarchy and stability.

TCS Journal 2016 Journal Article

Average-case complexity of the min-sum matrix product problem

• Ken C.K. Fong
• Minming Li
• Hongyu Liang
• Linji Yang
• Hao Yuan

We study the average-case complexity of min-sum product of matrices, which is a fundamental operation that has many applications in computer science. We focus on optimizing the number of “algebraic” operations (i. e. , operations involving real numbers) used in the computation, since such operations are usually expensive in various environments. We present an algorithm that can compute the min-sum product of two n × n real matrices using only O ( n 2 ) algebraic operations, given that the matrix elements are drawn independently and identically from some fixed probability distribution satisfying several constraints. This improves the previously best known upper-bound of O ( n 2 log ⁡ n ). The class of probability distributions under which our algorithm works include many important and commonly used distributions, such as uniform distributions, exponential distributions, folded normal distributions, etc. In order to evaluate the performance of the proposed algorithm, we performed experiments to compare the running time of the proposed algorithm with algorithms in [1]. The experimental results demonstrate that our algorithm achieves significant performance improvement over the previous algorithms.

ECAI Conference 2016 Conference Paper

Facility Location Games with Optional Preference

• Hongning Yuan
• Kai Wang 0018
• Ken C. K. Fong
• Yong Zhang 0001
• Minming Li

In this paper, we propose the optional preference model for the facility location game with two heterogeneous facilities on a line. Agents in this new model are allowed to have optional preference, which gives more flexibility for agents to report. Aiming at minimizing maximum cost or sum cost of agents, we propose different deterministic strategy-proof mechanisms without monetary transfers. Depending on which facility the agent with optional preference cares for, we consider two variants of the optional preference model: Min (caring for the closer one) and Max (caring for the further one). For the Min variant, we propose a 2-approximation mechanism for the maximum cost objective, as well as a lower bound of 4/3, and a &lpar; n/2+1&rpar; -approximation mechanism for the sum cost objective, as well as a lower bound of 2. For Max variant, we propose an optimal mechanism for the maximum cost objective and a 2-approximation mechanism for the sum cost objective.

AAMAS Conference 2016 Conference Paper

Network Pollution Games

• Eleftherios Anastasiadis
• Xiaotie Deng
• Piotr Krysta
• Minming Li
• Han Qiao
• Jinshan Zhang

We introduce a new network model of the pollution control problem and present two applications of this model. On a high level, our model comprises a graph whose nodes represent the agents, that could be thought of as sources of pollution, and edges between agents represent the effect of spread of pollution. The government as the regulator is responsible to maximize the social welfare while setting bounds on the levels of emitted pollution both locally and globally. Our model is inspired by the existing literature in environmental economics that applies game theoretical methodology to control pollution. We study the social welfare maximization problem in our model. Our main results include hardness results for the problem, and in complement, a constant approximation algorithm on planar graphs. Our approximation algorithm leads to a truthful in expectation mechanism, and it is obtained by a novel decomposition technique of planar graphs to deal with constraints on vertices. We note that no known planar decomposition techniques can be used here and our technique can be of independent interest.

AAMAS Conference 2016 Conference Paper

Strategy-Proof Mechanism Design for Facility Location Games: Revisited (Extended Abstract)

• Lili Mei
• Minming Li
• Deshi Ye
• Guochuan Zhang

In facility location games, one aims at designing a mechanism to decide the facility location based on the addresses reported by all agents. In the standard facility location game, each agent wants to minimize the distance from the facility, while in the obnoxious facility game, each agent prefers to be as far away from the facility as possible. In this paper we revisit the two games on a line network by finely defining more reasonable agent cost (utility) functions in terms of their satisfaction degree with respect to the facility location. Namely, a happiness factor within [0, 1] is introduced to measure the difference between the best facility location for an agent and the one given by the mechanism. Agents aim at a largest possible happiness factor while the social satisfaction is to maximize the total factors. For the standard facility location game, we observe that the median mechanism [4] is of 3/2-approximation. We then devise a 5/4-approximation group strategy-proof mechanism. For the obnoxious facility game, we show the majority mechanism [1] is best possible with approximation ratio of two.

AAAI Conference 2015 Conference Paper

Facility Location with Double-Peaked Preferences

• Aris Filos-Ratsikas
• Minming Li
• Jie Zhang
• Qiang Zhang

We study the problem of locating a single facility on a real line based on the reports of self-interested agents, when agents have double-peaked preferences, with the peaks being on opposite sides of their locations. We observe that double-peaked preferences capture real-life scenarios and thus complement the well-studied notion of single-peaked preferences. We mainly focus on the case where peaks are equidistant from the agents’ locations and discuss how our results extend to more general settings. We show that most of the results for singlepeaked preferences do not directly apply to this setting; this makes the problem essentially more challenging. As our main contribution, we present a simple truthfulin-expectation mechanism that achieves an approximation ratio of 1+b/c for both the social and the maximum cost, where b is the distance of the agent from the peak and c is the minimum cost of an agent. For the latter case, we provide a 3/2 lower bound on the approximation ratio of any truthful-in-expectation mechanism. We also study deterministic mechanisms under some natural conditions, proving lower bounds and approximation guarantees. We prove that among a large class of reasonable mechanisms, there is no deterministic mechanism that outpeforms our truthful-in-expectation mechanism.

TCS Journal 2015 Journal Article

Optimal trees for minimizing average individual updating cost

• Sicen Guo
• Minming Li
• Yingchao Zhao

Key tree is a popular model to maintain the security of group information sharing by using a tree structure to maintain the keys held by different users. Previously, researchers proved that to minimize the worst case updating cost in case of single user deletion, one needs to use a special 2–3 tree. In this paper, we study the average case for user update. We prove that in the optimal tree, the branching degree of every node can be bounded by 3 and furthermore the structure of the optimal tree can be pretty balanced. We also show the way to construct the optimal tree when there are loyal users in the group. Finally we discuss about the weighted case where different users have different probabilities to be the first one leaving the group. We design a polynomial time algorithm to construct the optimal tree when the number of different probabilities is a constant.

IJCAI Conference 2015 Conference Paper

Truthful Cake Cutting Mechanisms with Externalities: Do Not Make Them Care for Others Too Much!

• Minming Li
• Jialin Zhang
• Qiang Zhang

We study truthful mechanisms in the context of cake cutting when agents not only value their own pieces of cake but also care for the pieces assigned to other agents. In particular, agents derive benefits or costs from the pieces of cake assigned to other agents. This phenomenon is often referred to as positive or negative externalities. We propose and study the following model: given an allocation, externalities of agents are modeled as percentages of the reported values that other agents have for their pieces. We show that even in this restricted class of externalities, under some natural assumptions, no truthful cake cutting mechanisms exist when externalities are either positive or negative. However, when the percentages agents get from each other are small, we show that there exists a truthful cake cutting mechanism with other desired properties.

TCS Journal 2013 Journal Article

Minimizing the total weighted completion time of fully parallel jobs with integer parallel units

• Qiang Zhang
• Weiwei Wu
• Minming Li

We consider the total weighted completion time minimization in the following scheduling problem. There are m identical resources available at each time unit, and n jobs. Each job requires a number s i of resources and one resource can only be assigned to one job at each time unit. Each job is also called fully parallel such that the job is satisfied once it receives enough resources no matter how the resources distribute. The objective is to find a schedule that minimizes ∑ w i C i, where w i is the weight of job J i and C i is the time when job J i receives s i resources. We show that the total weighted completion time minimization is NP-hard when m is an input of the problem. We then give a simple greedy algorithm with an approximation ratio 2. Finally, we present a polynomial time algorithm with complexity O ( n d + 1 ) to solve this problem when the number of different resource requirements that are not multiples of m is at most d.

TCS Journal 2012 Journal Article

Single and multiple device DSA problems, complexities and online algorithms

• Weiwei Wu
• Minming Li
• Wanyong Tian
• Jason Chun Xue
• Enhong Chen

We study the single-device Dynamic Storage Allocation (DSA) problem and the multi-device Balancing DSA problem in this paper. The goal is to dynamically allocate the job into memory to minimize the usage of space without concurrency. The SRF problem is just a variant of the DSA problem. Our results are as follows. • The NP-completeness for the 2-SRF problem, 3-DSA problem, and DSA problem for jobs with agreeable deadlines. • An improved 3-competitive algorithm for jobs with agreeable deadlines on single-device DSA problems. A 4-competitive algorithm for jobs with agreeable deadlines on multi-device Balancing DSA problems. • Lower bounds for jobs with agreeable deadlines: any non-clairvoyant algorithm cannot be ( 2 − ϵ ) -competitive and any clairvoyant algorithm cannot be ( 1. 54 − ϵ ) -competitive. • The first O ( log L ) -competitive algorithm for general jobs on multi-device Balancing DSA problems without any assumption.

TCS Journal 2011 Journal Article

Approximation algorithms for variable voltage processors: Min energy, max throughput and online heuristics

• Minming Li

Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. It was shown that if the processor can run at arbitrary speeds and uses power s α when running at speed s, the online heuristic AVR has a competitive ratio ( 2 α ) α / 2. In this paper we first study the online heuristics for the discrete model where the processor can only run at d given speeds. We propose a method to transform online heuristic AVR to an online heuristic for the discrete model and prove a competitive ratio 2 α − 1 ( α − 1 ) α − 1 ( δ α − 1 ) α ( δ − 1 ) ( δ α − δ ) α − 1 + 1, where δ is the maximum ratio between adjacent non-zero speed levels. We also prove that the analysis holds for a class of heuristics that satisfy certain natural properties. We further study the throughput maximization problem when there is an upper bound for the maximum speed. We propose a greedy algorithm with running time O ( n 2 log n ) and prove that the output schedule is a 3-approximation of the throughput and a ( α − 1 ) α − 1 ( 3 α − 1 ) α 2 α α ( 3 α − 1 − 1 ) α − 1 -approximation of the energy consumption.

TCS Journal 2011 Journal Article

Min-energy scheduling for aligned jobs in accelerate model

• Weiwei Wu
• Minming Li
• Enhong Chen

A dynamic voltage scaling technique provides the capability for processors to adjust the speed and control the energy consumption. We study the pessimistic accelerate model where the acceleration rate of the processor speed is at most K and jobs cannot be executed during the speed transition period. The objective is to find a min-energy (optimal) schedule that finishes every job within its deadline. The job set we study in this paper is aligned jobs where earlier released jobs have earlier deadlines. We start by investigating a special case where all jobs have a common arrival time and design an O ( n 2 ) algorithm to compute the optimal schedule based on some nice properties of the optimal schedule. Then, we study the general aligned jobs and obtain an O ( n 2 ) algorithm to compute the optimal schedule by using the algorithm for the common arrival time case as a building block. Because our algorithm relies on the computation of the optimal schedule in the ideal model ( K = ∞ ), in order to achieve O ( n 2 ) complexity, we improve the complexity of computing the optimal schedule in the ideal model for aligned jobs from the currently best known O ( n 2 log n ) to O ( n 2 ).

TCS Journal 2010 Journal Article

Energy optimal schedules for jobs with multiple active intervals

• Wanyong Tian
• Minming Li
• Enhong Chen

In this paper, we study the scheduling problem of jobs with multiple active intervals. Each job in the problem instance has n ( n ⩾ 1 ) disjoint active time intervals where it can be executed and a workload characterized by the required number of CPU cycles. Previously, people studied multiple interval job scheduling problem where each job must be assigned enough CPU cycles in one of its active intervals. We study a different practical version where the partial work done by the end of an interval remains valid and each job is considered finished if total CPU cycles assigned to it in all its active intervals reach the requirement. The goal is to find a feasible schedule that minimizes energy consumption. By adapting the algorithm for single interval jobs proposed in Yao, Demers and Shenker (1995) [1], one can still obtain an optimal schedule. However, the two phases in that algorithm (critical interval finding and scheduling the critical interval) can no longer be carried out directly. We present polynomial time algorithms to solve the two phases for jobs with multiple active intervals and therefore can still compute the optimal schedule in polynomial time.

TCS Journal 2009 Journal Article

Approximately optimal trees for group key management with batch updates

• Minming Li
• Ze Feng
• Nan Zang
• Ronald L. Graham
• Frances F. Yao

We investigate the group key management problem for broadcasting applications. Previous work showed that, in handling key updates, batch rekeying can be more cost effective than individual rekeying. One model for batch rekeying is to assume that every user has probability p of being replaced by a new user during a batch period with the total number of users unchanged. Under this model, it was recently shown that an optimal key tree can be constructed in linear time when p is a constant and in O ( n 4 ) time when p → 0. In this paper, we investigate more efficient algorithms for the case p → 0, i. e. , when membership changes are sparse. We design an O ( n ) heuristic algorithm for the sparse case and show that it produces a nearly 2-approximation to the optimal key tree. Simulation results show that its performance is even better in practice. We also design a refined heuristic algorithm and show that it achieves an approximation ratio of 1 + ϵ for any fixed ϵ > 0 and n, as p → 0. Finally, we give another approximation algorithm for any p ∈ ( 0, 0. 693 ) which is shown to be quite good by our simulations.

TCS Journal 2009 Journal Article

Optimal tree structures for group key tree management considering insertion and deletion cost

• Weiwei Wu
• Minming Li
• Enhong Chen

We study the optimal structure for the group broadcast problem where the key tree model is extensively used. The objective is usually to find an optimal key tree to minimize the cost based on certain assumptions. Under the assumption that n members arrive in the initial setup period and only member deletions are allowed after that period, previous works show that when only considering the deletion cost, the optimal tree can be computed in O ( n 2 ) time. In this paper, we first prove a semi-balance property for the optimal tree and use it to reduce the running time from O ( n 2 ) to O ( log log n ) multiplications of O ( log n ) -bit integers. Then we study the optimal tree structure when insertion cost is also considered. We show that the optimal tree is such a tree where any internal node has degree at most 7 and children of nodes with degree not equal to 2 or 3 are all leaves. Based on this result we give a dynamic programming algorithm with O ( n 2 ) time to compute the optimal tree.

TCS Journal 2008 Journal Article

Lower bounds and new constructions on secure group communication schemes

• Scott C.-H. Huang
• Frances Yao
• Minming Li
• Weili Wu

This paper presents both the theoretical and practical aspects of secure group communication schemes. We pointed out that multiple revocation is a fundamentally time-consuming task in secure group communication, by establishing lower bounds for broadcast encryption and group key distribution schemes. We showed that they are O ( n ) for BE and O ( n / m ) for GKD respectively, where m is storage requirement and n is the number of users. Thus, they are clearly far more costly than the ideal log bound. In practice, we designed a new broadcast encryption scheme RBE that actually achieves these lower bounds. RBE is shown to outperform most efficient BE schemes in mass revocation. We discuss the influence of join as well as the feasibility of adding it in BE schemes by means of performing full updating or overprovisioning.

TCS Journal 2008 Journal Article

Optimizing deletion cost for secure multicast key management

• Zhi-Zhong Chen
• Ze Feng
• Minming Li
• Frances Yao

Multicast and broadcast are efficient ways to deliver messages to a group of recipients in a network. Due to the growing security concerns in various applications, messages are often encrypted with a secret group key. The key tree model which has been widely adopted maintains a set of keys in a tree structure so that in case of group member change, the group key can be updated in a secure and efficient way. In this paper, we focus on the updating cost incurred by member deletions. To implement a sequence of member deletions in any key tree, a certain number of encrypted messages need to be broadcast to accomplish the updates. Our goal is to identify the best key tree which can minimize the worst-case deletion cost (i. e. , the amortized cost over n member deletions). We prove that there is an optimal tree in which each internal node has at most five children and each internal node with at least one non-leaf child has exactly three children. Based on these characterizations, we present a dynamic programming algorithm that computes an optimal key tree in O ( n 2 ) time.

MFCS Conference 2005 Conference Paper

An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules

• Minming Li
• F. Frances Yao

Abstract We consider the problem of job scheduling on a variable voltage processor with d discrete voltage/speed levels. We give an algorithm which constructs a minimum energy schedule for n jobs in O ( dn log n ) time. Previous approaches solve this problem by first computing the optimal continuous solution in O ( n 3 ) time and then adjusting the speed to discrete levels. In our approach, the optimal discrete solution is characterized and computed directly from the inputs. We also show that O ( n log n ) time is required, hence the algorithm is optimal for fixed d.

TCS Journal 2005 Journal Article

Approximation of Walrasian equilibrium in single-minded auctions

• Li-Sha Huang
• Minming Li
• Bo Zhang

We consider a social optimization model of pricing scheme in single-minded auctions, in cases where Walrasian equilibrium does not exist. We are interested in the maximization of the ratio, R, of happy bidders over all agents, in a feasible allocation-pricing scheme. We show NP-hardness of the optimization problem, establish lower and upper bounds of R, as well as develop greedy algorithms to approximate the optimal value of R.

TCS Journal 2004 Journal Article

Performance evaluation for energy efficient topologic control in ad hoc wireless networks

• Minming Li
• Shawn L. Huang
• Xiaoming Sun
• Xiao Huang

Minimizing total energy to keep an ad hoc wireless network symmetrically connected is an NP-hard problem. Recently, several greedy approximations have been proposed, based on k-restricted decompositions of the network. Their performance ratios are established through estimations of the least upper bound ρ k for the ratio between total powers of best possible k-restricted decomposition and the optimal solution. In this paper, we determine the exact value of ρ k for all k.