[논문]게임이론과 네트워크의 만남

모정훈; 박광우; 김태현

게임이론과 네트워크의 만남 원문보기

정보와 통신 : 한국통신학회지 = Information & communications magazine, v.26 no.7, 2009년, pp.17 - 23

모정훈 (연세대학교) , 박광우 (연세대학교) , 김태현 (연세대학교)

초록
AI-Helper

최근 네트워크에서의 많은 문제가 게임이론을 이용하여 정형화되고 있다. 기본적으로 분산시스템인 인터넷의 활성화, 스스로 망을 조직화하는 무선시스템의 개발로 인하여 다수의 의사결정자가 필요한 게임이론이 적용될 수 있는 영역이 확대된 결과이다. 본 고에서는 게임이론이 네트워크의 다양한 문제에 어떻게 적용되었는지를 다룬다.

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

He는 渺]에서 여러명의 인터넷 서비스 사업자중 병목에 해당하는 사업자의 매출이 많다는 것을 보이고 이러한 이유 때문에 병목 사업자가 망을 업그레이드 할 이유가 적다는 것을 보였다. 그리고 그러한 문제를 해결하기 위한 방법을 제안하였다.
본 논문에서는 게임이론이 유무선 네트워크의 자원할당문제 그리고 과금문제에 어떻게 적용되었는지에 관하여 다룬다. 일단 2절에서는 게임이론의 가장 기본적인 개념에 대하여 설명하겠다.
본고에서는 게임 이론의 기본개념과 네트워크에 적용된 다양한 사례를 살펴보았다. 게임이론은 이미 혼잡제어, 라우팅, 무선망, 과금, 그리고 인터넷 보안등의 다양한문제에 사용되고 있다.

가설 설정

라우팅 게임의 기본 가정은 각 사용자가 자신의경로를 결정한다는 것이다. 이러한 경우에 본인의 비용을 최소화시키려고 한다면 이러한 이기심이 어떠한 결과를 발생시킬 것인가가 라우팅 게임의 연구대상이다.

제안 방법

