The Team Order Problem: Maximizing the Probability of Matching Being Large Enough
Haris Aziz, Jiarui Gan, Grzegorz Lisowski, Ali Pourmiri · 2026
Read The Team Order Problem: Maximizing the Probability of Matching Being Large Enough by Haris Aziz, Jiarui Gan, Grzegorz Lisowski, Ali Pourmiri (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21234.txt.
Introduction
Haris Aziz and colleagues study the team order problem: arranging one team's players against a fixed opposing order to maximize the chance of winning enough matches. Input is a graph of win probabilities for each pairing, and output is the optimal ordering for team one. Their central result is a polynomial-time approximation scheme whose winning probability falls at most epsilon short of optimal. They also give tractability results for special cases and a bound on how far a maximum-weight matching falls from the best achievable probability.
Catalog record
| CREATOR | Haris Aziz, Jiarui Gan, Grzegorz Lisowski, Ali Pourmiri |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64627 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.21234
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Team Order Problem: Maximizing the Probability of Matching Being Large Enough Haris Aziz, Jiarui Gan, Grzegorz Lisowski, Ali Pourmiri Abstract We consider a matching problem, which is meaningful in team competitions, as well as in information theory, recommender systems, and assignment problems. In the competitions which we study, each competitor in a team order plays a match with the corresponding opposing player. The team that wins more matches wins. We consider a problem where the input is the graph of probabilities that a team 1 player can win against the team 2 player, and the output is the optimal ordering of team 1 players given the fixed ordering of team 2. Our central result is a polynomial-time approximation scheme (PTAS) to compute a matching whose winning probability is at most ε \varepsilon less than the winning probability of the optimal matching. We also provide tractability results for several special cases of the problem, as well as an analytical bound on how far the winning probability of a maximum weight matching of the underlying graph is from the best achievable winning probability. 1 Introduction Bipartite matching underpins several impactful problems in allocation and market design problems including kidney allocation, adword auctions, on demand taxi allocation, refugee assignment, or school choice (see, e.g., 11 ). We consider a fundamental matching problem with an underlying weighted bipartite graph where each edge weight has weight between 0 and 1. Instead of focusing on the classical objective of maximizing the total weight of the matching, we focus on a different objective with a probabilistic interpretation: We want to compute a matching that maximizes the probability of reaching a target size. This problem can model several scenarios, including that of the so called team order problem . One of the most relevant applications of our setting is the rivalry between teams of contestants. Consider team competitions in which both teams put forward an ordering of their players. The contestants then play matches against the corresponding contestants from the opposing team. The team that wins more matches wins the overall competition. Such competitions are not only held in various inter-club tennis competitions, the same format is also used in international table tennis and badminton competitions, such as the Corbillon Cup, Swaythling Cup, Thomas Cup, and the Olympic Games. We focus on the problem in which one team’s order is fixed (as is the case in many situations where the home team commits to an ordering) and the other team wants to compute the optimal ordering. As the ordering of one team is fixed, the problem of computing the other team’s ordering is essentially a competitor matching problem. The problem of finding a way to maximize the number of achieved goals by setting an appropriate line-up is not limited to sport competitions. Indeed, it admits several other motivations in competitive contexts such as politics (fielding political candidates in different constituencies against candidates of a rival party). Our problem also provides a perspective into finding durable matchings . Suppose that we are given the probability of success of various partnerships. For example a partnership could represent a job placement or allocation of refugee family to a council (see, e.g., 6 ; 1 ). A typical objective could be maximizing the expected number of partnerships. However, another meaningful objective that is centred around a particular target could be to maximize the probability of having a target number of successful partnerships , which maps to the objective that we study . Another potential application of our research relates to information networks (see, e.g., 22 ). Suppose that we are given such a network, represented by a flow network. There, each edge has a reliability probability of a message reaching the other side , and we want to find a flow maximizing probability of delivering a target number of messages. Finally, our research is motivated by its applications in recommendation systems (see, e.g., 26 ). Suppose that a ranked list of recommendations needs to be displayed with each item having a probability of being clicked depending on its position in the ranking list. One may want to maximize the probability of having a target number of items being clicked , which can be captured by our problem. We explore the following questions. How hard is the team order problem? Under what conditions is it easy to solve? What are reasonable approximation approaches for the problem? We note that the problem that we study in this paper is closely related to the maximum-weight matching problem. There, we are given a bipartite graph, where each edge is assigned a weight, and the objective is to find a matching with the maximum sum of weights. In fact, our results reflect that finding the solution to that problem provides a good approximation of the optimal solution. However, the problem we study is substantially more complex. Indeed, for an instance of the team order problem to be positive, we require that the weights in a selected matching are large enough for some subset of edges, instead of maximizing their global sum. Furthermore, given the strategic games interpretation of our setting, our results concern the computation of the optimal response to the opponent choice, which is an important step towards the study of equilibria in this setting. Contributions. We first show that the winning probability of a given matching (line-up) can be computed in polynomial time (Proposition 1 ) . Subsequently, we show that in certain settings computing an optimal line-up is tractable. In particular, when the input winning probability of each partnership takes its value from a size-three set \{\alpha,\beta,0\} we show that the optimal matching can be computed in polynomial time (Theorem 1 ) . While we conjecture that the team order problem is hard in the general case, we show that it is tractable for practical purposes. Our central result is a polynomial-time approximation scheme (PTAS) 1 1 1 A PTAS is a scheme which, for every instance of a problem and \varepsilon>0 , provides an approximate solution based on \varepsilon . to compute a matching whose winning probability is at most \varepsilon less than the winning probability of the optimal matching (Theorem 3 ) . Although the winning probability is not a linear objective, we show that the general problem of computing an optimal matching can be solved via integer linear programming. Also, we provide an analytical bound on how far the winning probability of a maximum weight matching is from the best achievable winning probability. 2 Related Work Our results are relevant to a number of research direction in multi-agent systems. Matching Theory. Matching problems have been widely studied in combinatorial optimization. The standard objectives typically focus on maximizing the weight of the matching (see, e.g., 9 ; 25 ). In our context, maximizing the weight of the underlying weighted bipartite graph gives us a matching maximizing the expected number of matches won. Our objective is different as we want to maximize the probability of winning a target number of matches. The paper most relevant to our work is by Tang et al. 29 , which concerns the same setting but considered different problems. It takes an economic design approach and presents