Search

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).

Let [Formula: see text] be a tournament with a nonnegative integral weight w(e) on each arc e. A subset F of arcs is called a feedback arc set (FAS) if [Formula: see text] contains no cycles (directed). A collection [Formula: see text] of FASs (with repetition allowed) is called an FAS packing if each arc e is used at most w(e) times by the members of [Formula: see text]. The purpose of this paper is to give a characterization of all tournaments [Formula: see text] with the property that, for every nonnegative integral weight function w defined on A, the minimum total weight of a cycle is equal to the maximum size of an FAS packing. Funding: This work was supported by the National Natural Science Foundation of China [Grants 11801266 and 11971228]; the Chinese Academy of Sciences [Grants XDA27000000 and ZDBS-LY-7008]; the Ministry of Science and Technology of China [Grant 2018AAA0101002]; the Research Grants Council of Hong Kong; the Fundamental Research Funds for the Central Universities [Grant 020314380035].

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

A tournament T = ( V , A ) is called cycle Mengerian (CM) if it satisfies the minimax relation on packing and covering cycles, for every nonnegative integral weight function defined on A. The purpose of this series of two papers is to show that a tournament is CM iff it contains none of four Mobius ladders as a subgraph; such a tournament is referred to as Mobius-free. In the first paper we have given a structural description of all Mobius-free tournaments, and have proved that every CM tournament is Mobius-free. In this second paper we establish the converse by using our structural theorems and linear programming approach.

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.

In this series of two papers we examine the classical problem of ranking a set of players on the basis of a set of pairwise comparisons arising from a sports tournament, with the objective of minimizing the total number of upsets, where an upset occurs if a higher ranked player was actually defeated by a lower ranked player. This problem can be rephrased as the so-called minimum feedback arc set problem on tournaments, which arises in a rich variety of applications and has been a subject of extensive research. In this series we study this NP-hard problem using structure-driven and linear programming approaches. Let T = ( V , A ) be a tournament with a nonnegative integral weight w ( e ) on each arc e. A subset F of arcs is called a feedback arc set if T \ F contains no cycles (directed). A collection C of cycles (with repetition allowed) is called a cycle packing if each arc e is used at most w ( e ) times by members of C . We call T cycle Mengerian (CM) if, for every nonnegative integral function w defined on A, the minimum total weight of a feedback arc set is equal to the maximum size of a cycle packing. The purpose of these two papers is to show that a tournament is CM iff it contains none of four Mobius ladders as a subgraph; such a tournament is referred to as Mobius-free. In this first paper we present a structural description of all Mobius-free tournaments, which relies heavily on a chain theorem concerning internally 2-strong tournaments.

This paper establishes several sufficient conditions for the weak Pareto optimality of Nash equilibria in nonatomic routing games on single- and multi-commodity networks, where a Nash equilibrium (NE) is weakly Pareto optimal (WPO) if under it no deviation of all players could make everybody better off. The results provide theoretical and technical bases for characterizing graphical structures for nonatomic routing games to admit WPO NEs. We prove that the NE of every nonatomic routing game on a single or multi-commodity network is WPO (regardless of the choices of nonnegative, continuous, nondecreasing latency functions on network links) if the network does not have two links x, y and three paths each of which goes from some origin to some destination such that the intersections of the three paths with $$\{x,y\}$$ are $$\{x\},\{y\}$$ and $$\{x,y\}$$, respectively. This sufficient condition leads to an alternative proof of the recent result that the NE of every 2-commodity nonatomic routing game on any undirected cycle is WPO. We verify a general property satisfied by all feasible 2-commodity routings (not necessarily controlled by selfish players) on undirected cycles, which roughly says that no feasible routing can “dominate” another in some sense. The property is crucial for proving the weak Pareto optimality associated to the building blocks of undirected graphs on which all NEs w.r.t. two commodities are WPO.

