This paper studies the problem of minimizing group-level inequity in facility location games on the real line, where agents belong to different groups and may act strategically. We explore a fairness-oriented objective that minimizes the maximum group effect. For each group, the group effect is defined as its total or maximum distance to the nearest facility, weighted by group-specific factors. We show that this formulation generalizes several prominent optimization objectives, including the classical utilitarian (social cost) and egalitarian (maximum cost) objectives, as well as two group-fair objectives, maximum total and average group cost. In order to minimize the maximum group effect, we first propose two novel mechanisms for the single-facility case, the Balanced mechanism and the Major-Phantom mechanism. Both are strategyproof and achieve tight approximation guarantees under distinct formulations of the maximum group effect objective. Our mechanisms not only close the existing gap in approximation bounds for the group-fairness objectives, maximum total group cost and maximum average group cost, but also unify many classical truthful mechanisms within a broader fairness-aware framework. For the two-facility case, we revisit and extend the classical endpoint mechanism to our generalized setting and demonstrate that it provides tight bounds for two distinct maximum group effect objectives.

Strategyproofness in network auctions requires that bidders not only report their valuations truthfully, but also do their best to invite neighbours from the social network. In contrast to canonical auctions, where the value-monotone allocation in Myerson's Lemma is a cornerstone, a general principle of allocation rules for strategyproof network auctions is still missing. We show that, due to the absence of such a principle, even extensions to multi-unit network auctions with single-unit demand present unexpected difficulties, and all pioneering researches fail to be strategyproof. For the first time in this field, we identify two categories of monotone allocation rules on networks: Invitation-Depressed Monotonicity (ID-MON) and Invitation-Promoted Monotonicity (IP-MON). They encompass all existing allocation rules of network auctions as specific instances. For any given ID-MON or IP-MON allocation rule, we characterize the existence and sufficient conditions for the strategyproof payment rules, and show that among all such payment rules, the revenue-maximizing one exists and is computationally feasible. With these results, the obstacle of combinatorial network auction with single-minded bidders is now resolved.

The augmentation of algorithms with predictions of the optimal solution, such as from a machine-learning algorithm, has garnered significant attention in recent years, particularly in facility location problems. Moving beyond the traditional focus on utilitarian and egalitarian objectives, we design learning-augmented facility location mechanisms for the envy ratio objective, a fairness metric defined as the maximum ratio between the utilities of any two agents. For the deterministic setting, we propose a mechanism which utilizes predictions to achieve $\alpha$-consistency and $\frac{\alpha}{\alpha - 1}$-robustness for a selected parameter $\alpha \in [1,2]$, and prove its optimality. We also resolve open questions raised by Ding et al. [2020], devising a randomized mechanism without predictions to improve upon the best-known approximation ratio from $2$ to $1.8944$. Building upon these advancements, we construct a novel randomized mechanism which incorporates predictions to achieve improved performance guarantees.

We propose a novel protocol for crowdsourcing and crowdsensing by integrating combinatorial auctions and networks. With this protocol, agents who have already participated in crowdsourcing or crowdsensing tasks are incentivized to invite other agents to join the task. This new protocol aims to attract a growing number of skilled agents, thereby significantly improving the performance of crowdsourcing and crowdsensing. The challenge to this objective is how to incentivize each participant not only to contribute her full ability but also to try her best to spread the task information to her neighbors in the network. This problem is called networked auction or diffusion auction, which is a very new topic in algorithmic game theory and AI and has attracted considerable attention in recent years. Notably, current diffusion auctions lack customization for crowdsourcing or crowdsensing scenarios. Furthermore, no established diffusion auction adequately addresses the intricacies of handling multiple or even combinatorial tasks. This work is the first to design networked auction protocols for combinatorial tasks. From both theory and experiments, we have shown that the new protocols are proven to be incentive compatible, and that both the system’s cost and the requester’s costs could be decreased.

In recent years, a new branch of auction models called diffusion auction has extended the traditional auction into social network scenarios. The diffusion auction models the auction as a networked market whose nodes are potential customers and whose edges are the relations between these customers. The diffusion auction mechanism can incentivize buyers to not only submit a truthful bid, but also further invite their surrounding neighbors to participate into the auction. It can convene more participants than traditional auction mechanisms, which leads to better optimizations of different key aspects, such as social welfare, seller’s revenue, amount of redistributed money and so on. The diffusion auctions have recently attracted a discrete interest in the algorithmic game theory and market design communities. This survey summarizes the current progress of diffusion auctions.