Integer Programming Approaches to Stochastic Games Arising in Paired Kidney Exchange and Industrial Organization

Dehghanian, Amin (2015) Integer Programming Approaches to Stochastic Games Arising in Paired Kidney Exchange and Industrial Organization. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

Preview

PDF Primary Text Download (431kB)

Abstract

We investigate three different problems in this dissertation. The first two problems are related to games arising in paired kidney exchange, and the third is rooted in a computational branch of the industrial organization literature. We provide more details on these problems in the following.

End-stage renal disease (ESRD), the final stage of chronic kidney disease, is the ninth-leading cause of death in the United States, where it afflicts more than a half million patients, and costs more than forty billion dollars indirect expenses annually. Transplantation is the preferred treatment for ESRD; unfortunately, there is a severe shortage of transplantable kidneys.
Kidney exchange is a growing approach to alleviate the shortage of kidneys for transplantation, and the United States is considering creating a national kidney exchange program since such a program provides more and better transplants. A major challenge to establish a national kidney exchange program is the lack of incentives for transplant centers to participate in such a program. To overcome this issue, the kidney transplant community has recently proposed a payment strategy framework that incentivizes transplant centers to participate in a national program. Absent from this debate is a careful investigation of how to design these incentives. We develop a principal-agent model to analyze these incentives and find an equilibrium payment strategy. We develop a mixed-integer bilinear bilevel program to compute an equilibrium payment strategy. We show that this bilevel program can be solved as a mixed-integer linear program. We calibrate our model and provide several data-driven insights about advantages of a national kidney exchange program. We shed light on several controversial policy questions about an equilibrium payment strategy. In particular, we demonstrate that there exists a ``win-win'' payment strategy that could result in saving thousands of lives and billions of dollars annually.

Consensus stopping games are a class of stochastic games that arises in the context of kidney exchange. Specifically, the problem of finding a socially optimal pure stationary equilibrium of a consensus stopping game is adapted to value a given kidney exchange. However, computational difficulties have limited its applicability. We show that a consensus stopping game may have many pure stationary equilibria, which in turn raises the question of equilibrium selection. Given an objective criterion, we study the problem of finding a best pure stationary equilibrium for the game, which we show to be NP-hard. We characterize the pure stationary equilibria, show that they form an independence system, and develop several families of valid inequalities. We then solve the equilibrium selection problem as a mixed-integer linear program (MILP) by a branch-and-cut approach. Our computational results demonstrate the advantages of our approach over a commercial solver.

Industrial organization is an area of economics that studies firms and markets. Currently, a class of stochastic games are adopted to model behaviors of firms in a market. However, inherent challenges in computability of stationary equilibria have restricted its applicability. To overcome this challenge, we develop several characterizations of stationary equilibria for the class of stochastic games.

---

Share

Citation/Export:	Select format... Citation - Text Citation - HTML Endnote BibTex Dublin Core OpenURL MARC (ISO 2709) METS MODS EP3 XML Reference Manager Refer
Social Networking:	Share |

---

Details

Item Type:	University of Pittsburgh ETD
Status:	Unpublished
Creators/Authors:	Creators Email Pitt Username ORCID Dehghanian, Amin amd120@pitt.edu AMD120
ETD Committee:	Title Member Email Address Pitt Username ORCID Thesis Advisor Schaefer, Andrew J. schaefer@ie.pitt.edu SCHAEFER Committee Member Kharoufeh, Jeffrey P. jkharouf@pitt.edu JKHAROUF Committee Member Rajgopal, Jayant rajgopal@pitt.edu RAJGOPAL Committee Member Prokopyev, Oleg A. droleg@pitt.edu DROLEG Committee Member Akan, Mustafa akan@andrew.cmu.edu
Date:	11 September 2015
Date Type:	Publication
Defense Date:	6 July 2015
Approval Date:	11 September 2015
Submission Date:	18 July 2015
Access Restriction:	5 year -- Restrict access to University of Pittsburgh for a period of 5 years.
Number of Pages:	100
Institution:	University of Pittsburgh
Schools and Programs:	Swanson School of Engineering > Industrial Engineering
Degree:	PhD - Doctor of Philosophy
Thesis Type:	Doctoral Dissertation
Refereed:	Yes
Uncontrolled Keywords:	Kidney exchange, standard acquisition charge, pricing, bilevel programming, principal-agent models, stochastic stopping games, equilibrium selection, consensus decision-making, veto players, independence system, branch-and-cut, industrial organization
Date Deposited:	11 Sep 2015 18:10
Last Modified:	11 Sep 2020 05:15
URI:	http://d-scholarship.pitt.edu/id/eprint/25672

---

Metrics

Monthly Views for the past 3 years

Plum Analytics

---

Actions (login required)

View Item