Changjun Wang

Many large cities have adopted a policy of restricting the number of new vehicle licenses in order to address the challenges of traffic and air pollution problems. An important question that then arises is how to allocate these limited new license quotas among a large set of demanders while taking both social efficiency and equality into consideration. Inspired by this practical problem, we study the problem of designing simple and optimal mechanisms to tradeoff between efficiency and equality in a similar public goods allocation problem. We first propose a truthful two-group mechanism framework that is both general and simple and then use it to compute the optimal solution that maximizes social efficiency while guaranteeing a certain level of equality. Interestingly and surprisingly, under some natural conditions regarding the players’ private values, we show that the optimal mechanisms within the proposed framework are always the mechanisms that first run an auction and then run a lottery (ATL for short). In addition, beyond the framework and those conditions, we prove that the ATL mechanism can always guarantee at least [ ] ([ ] is the minimum equality level) of the optimal solution efficiency. This approximation ratio can in practice be further improved to near-optimal when resources are scarce and the natural conditions hold. We further establish a theoretical connection between these natural conditions and common value distributions, demonstrating that these conditions are widely satisfied in practice. Finally, we implement several experiments to verify the ATL mechanism’s optimality and robustness. This paper was accepted by Chung Piaw Teo, optimization. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72401252, 72192830, 72192832, 62472428, 72192804, 72301235, 72394360 and 72394363]; the Public Computing Cloud, Renmin University of China, the fund for building world-class universities (disciplines) of Renmin University of China; the Beijing Natural Science Foundation [Grant Z220001]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/mnsc.2022.02785 .

We analyze an infinite-horizon deterministic joint replenishment model from a non-cooperative game-theoretical approach. In this model, a group of retailers can choose to jointly place an order, which incurs a major setup cost independent of the group, and a minor setup cost for each retailer. Additionally, each retailer is associated with a holding cost. Our objective is to design cost allocation rules that minimize the long-run average system cost while accounting for the fact that each retailer independently selects its replenishment interval to minimize its own cost. We introduce a class of cost allocation rules that distribute the major setup cost among the associated retailers in proportion to their predefined weights. For these rules, we establish a monotonicity property of agent better responses, which enables us to prove the existence of a payoff dominant pure Nash equilibrium that can also be computed efficiently. We then analyze the efficiency of these equilibria by examining the price of stability (PoS), the ratio of the best Nash equilibrium's system cost to the social optimum, across different information settings. In particular, our analysis reveals that one rule, which leverages retailers' own holding cost rates, achieves a near-optimal PoS of 1.25, while another rule that does not require access to retailers' private information also yields a favorable PoS.

In this study, we investigate two different types of duopolistic competitive assortment problems under the multinomial logit model: (1) In simultaneous assortment competition, both retailers make strategic decisions and offer assortments simultaneously. The objective is to identify an assortment strategy profile that prevents unilateral and profitable deviations by either retailer; (2) In sequential assortment competition, retailers sequentially offer assortments, with one round to each retailer. The objective is to determine the optimal strategy for the leader (first-moved retailer), with the follower (second-moved retailer) reacting optimally based on the leader's choice. We extend prior work by introducing a more general competitive model incorporating common products under the multinomial logit model, capable of capturing a variety of choice behaviors that appear in retailing scenarios, such as consumer loyalty and rarity effects. For simultaneous assortment competition, we study the existence of a pure-strategy Nash equilibrium and fully characterize the structures of equilibrium outcomes. Specifically, we demonstrate the existence of an equilibrium that always Pareto-dominates others in the settings with both common and exclusive products. This equilibrium is efficiently computed using a carefully crafted iterative best response process. However, deciding whether a pure-strategy Nash equilibrium exists in more general settings, including those with common products and cardinality constraints, turns out to be NP-complete. For sequential assortment competition, we find that the subgame perfect Nash equilibrium leads to higher profitability for both the leader and the follower compared to the Pareto-dominant equilibrium in simultaneous assortment competition. This significant difference from general sequential games suggests that both retailers would prefer participating in a sequential assortment competition over a simultaneous counterpart. Despite its profitability advantages, computing the subgame perfect Nash equilibrium for duopoly sequential assortment competition is NP-hard, even with only exclusive products. To address this hardness result, we propose a fully polynomial-time approximation scheme for problems involving both common and exclusive products. We also extend our analysis and develop near-optimal approximation algorithms or establish inapproximability hardness results for the sequential assortment competition with capacity constraints. A full version of this paper can be found at https://ssrn.com/abstract=4857696.

In this paper, we are concerned with bounding agents’ residence times in the network for a broad class of atomic dynamic routings. We explore novel token techniques to circumvent direct analysis on complicated chain effects of dynamic routing choices. Even though agents may enter the network over time for an infinite number of periods, we prove that under a mild condition, the residence time of every agent is upper bounded (by a network-dependent constant plus the total number of agents inside the network at the entry time of the agent). Applying this result to three game models of atomic dynamic routing in the recent literature, we establish that the residence times of selfish agents in a series-parallel network with a single origin-destination pair are upper bounded at equilibrium, provided the number of incoming agents at each time point does not exceed the network capacity (i.e., the smallest total capacity of edges in the network whose removal separates the origin from the destination).