A tournament 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 Möbius ladders as a subgraph; such a tournament is referred to as Möbius-free. In the first paper we have given a structural description of all Möbius-free tournaments, and have proved that every CM tournament is Möbius-free. In this second paper we establish the converse by using our structural theorems and linear programming approach.

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 be a tournament with a nonnegative integral weight on each arc e. A subset F of arcs is called a feedback arc set if contains no cycles (directed). A collection of cycles (with repetition allowed) is called a cycle packing if each arc e is used at most times by members of . 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 Möbius ladders as a subgraph; such a tournament is referred to as Möbius-free. In this first paper we present a structural description of all Möbius-free tournaments, which relies heavily on a chain theorem concerning internally 2-strong tournaments.

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(U)/(|U|-1)$, where $w(U)$ is the total weight of all edges with both ends in $U$, and the weighted fractional edge-coloring problem can be formulated as the following linear program: minimize ${\bm 1}^T {\bm x}$ subject to $ A{\bm x} = {\bm w}$, ${\bm x} \ge {\bm 0}$, where $A$ is the edge-matching incidence matrix of $G$. These two problems are closely related to the celebrated Goldberg--Seymour conjecture on edge-colorings of multigraphs, and are interesting in their own right. Even when $w(e)=1$ for all edges $e$, determining whether WDP can be solved in polynomial time was posed by Jensen and Toft [Topics in Chromatic Graph Theory, Cambridge University Press, Cambridge, 2015, pp. 327--357] and by Stiebitz et al. [Graph Edge Colouring: Vizing's Theorem and Goldberg's Conjecture, John Wiley, New York, 2012] as an open problem. In this paper we present strongly polynomial-time algorithms for solving them exactly, and develop a novel matching removal technique for multigraph edge-coloring.

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

Let G be a digraph and let π(G) be the linear system consisting of nonnegativity, stability, and domination inequalities. We call G kernel ideal if π(H) defines an integral polytope for each induced subgraph H of G, and we call G kernel Mengerian if π(H) is totally dual integral (TDI) for each induced subgraph H of G. In this paper we show that a digraph is kernel ideal iff it is kernel Mengerian iff it contains none of three forbidden structures; our characterization yields a polynomial-time algorithm for the minimum weighted kernel problem on kernel ideal digraphs. We also prove that it is NP-hard to find a kernel of minimum size even in a planar bipartite digraph with maximum degree at most three.

Braess’s paradox exposes a counterintuitive phenomenon that when travelers selfishly choose their routes in a network, removing links can improve the overall network performance. Under the model of nonatomic selfish routing, we characterize the topologies of k-commodity undirected and directed networks in which Braess’s paradox never occurs. Our results strengthen Milchtaich’s series-parallel characterization (Milchtaich, Games Econom. Behav. 57(2), 321–346 (2006)) for the single-commodity undirected case.

We design a Copula-based generic randomized truthful mechanism for scheduling on two unrelated machines with approximation ratio within [1.5852,1.58606], offering an improved upper bound for the two-machine case. Moreover, we provide an upper bound 1.5067711 for the two-machine two-task case, which is almost tight in view of the known lower bound of 1.506 for the scale-free truthful mechanisms. Of independent interest is the explicit incorporation of the concept of Copula in the design and analysis of the proposed approximation algorithm. We hope that techniques like this one will also prove useful in solving other related problems in the future.

We analyze the network congestion game with atomic players, asymmetric strategies, and the maximum latency among all players as social cost. This important social cost function is much less understood than the average latency. We show that the price of anarchy is at most two, when the network is a ring and the link latencies are linear. Our bound is tight. This is the first sharp bound for the maximum latency objective.

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

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