[6]에서는 사용자의 효용함수가 수율(throughput)인 경우에 지연시간에 대한 제약을 둔 모델을 연구하였다. [기은효용함수를 수율과 지연시간의 비율인 파워라는 개념을 도입하여 사용하였다. [81 에서는 이러한 혼잡제어 문제를 동적인 환경 에서 고찰하였다
回에서 저자는 매우 일반적인 비용함수에 대하여 내쉬 균형점이 존재하고 유일하다는 것을 보였다. 그리고 균형점에 도달하는 방법을 제시하였다. 하지만 네트워크의 토폴로지가 일반화되는 경우엔 이러한 유일성이 보장되지 않는다.
Odlyzko는 망을 여러 개의 논리적으로 구분하고 각 서비스의 과금을 차별화 함으로서 사용자의 서비스품질을 차별화하는 방법을 제안한 것이다. 기술적으로 서비스 품질을 차별화하는 것이 아니라 과금을 이용한 품질차별화를 제안하였다. 망사업자는 매출을 최대화할 수 있는 차별화된 가격을 선정할 수 있다.
침입자의 경우 침입경로를 선택하고 망 관리자는 침입자를 어떻게 찾을 것인가의 샘플링 전략을 선택하였을 때를 게임으로 모델 하였다.

참고문헌 (30)

T. Roughgarden and E. Tardos, 'How Bad is Selfish Routing?' , JACM '02

상세보기
김영세, 게임이론 전략과 정보의 경제학, 제3판, pp.1-2.2007.3
박주현, 게임이론의 이해 제2판, pp12-13, 81-82,2001.3
D. Fudenberg and J. Tirole, Game Theory, MIT Press, Cambridge (MA), 1991
F.P.Kelly, 'Charging and rate control for elastic traffic,' European Trans. on Telecommunications, 8(1): 33-37, 1996
Korilis Ya, Lazar A. 'On the existence of equilibria in noncooperative optimal flow control.' Journal of the ACM 1995;42(3):584-613

상세보기
Mazumdar R, Mason L, Douligeris C. 'Fairness in network optimal flow control: ptimality of product forms.' IEEE Transactions on Communications 1991;39(5):775-82

상세보기
Hsiao mt, Lazar aa. 'Optimal decentralized flow control of Markovian queueing networks with multiple controllers.' Performance Evaluation 1991;13:181-204

상세보기
A. Orda, R. Rom and N. Shirnkin, 'Competitive routing in multiuser communication networks,' IEEE/ACM Transactions on Networking, 1 (5) 1993

상세보기
Altman E, Kameda H. 'Equilibria for multidass routing problems in multi-agent networks.' In: 40th IEEE Conference on Decision and Control. Orlando, Florida, USA, December 2001
T. Roughgarden, 'Selfish routing with atomic players,' ACM/SIAM Symp. on Discrete Algorithms (SODA) 2005
J. MacKie-Mason, J.K., H. Varian, 'pricing congestible network resources,' IEEE Journal on Selected Areas in Communications, Vol. 13(7), pp. 1141-1149, 1995

상세보기
A. B. MacKenzie and S. B. Wicker, 'Game theory in communications: Motivation, explanation, and application to power control,' in Proceedings of IEEE GLOBECOM, 2001, pp. 821-826
V. Shah, N. B. Mandayam, and D. J. Goodman, 'power control for wireless data based on utility and pricing,' in Proceedings of the 9th IEEE International Symposium on Personal,Indoor and Mobile Radio Communications, September 1998, pp. 1427-1432
A. B. MacKenzie and S. B. Wicker, 'Stability of multipacket slotted aloha with selHsh users and perfect information,' in Proceedings of IEEE INFOCOM, April 2001
Z. Han and K. J. Ray Liu, 'Noncooperative powercontrol game and throughput game over wireless networks' , IEEE Trans. on Commun., vol. 53, no. 10, pp.1625-1629, Oct. 2005

상세보기
W. Teerapabkajorndet and P. Krishnamurthy, 'A reverse link power control algorithm based on game theory for multi-cell wireless data networks' , in Proc. GLOBECOM, 2004, pp.459-468
M. Felegyhazi, J. Hubaux, 'Game Theory in Wireless Networks: Tutorial,' EPFL Technical Report, 2006
C. W. Sung and W. S. Wong, ' A noncooperative power control game for multirate CDMA data networks' , IEEE Trans. on Wireless Commun., vol. 2, no. 1, pp.186-194, Jan. 2003

상세보기
A. OJlyzko, 'paris Metro Pricing for the Internet,' ACM Conference on Electronic Commerce, 1998
Jean Walrand, 'Economic Models of Communication Networks, Performance Modeling and Engineering,' page 57-89, 2008
D. Acemouglu, A. Ozdaglar, 'Competition and Efficiency in Congested Markets,' Mathematics of Operations Research, vol. 32, no. 1, pp. 1-31, February 2007

상세보기
J. Mussacchio, J. Walrand, 'WiFi access point pricing as a dynamic game' , IEEE/ACM Transactions on Networking, Vol. 14(2), 2006

상세보기
L. Huang MJ. Neely, 'The Optimality of Two Prices: Maximizing Revenue in Stochastic Network,' Proc. of the 45th Allerton Conference, 2007
S. Yang, B. Hajek, 'VCG-Kelly mechanisms for allocation of divisible goods: Adapting VCG mechanisms to one-dimensional signals,' IEEE JSAC (Issue on non cooperative behavior in networks) , vol. 25, pp. 1237-1243, 2007
R. Jain, 'An Efficient Nash-Implementation Mechanism for Allocating Atbitrary Bunclles of Divisible Resources,' IEEE JSAC, 2007
R. Johari and J. N. Tsitsiklis, 'Efficiency loss in a resource allocation game,' Mathematics of Operatiom Research, 29(3): 407-435, 2004

상세보기
L. Jiang, V. Anantharam, and J. Walrand, 'Efficiency of selfish investment in network security,' preprint,2008; http://robotics.eecs.berkeley.edu'wlr/Papers/libinsecurity.pdf
T.V. Lakshman, M. Kodialam. 'Detecting network intrusiom via sampling: a game theoretic approach.' In: IEEE INFOCOM. San Francisco, California, USA, 2003
E. Altman, 'A survey on networking games in telecommunications, Computers and Operations Research,' Vol 33, pages: 286 - 311, Issue 2, Feb 2006

상세보기

저자의 다른 논문 :

LOADING...

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증