Return to Answer

I have found a paper on a generalization of the Birkhoff-von Neumann theorem here:

http://cowles.econ.yale.edu/conferences/2009/sum-09/theory/che.pdf

The authors are Eric Budish, Yeon-Koo Che, Fuhito Kojima, and Paul Milgram.

Here is the Abstract:

The Birkhoff-von Neumann Theorem shows that any bistochastic matrix can be written as a convex combination of permutation matrices. In particular, in a setting where n objects must be assigned to n agents, one object per agent, any random assignment matrix can be resolved into a deterministic assignment in accordance with the specified probability matrix. We generalize the theorem to accommodate a complex set of constraints encountered in many real-life market design problems. Specifically, the theorem can be extended to any environment in which the set of constraints can be partitioned into two hierarchies. Further, we show that this bihierarchy structure constitutes a maximal domain for the theorem, and we provide a constructive algorithm for implementing a random assignment under bihierarchical constraints. We provide several applications, including (i) single-unit random assignment, such as school choice; (ii) multi-unit random assignment, such as course allocation and fair division; and (iii) two- sided matching problems, such as the scheduling of inter-league sports matchups. The same method also finds applications beyond economics, generalizing previous results on the minimize makespan problem in the computer science literature

I have also found a master's thesis that involved generalization from a matrix to a hyper matrix, a matrix in higher dimensions. So one example would be a cubic array of numbers instead of a square. He proves a generalization to the three dimensional matrices which are called blocks. There are some open questions there as well. I found it interesting as I have wondered about extending the two dimensions of matrices to three coordinates and seeing what happened. It is available here:

https://ritdml.rit.edu/dspace/bitstream/1850/5967/1/NReffThesis05-18-2007.pdf

I have found a paper on a generalization of the Birkhoff-von Neumann theorem here:

http://cowles.econ.yale.edu/conferences/2009/sum-09/theory/che.pdf (Wayback Machine)

The authors are Eric Budish, Yeon-Koo Che, Fuhito Kojima, and Paul Milgram.

Here is the Abstract:

The Birkhoff-von Neumann Theorem shows that any bistochastic matrix can be written as a convex combination of permutation matrices. In particular, in a setting where n objects must be assigned to n agents, one object per agent, any random assignment matrix can be resolved into a deterministic assignment in accordance with the specified probability matrix. We generalize the theorem to accommodate a complex set of constraints encountered in many real-life market design problems. Specifically, the theorem can be extended to any environment in which the set of constraints can be partitioned into two hierarchies. Further, we show that this bihierarchy structure constitutes a maximal domain for the theorem, and we provide a constructive algorithm for implementing a random assignment under bihierarchical constraints. We provide several applications, including (i) single-unit random assignment, such as school choice; (ii) multi-unit random assignment, such as course allocation and fair division; and (iii) two- sided matching problems, such as the scheduling of inter-league sports matchups. The same method also finds applications beyond economics, generalizing previous results on the minimize makespan problem in the computer science literature

I have also found a master's thesis that involved generalization from a matrix to a hyper matrix, a matrix in higher dimensions. So one example would be a cubic array of numbers instead of a square. He proves a generalization to the three dimensional matrices which are called blocks. There are some open questions there as well. I found it interesting as I have wondered about extending the two dimensions of matrices to three coordinates and seeing what happened. It is available here:

https://ritdml.rit.edu/dspace/bitstream/1850/5967/1/NReffThesis05-18-2007.pdf

I have found a paper on a generalization of the Birkhoff-von Neumann theorem here:

http://cowles.econ.yale.edu/conferences/2009/sum-09/theory/che.pdf

Here is the Abstract:

The Birkhoff-von Neumann Theorem shows that any bistochastic matrix can be written as a convex combination of permutation matrices. In particular, in a setting where n objects must be assigned to n agents, one object per agent, any random assignment matrix can be resolved into a deterministic assignment in accordance with the specified probability matrix. We generalize the theorem to accommodate a complex set of constraints encountered in many real-life market design problems. Specifically, the theorem can be extended to any environment in which the set of constraints can be partitioned into two hierarchies. Further, we show that this bihierarchy structure constitutes a maximal domain for the theorem, and we provide a constructive algorithm for implementing a random assignment under bihierarchical constraints. We provide several applications, including (i) single-unit random assignment, such as school choice; (ii) multi-unit random assignment, such as course allocation and fair division; and (iii) two- sided matching problems, such as the scheduling of inter-league sports matchups. The same method also finds applications beyond economics, generalizing previous results on the minimize makespan problem in the computer science literature

I have also found a master's thesis that involved generalization from a matrix to a hyper matrix, a matrix in higher dimensions. So one example would be a cubic array of numbers instead of a square. He proves a generalization to the three dimensional matrices which are called blocks. There are some open questions there as well. I found it interesting as I have wondered about extending the two dimensions of matrices to three coordinates and seeing what happened. It is available here:

