סוג האירוע

בחר הכל

הרצאות פומביות

מבחן/תחרות

סמינרים

קולוקוויום

כנסים וימי עיון

צהרי יום א'

ימים פתוחים וייעוץ

טקסים ואירועים מיוחדים

הרצאות לקהל הרחב

מועדון קשרי אקדמיה-תעשייה

תחום האירוע

בחר הכל

הפקולטה למדעים מדויקים

ביה"ס למדעי המתמטיקה

ביה"ס לפיזיקה ולאסטרונומיה

המועדון האסטרונומי

ביה"ס לכימיה

מרכז לחקר אינטראקציות אור חומר

סימפוזיונים והרצאות מיוחדות

החוג למדעי כדור הארץ

ביה"ס למדעי המחשב

ביה"ס למדעי כדור הארץ

קולוקוויום בביה"ס למדעי המחשב - Incentive Compatible Mechanisms for the Secretary Problem

Ilan Adler

20 בדצמבר 2018, 13:00 
בניין שרייבר, חדר 309 
קולוקוויום במדעי המחשב

In the classical secretary problem, an employer sequentially interviews n randomly ordered rankable candidates; following each interview, the employer must immediately decide whether to hire the candidate. The celebrated elegant solution that maximizes the probability of hiring the best candidate calls for ignoring about one third of the first interviewed candidates and then selecting the best candidate so far. Recognizing that the early candidates have no chance to be selected, and thus have no incentive to be interviewed, Buchbinder, Jain and Singh introduced an LP based selection mechanism that guarantees that all candidates have an equal probability of being selected. In this talk we introduce a tighter LP formulation whose dual is the direct formulation of the incentive problem as a Markov Decision Problem. This approach provides a clear insight into the LP formulation, simplifies the proofs of their validity, and provides a general framework for other incentive mechanisms. In particular, we present and analyze an incentive mechanism that maximizes the expected rank of the selected candidate. In addition, we introduce a couple of novel mechanisms that allow the candidates to set deadlines for accepting hiring offers. We show that these mechanisms guarantee equal probability of being selected for all the candidates that are interviewed, while the probability of selecting the best candidate is higher than that of the classical problem (though both converge - as n tends to ∞ - to the same value).‏

אוניברסיטת תל-אביב, ת.ד. 39040, תל-אביב 6997801
UI/UX Basch_Interactive