We address the metric ring star problem with fixed edge-cost ratio, abbreviated as RSP. Given a complete graph $$G=(V,E)$$ with a specified depot node $$d\in V$$ , a nonnegative cost function $$c\in \mathbb {R}_+^E$$ on E which satisfies the triangle inequality, and an edge-cost ratio $$M\ge 1$$ , the RSP is to locate a ring $$R=(V',E')$$ in G, a simple cycle through d or d itself, aiming to minimize the sum of two costs: the cost for constructing ring R, i.e., $$M\cdot \sum _{e\in E'}c(e)$$ , and the cost for attaching nodes in $$V{\setminus } V'$$ to their closest ring nodes (in R), i.e., $$\sum _{u\in V{\setminus } V'}\min _{v\in V'}c(uv)$$ . We show that the singleton ring d is an optimal solution of the RSP when $$M\ge (|V|-1)/2$$ . This particularly implies a $$\sqrt{|V|-1}$$ -approximation algorithm for the RSP with any $$M\ge 1$$ . We present randomized 3-approximation algorithm and deterministic 5.06-approximation algorithm for the RSP, by adapting algorithms for the tour-connected facility location problem (tour-CFLP) and single-source rent-or-buy problem due to Eisenbrand et al. and Williamson and van Zuylen, respectively. Building on the PTAS of Eisenbrand et al. for the tour-CFLP, we give a PTAS for the RSP with $$|V|/M=O(1)$$ . We also consider the capacitated RSP (CRSP) which puts an upper limit k on the number of leaf nodes that a ring node can serve, and present a $$(10+6M/k)$$ -approximation algorithm for this capacitated generalization. Heuristics based on some natural strategies are proposed for both the RSP and CRSP. Simulation results demonstrate that the proposed approximation and heuristic algorithms have good practical performances.

Given a multigraph $G=(V,E)$ with a positive rational weight $w(e)$ on each edge $e$, the weighted density problem (WDP) is to find a subset $U$ of $V$, with $|U|\ge 3$ and odd, that maximizes $2w(...

Games with strategic substitutes (GSS) are generally less tractable than games with strategic complements (GSC). This paper revisits the GSC versus GSS comparison by establishing a novel connection between them. We show through a network perspective that, when the strategy set of each player is the product of some linearly ordered sets that are order isomorphic to subsets of the real space, every GSC can be embedded into a GSS, such that the set of pure strategy Nash equilibria of the former is a projection of that of the latter. In comparison, no GSS with multiple pure strategy Nash equilibria can be embedded into any GSC. In this sense, the class of GSS is broader than the class of GSC.

Let G = (V, E) be a simple graph and $\mathbf {w}\in \mathbb {Z}^{E}_{>0}$ assign each edge e ∈ E a positive integer weight w(e). A subset of E that intersects every triangle of G is called a triangle cover of (G, w), and its weight is the total weight of its edges. A collection of triangles in G (repetition allowed) is called a triangle packing of (G, w) if each edge e ∈ E appears in at most w(e) members of the collection. Let τ t (G, w) and ν t (G, w) denote the minimum weight of a triangle cover and the maximum cardinality of a triangle packing of (G, w), respectively. Generalizing Tuza’s conjecture for unit weight, Chapuy et al. conjectured that τ t (G, w)/ν t (G, w) ≤ 2 holds for every simple graph G and every $\mathbf {w}\in \mathbb {Z}^{E}_{>0}$ . In this paper, using a hypergraph approach, we design polynomial-time combinatorial algorithms for finding triangle covers of small weights. These algorithms imply new sufficient conditions for the conjecture of Chapuy et al. More precisely, given (G, w), suppose that all edges of G are covered by the set ${\mathscr {T}}_{G}$ consisting of edge sets of triangles in G. Let $|E|_{w}={\sum }_{e\in E}w(e)$ and $|{\mathscr {T}}_{G}|_{w}={\sum }_{\{e,f,g\}\in {\mathscr {T}}_{G}}w(e)w(f)w(g)$ denote the weighted numbers of edges and triangles in (G, w), respectively. We show that a triangle cover of (G, w) of weight at most 2ν t (G, w) can be found in strongly polynomial time if one of the following conditions is satisfied: (i) $\nu _{t}(G,\mathbf {w})/|{\mathscr {T}}_{G}|_{w}\ge \frac {1}{3}$ , (ii) $\nu _{t}(G,\mathbf {w})/|E|_{w}\ge \frac {1}{4}$ , (iii) $|E|_{w}/|{\mathscr {T}}_{G}|_{w}\ge 2$ .

We study the two-opposite-facility location game on a line segment, where a mechanism determines the locations of a popular facility and an obnoxious facility for finitely many agents. The agents report their private locations, and try to maximize their own utilities depending on their distances to the facilities. We prove tight bounds on the inapproximability of both randomized and deterministic strategy-proof mechanisms for maximizing the total agent utility minus a penalty determined by the distance between the two facilities.