https://ritdml.rit.edu/dspace/bitstream/1850/5967/1/NReffThesis05-18-2007.pdf

I have found a paper on a generalization of the Birkhoff-von Neumann theorem here:

http://cowles.econ.yale.edu/conferences/2009/sum-09/theory/che.pdf

The authors are Eric Budish, Yeon-Koo Che, Fuhito Kojima, and Paul Milgram.

Here is the Abstract:

The Birkhoff-von Neumann Theorem shows that any bistochastic matrix can be written as a convex combination of permutation matrices. In particular, in a setting where n objects must be assigned to n agents, one object per agent, any random assignment matrix can be resolved into a deterministic assignment in accordance with the specified probability matrix. We generalize the theorem to accommodate a complex set of constraints encountered in many real-life market design problems. Specifically, the theorem can be extended to any environment in which the set of constraints can be partitioned into two hierarchies. Further, we show that this bihierarchy structure constitutes a maximal domain for the theorem, and we provide a constructive algorithm for implementing a random assignment under bihierarchical constraints. We provide several applications, including (i) single-unit random assignment, such as school choice; (ii) multi-unit random assignment, such as course allocation and fair division; and (iii) two- sided matching problems, such as the scheduling of inter-league sports matchups. The same method also finds applications beyond economics, generalizing previous results on the minimize makespan problem in the computer science literature

I have also found a master's thesis that involved generalization from a matrix to a hyper matrix, a matrix in higher dimensions. So one example would be a cubic array of numbers instead of a square. He proves a generalization to the three dimensional matrices which are called blocks. There are some open questions there as well. I found it interesting as I have wondered about extending the two dimensions of matrices to three coordinates and seeing what happened. It is available here:

https://ritdml.rit.edu/dspace/bitstream/1850/5967/1/NReffThesis05-18-2007.pdf

I have found a paper on a generalization of the Birkhoff-von Neumann theorem here:

http://cowles.econ.yale.edu/conferences/sum-09/theory/che.pdf

Here is the Abstract:

The Birkhoff-von Neumann Theorem shows that any bistochastic matrix can be written as a convex combination of permutation matrices. In particular, in a setting where n objects must be assigned to n agents, one object per agent, any random assignment matrix can be resolved into a deterministic assignment in accordance with the specified probability matrix. We generalize the theorem to accommodate a complex set of constraints encountered in many real-life market design problems. Specifically, the theorem can be extended to any environment in which the set of constraints can be partitioned into two hierarchies. Further, we show that this bihierarchy structure constitutes a maximal domain for the theorem, and we provide a constructive algorithm for implementing a random assignment under bihierarchical constraints. We provide several applications, including (i) single-unit random assignment, such as school choice; (ii) multi-unit random assignment, such as course allocation and fair division; and (iii) two- sided matching problems, such as the scheduling of inter-league sports matchups. The same method also finds applications beyond economics, generalizing previous results on the minimize makespan problem in the computer science literature

I have also found a master's thesis that involved generalization from a matrix to a hyper matrix, a matrix in higher dimensions. So one example would be a cubic array of numbers instead of a square. He proves a generalization to the three dimensional matrices which are called blocks. There are some open questions there as well. I found it interesting as I have wondered about extending the two dimensions of matrices to three coordinates and seeing what happened. It is available here:

https://ritdml.rit.edu/dspace/bitstream/1850/5967/1/NReffThesis05-18-2007.pdf

I have found a paper on a generalization of the Birkhoff-von Neumann theorem here:

http://cowles.econ.yale.edu/conferences/2009/sum-09/theory/che.pdf

Here is the Abstract:

The Birkhoff-von Neumann Theorem shows that any bistochastic matrix can be written as a convex combination of permutation matrices. In particular, in a setting where n objects must be assigned to n agents, one object per agent, any random assignment matrix can be resolved into a deterministic assignment in accordance with the specified probability matrix. We generalize the theorem to accommodate a complex set of constraints encountered in many real-life market design problems. Specifically, the theorem can be extended to any environment in which the set of constraints can be partitioned into two hierarchies. Further, we show that this bihierarchy structure constitutes a maximal domain for the theorem, and we provide a constructive algorithm for implementing a random assignment under bihierarchical constraints. We provide several applications, including (i) single-unit random assignment, such as school choice; (ii) multi-unit random assignment, such as course allocation and fair division; and (iii) two- sided matching problems, such as the scheduling of inter-league sports matchups. The same method also finds applications beyond economics, generalizing previous results on the minimize makespan problem in the computer science literature

I have also found a master's thesis that involved generalization from a matrix to a hyper matrix, a matrix in higher dimensions. So one example would be a cubic array of numbers instead of a square. He proves a generalization to the three dimensional matrices which are called blocks. There are some open questions there as well. I found it interesting as I have wondered about extending the two dimensions of matrices to three coordinates and seeing what happened. It is available here:

https://ritdml.rit.edu/dspace/bitstream/1850/5967/1/NReffThesis05-18-2007.pdf