Assignment

Bruce C. Dieffenbach ()
Additional contact information
Bruce C. Dieffenbach: Independent author

Chapter 17 in Conjugate Duality in Economic Analysis, 2026, pp 127-130 from Springer

Abstract: Abstract We analyze the problem of assigning n people to n jobs. The value of person j in job i is $$X_{ij}^{\ast }$$, and let X* denote the n×n matrix of these values. The goal is to maximize the total value. The assignment of people to jobs is a permutation. A mathematical model of a permutation is an n×n matrix X, having components Xij. Each row has a single component one, and each column has a single component one. All other components are zero. Interpret Xij=1 as the assignment of person j to job i. The total value achieved by a permutation X is the linear function $$\left \langle {\textit {{\sf { {X}}}}}^{\ast },{\textit {{\sf { {X}}}}}\right \rangle$$. The assignment problem was important in the historical development of the theory of linear programming and duality. At first glance, it might seem that the problem is not a convex optimization. Choosing the optimum permutation from among the n! possible permutations is a choice among discrete alternatives, not a convex problem. Nevertheless, it is possible to cast the problem as an interesting convex optimization, having a dual with an insightful economic interpretation. A matrix is doubly stochastic if the sum of each column is one, and the sum of each row is one, and every component is nonnegative. A permutation is doubly stochastic, and any convex combination of permutations is doubly stochastic. Thus any doubly stochastic linear transformation is a convex combination of permutations. That the permutations are the extreme points of the set of doubly stochastic linear transformation is a fundamental theorem. Set the assignment problem as the maximization of$$~\left \langle {\textit {{\sf { {X}}}}}^{\ast },{\textit {{\sf { {X}}}}}\right \rangle$$ among all doubly stochastic linear transformations.

Date: 2026
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:conchp:978-3-032-21396-9_17

Ordering information: This item can be ordered from
http://www.springer.com/9783032213969

DOI: 10.1007/978-3-032-21396-9_17

Access Statistics for this chapter

More chapters in Contributions to Economics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().