부럽지 않은 매칭

경제사회선택론에서 질투 없는 매칭(EFM)은 사람과 사람 사이의 매칭으로, 자신의 '무엇'을 다른 사람의 것과 바꾸려 하지 않는다는 점에서 부러움이 없는 것이다.이 용어는 여러 가지 다른 맥락에서 사용되어 왔다.

가중치가 없는 초당적 그래프

가중치가 없는 초당적 그래프 G = (X+Y, E)^[1]에서 질투 없는 일치는 X에서 일치하지 않는 정점이 Y에서 일치하는 정점에 인접하지 않는 일치를 의미한다.X의 정점이 사람을 나타내고, Y의 정점이 집을 나타내며, 사람 x와 집 y 사이의 가장자리가 x가 y에 살 의향이 있다는 사실을 나타낸다고 가정하자.그렇다면 EFM은 무주택자 각자가 주택이 있는 사람을 부러워하지 않도록 주택의 일부분배분을 하는 것이다.

X를 포화시킨 매칭마다 부러움이 없고, 빈 매칭마다 부러움이 없다.더욱이 N_G(X) ≥ X 1 1 (여기서_G N(X)은 Y의 X의 이웃집 집합)이라면 G는 비어 있지 않은 EFM을 인정한다.^[1]이것은 홀의 결혼 조건의 완화인데, 만약 X의 서브셋 X마다_G N(X') ≥ X'가 존재한다면, X 포화 매칭이 존재한다는 것이다.

돈이 있는 시장에서.

여러 구매자와 여러 상품이 있고 각각의 상품에 가격이 있을 수 있는 시장을 생각해 보라.가격 결정자가 주어진 경우, 각 구매자는 수요 집합 즉, 모든 번들에 대해 구매자의 효용을 극대화하는 번들 집합이 있다(이 집합은 구매자가 모든 번들을 너무 비싸다고 생각할 경우 빈 번들을 포함할 수 있다).

가격-인식 매칭(가격-벡터 부여)은 각 에이전트가 자신의 요구 집합으로부터 묶음을 받는 매칭이다.같은 가격의 다른 보따리를 받고 싶어 하는 대리인은 없을 것이라는 뜻이다.^[2]이 설정의 예로는 임대 조화 문제 - 각 객실에 가격을 책정하면서 임차인(대리인)과 객실(품목)을 매칭하는 것이다.

부러움 없는 가격은 부러움 없는 매치가 존재하는 가격 벡터다.월라시안 평형 완화다. 월라시안 평형은 EF 가격과 EF 매칭으로 구성되며, 게다가 모든 품목이 일치하거나 영가격을 가져야 한다.월라스 평형에서는 매칭이 값의 합을 최대화하여, 즉 최대 중량 매칭이라고 알려져 있다.그러나 판매자의 수익은 낮을 수도 있다.이는 판매자가 수익을 증가시키기 위해 예비 가격을 사용할 수 있는 EF 가격 결정의 완화에 동기를 부여한다. 자세한 내용은 질투 없는 가격을 참조하십시오.

돈이 없는 시장에서.

질투 없는 매칭이라는 용어는 종종 더 약한 조건, 즉 정당화되지 않은 매칭을 나타내기 위해 사용된다.

케이크 커팅에서

부러움 없는 매칭이라는 용어는 시샘 없는 케이크 커팅의 효율성을 높이기 위한 알고리즘이라는 다른 맥락에서 사용되기도 했다.^[3]

참고 항목

• 부러움 없는 아이템 할당
• 렌탈하모니
• 주택 할당 문제

참조