서브메뉴
검색
Simple Policies in Dynamic Matching Markets
Simple Policies in Dynamic Matching Markets
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260202103626
- ISBN
- 9798286442645
- DDC
- 000
- 저자명
- Simon, Felipe.
- 서명/저자
- Simple Policies in Dynamic Matching Markets
- 발행사항
- [Sl] : University of Minnesota, 2025
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2025
- 형태사항
- 124 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 86-12, Section: A.
- 주기사항
- Advisor: Arnosti, Nick.
- 학위논문주기
- Thesis (Ph.D.)--University of Minnesota, 2025.
- 초록/해제
- 요약This thesis contains two self contained essays.The first essay studies a foundational model of dynamic matching market with abandonment. This model has been studied by Collina et al. (2020) and Aouad and Saritac (2022), and many other papers have considered special cases. The performance of greedy policies - which identify a set of "acceptable" matches up front, and perform these matches as soon as possible - is compared to that of an omniscient benchmark which knows the full arrival and departure sequence. A novel family of linear programs (PLP) is introduced to identify which greedy policy to follow. We show that the value of PLP is a lower bound on the value of the greedy policy that it identifies in two settings of interest:• The case where the everyone has the same departure rate.• The bipartite case where everyone on the same side of the market has the same departure rate.The proofs of these results use a new result (Lemma 1), which relates the probability that at least one agent from a set of types is present in the system to the expected number of such agents. We show that the value of PLP is at least 1/2 of the reward rate earned by the omniscient policy (Proposition 4). Therefore, for both settings above, the identified greedy policy provably earns at least half of the omniscient reward rate. This improves upon the bound of 1/8 from Collina et al. (2020). In both settings the competitive ratio of 1/2 is the best possible: no online policy can provide a better guarantee (Theorem 2).The second essay models the problem facing a policymaker who must allocate rapid rehousing support to people experiencing homelessness and wishes to minimize the steady-state size of the homeless population. Typically, support is given to the most vulnerable applicants, or to applicants most likely to remain housed. Although these approaches can be effective in some cases, in general they may result in a homeless population that is arbitrarily larger than what could be achieved by an optimal policy. We propose an alternative priority queue that is approximately optimal.We then study a family of policies where the policymaker does not differentiate between agents based on their characteristics. Within this family, FIFO queues best target the most vulnerable. If the most vulnerable households benefit most from housing assistance, then a FIFO queue minimizes the expected unhoused population. Conversely, a LIFO queue is optimal if the least vulnerable households benefit most from housing assistance.Finally, we expand our model to allow households to choose among several allocation systems. We show that even in this larger family of policies, if the most vulnerable households are also the ones that most benefit from housing assistance, a FIFO queue minimizes the expected unhoused population.
- 키워드
- Linear programs
- 기타저자
- University of Minnesota Industrial and Systems Engineering
- 기본자료저록
- Dissertations Abstracts International. 86-12A.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260126s2025 us c eng d■001000017357982
■00520260202103626
■006m o d
■007cr#unu||||||||
■020 ▼a9798286442645
■035 ▼a(MiAaPQ)AAI32046472
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a000
■1001 ▼aSimon, Felipe.
■24510▼aSimple Policies in Dynamic Matching Markets
■260 ▼a[Sl]▼bUniversity of Minnesota▼c2025
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2025
■300 ▼a124 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 86-12, Section: A.
■500 ▼aAdvisor: Arnosti, Nick.
■5021 ▼aThesis (Ph.D.)--University of Minnesota, 2025.
■520 ▼aThis thesis contains two self contained essays.The first essay studies a foundational model of dynamic matching market with abandonment. This model has been studied by Collina et al. (2020) and Aouad and Saritac (2022), and many other papers have considered special cases. The performance of greedy policies - which identify a set of "acceptable" matches up front, and perform these matches as soon as possible - is compared to that of an omniscient benchmark which knows the full arrival and departure sequence. A novel family of linear programs (PLP) is introduced to identify which greedy policy to follow. We show that the value of PLP is a lower bound on the value of the greedy policy that it identifies in two settings of interest:• The case where the everyone has the same departure rate.• The bipartite case where everyone on the same side of the market has the same departure rate.The proofs of these results use a new result (Lemma 1), which relates the probability that at least one agent from a set of types is present in the system to the expected number of such agents. We show that the value of PLP is at least 1/2 of the reward rate earned by the omniscient policy (Proposition 4). Therefore, for both settings above, the identified greedy policy provably earns at least half of the omniscient reward rate. This improves upon the bound of 1/8 from Collina et al. (2020). In both settings the competitive ratio of 1/2 is the best possible: no online policy can provide a better guarantee (Theorem 2).The second essay models the problem facing a policymaker who must allocate rapid rehousing support to people experiencing homelessness and wishes to minimize the steady-state size of the homeless population. Typically, support is given to the most vulnerable applicants, or to applicants most likely to remain housed. Although these approaches can be effective in some cases, in general they may result in a homeless population that is arbitrarily larger than what could be achieved by an optimal policy. We propose an alternative priority queue that is approximately optimal.We then study a family of policies where the policymaker does not differentiate between agents based on their characteristics. Within this family, FIFO queues best target the most vulnerable. If the most vulnerable households benefit most from housing assistance, then a FIFO queue minimizes the expected unhoused population. Conversely, a LIFO queue is optimal if the least vulnerable households benefit most from housing assistance.Finally, we expand our model to allow households to choose among several allocation systems. We show that even in this larger family of policies, if the most vulnerable households are also the ones that most benefit from housing assistance, a FIFO queue minimizes the expected unhoused population.
■590 ▼aSchool code: 0130.
■653 ▼aDynamic matching market
■653 ▼aLinear programs
■653 ▼aUnhoused population
■690 ▼a0796
■690 ▼a0501
■71020▼aUniversity of Minnesota▼bIndustrial and Systems Engineering.
■7730 ▼tDissertations Abstracts International▼g86-12A.
■790 ▼a0130
■791 ▼aPh.D.
■792 ▼a2025
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17357982▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
