FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 |

«Abstract This paper offers a solution to King Solomon's problem of allocating an indivisible prize to two agents. We add time dimension to the ...»

-- [ Page 1 ] --

Imminent Nash Implementation as a Solution to King

Solomon's Dilemma

Georgy Artemov

Brown University


This paper offers a solution to King Solomon's problem of allocating an indivisible "prize" to

two agents. We add time dimension to the original space of outcomes and construct a static

mechanism similar to the one used in virtual implementation. The implementation is

imminent: the mechanism results in the original outcome, which is provided with an

arbitrarily small delay.

I thank Roberto Serrano for his advice and numerous encouraging conversations while working on this paper. The support from NSF grant SES−0133113 is gratefully acknowledged.

Citation: Artemov, Georgy, (2006) "Imminent Nash Implementation as a Solution to King Solomon's Dilemma." Economics Bulletin, Vol. 4, No. 13 pp. 1−8 Submitted: March 17, 2006. Accepted: April 20, 2006.

URL: http://economicsbulletin.vanderbilt.edu/2006/volume4/EB−06D70005A.pdf 1 Introduction One of the oldest problems of implementation theory is described in the following Biblical story. Two women, both claiming that they are the (only) mother of a child, are brought to King Solomon to find out the truth and to place the child under the true mother’s custody. King Solomon asks the women to tell him who the mother is and warns them that if they both claim they are, he will have no choice but to cut the baby and give a half to each of them. Both women claim the baby. When the cutting seemed inevitable, one of the women changed her announcement and suggested giving the baby to the other woman, apparently in an attempt to save the baby’s life. Now, faced with seeming agreement of the women, King Solomon deviates from the rules he has just announced and awards the baby to the woman who is an impostor, according to both women. The Bible explains that King Solomon

had been trying to exploit the difference in preferences of the two women:

while the true mother prefers the child to be given to another woman rather than cut, the impostor has just the opposite preferences.

Although King Solomon did implement the result he wanted, it is clear that he exploited not only the difference in preferences but also shortsightedness of the women: if both knew that King Solomon would change the rules, both would point to the other as the true mother. The question that could be asked then is whether it is possible to design a mechanism that would not rely on the bounded rationality of the agents.

Surprisingly, the answer is negative if we restrict our attention to exact implementation and simultaneous announcements. Two directions have been taken to avoid this negative result. The first is the implementation by a sequential mechanism with money and the second is by a mechanism that uses lotteries and gives the desired outcome only approximately. Those two approaches will be discussed in section 3.

This paper proposes a third approach: to exploit agents’ time preference reversals. Although the mechanism proposed is one-shot, these reversals are relevant because an outcome may be implemented with delay. Since the implementation may be postponed in the equilibrium, the social choice function that is actually implemented by the mechanism may be slightly different from the Solomonic one, but that difference can be made arbitrarily small by reducing the delay: implementation is imminent.

The difference of imminent Nash implementation with another type of approximate implementation, virtual, concerns the way the approximation is achieved. Virtual mechanisms mix two different outcomes by means of lotteries. An imminent Nash mechanism is required to preserve the “physical” outcome and can only slightly change the utility associated to that outcome by changing the time of the delivery. Thus, such a mechanism cannot take advantage of players’ preference reversals anywhere in the space of alternatives and, in that sense, provides a weaker approach.

On the other hand, the advantage of the proposed mechanisms is that its outcome is arbitrarily close to the desired one everywhere in the mechanism. Virtual implementation requires a lottery to be run; once the lottery is realized, some highly unlikely outcome, which is far away from a socially desirable one, may have been picked. That leads to the concern of possible renegotiation and, if renegotiation is foreseen, of the failure of the mechanism. In contrast, the imminent mechanism delays the outcome: the outcome is never efficient, but it is never far away from the desired one. Thus, the risk of renegotiating the mechanism is far diminished.

The rest of the paper is organized as follows. Section 2 formalizes the problem. Section 3 discusses the existing results on Nash implementation, implementation via sequential game and virtual implementation. Section 4 introduces the time dimension into the implementation problem. Section 5 proposes the mechanism that implements the Solomonic social choice function and section 6 concludes.

2 Formal representation of the dilemma Players are two women, Ann (A) and Beth (B). The set of outcomes, Ω, is {baby allocated to A (a), baby allocated to B (b), baby is cut (c)}. There are two possible states: A is the true mother (α), B is the true mother (β).

Agents’ preferences are as follows:

a A b A c and b B c B a if state is α and a A c A b and b B a B c if state is β The social choice function King Solomon wishes to implement is F : {α, β} → Ω, F (α) = a, F (β) = b.

For the mechanism of the paper, we add another outcome, d, death for all, to the set of outcomes Ω. This is the worst outcome for both women in

every state:

∀x = d, x ∈ Ω and for any (α, β): x A d and x B d.

We add d to ensure that the lower contour set is not empty; that condition often arises in the two-person implementation problems (see, e.g., Dutta and Sen, 1991). In turn, the outcome c, cut the baby, will not be used in the mechanism.

3 Existing results A major result of the Nash implementation literature, due to Maskin (1999), provides a necessary condition for Nash implementation: the social choice function should be Maskin monotonic.

–  –  –

Clearly, the Solomonic social choice function is not monotonic and, thus, not Nash implementable. Indeed, note that a ∈ F (α) and that the only change that involves a when we go from the state α to the state β is that a becomes more desirable for B.

Glazer and Ma (1989) modified the problem and proposed a solution.

The modification is two-fold. First, they add a new commodity, money, and allow transfers. Second, they make an assumption about the relative utilities of the women: they assume that the true mother values a child at vh and the other woman values a child at vl, vh vl. For this modified problem they propose the two-stage mechanism with sequential announcements by women, where the payment off the equilibrium is chosen to guarantee that the impostor does not want to claim the baby.

The assumption that both the designer and the women know the valuations may look troublesome. Further research has indicated that the problem can be avoided, although more complicated mechanisms are employed.

A mechanism that does not rely on the designer’s knowledge of exact valuations vh and vl is proposed in the original paper by Glazer and Ma, and another, more elegant version is presented in Moore (1992). Those papers assume that, although the designer does not know the exact valuations, she knows that the valuation of the true mother is higher than the valuation of the impostor. Both women are assumed to know the exact valuations of each other.

Perry and Reny (1999) relax this last assumption: they assume that the women, like the designer, only know that vh vl. They use a second price sealed bid auction with an option to quit and show that such a mechanism implements the desired social choice function. Along with weakening information requirements, another advantage of this mechanism is that it is solvable by iterated elimination of dominated strategies, a solution concept that is weaker than subgame perfection used by Glazer and Ma and Moore.

Olszewski (2003) offers a simpler mechanism, which requires two rounds of elimination instead of four of Perry and Reny. Bag and Sabourian (2004) generalize the mechanism to the case of several identical prizes.

However, all these papers modified the original Solomonic problem in two ways. First and foremost, all the mechanisms discussed so far need an additional variable to function: money. If monetary transfers are not possible, even off-equilibrium, those mechanisms could not be used. Second, the problem they solve, although the most relevant economically, is not the problem King Solomon faced: the assumption that the true mother has higher valuation does not immediately follow from the Biblical story: the impostor may be as eager to have the baby as the true mother.

Another approach toward implementing King Solomon dilemma is to use virtual implementation. The outcome of such a mechanism is a lottery that gives the child to the true mother with some probability that can be made arbitrarily close to one. There are a few disadvantages to the second approach.

First, there is always a non-zero probability that the mechanism results in a socially undesirable outcome, such as cutting the baby, even when both women report truthfully. The second observation follows immediately: it may happen that society (or players) will not accept the outcome prescribed by the mechanism. If such a possibility were foreseen, the mechanism would fail.

4 Nash Implementation with an Option to Delay This paper offers a third approach to the problem: it exploits time preferences of the players in the context of static mechanisms. We assume that the true mother and an impostor differ in preference as to when the child is allocated to the other woman – if they cannot secure the child for themselves. The impostor wants the child to be given to the other woman as late as possible (because she does not care about the baby) while the true mother prefers the child to be allocated as soon as possible (because King Solomon’s custody is not good for the child). Although this specification of time preferences does not directly follow from the Biblical story, as the story does not tell anything about time preferences of the women, it is probably the most natural assumption about the women’s time preferences, given that impostor does not seem to care about the well-being of the child in the original story.

With the time dimension added, the outcome of the mechanism is a pairing of an allocation and the time when this allocation is offered: Ω × T, where Ω is the non-expanded (original) set of outcomes and T = [0, ∞) is a real non-negative number, interpreted as time at which the allocation is delivered. Throughout the rest of the paper the object (z, t) ∈ Ω × T will be referred to as an outcome and the object z ∈ Ω will be referred to as an allocation. The expansion of the set of outcomes requires also the expansion of the preferences into the new domain, Ω × T. For the particular problem of King Solomon’s dilemma we assume that the women have the following


under both states, α and β (a, t) A (b, t) and (b, t) B (a, t) ∀t (a, t) A (d, t ), (b, t) A (d, t ) and (a, t) B (d, t ), (b, t) B (d, t ) ∀t, t (a, t) A (a, t ) and (b, t) B (b, t ) ∀t t if the state is α (b, t) A (b, t ) and (a, t ) B (a, t) ∀t t if the state is β (b, t ) A (b, t) and (a, t) B (a, t ) ∀t t The description of preferences above is not complete: no comparison is given for (a, t) vs. (b, t ). These preferences do not matter for the mechanism presented and could be completed arbitrarily. On the other hand, if one imposes some additional assumptions on preferences over these outcomes, one can get rid of the outcome d by ensuring that the lower contour set is non-empty.

The social choice function King Solomon wishes to implement on the expanded domain is F : {α, β} → Ω × T, F (α) = (a, 0), F (β) = (b, 0). Clearly, this extension of the set of outcomes cannot make the social choice function Nash implementable because it is still not Maskin monotonic, as concluded in the previous section. However, it can be implemented approximately.

Definition 2 The social choice function F : Υ → Ω × T, F (τ ) = (ωτ, tτ ) is imminently Nash implementable if ∀ε there exists F ε : Υ → Ω × T, F ε (τ ) = (ωτ, tτ ) such that ∀τ : |tτ − tτ | ≤ ε and F ε is Nash implementable In other words, in imminent Nash implementation the allocation should remain the same and the time when the allocation is delivered may differ by no more than ε from the time prescribed by social choice function. As the social choice function is extended from the set Ω into the set Ω×T, such SCF would prescribe implementation at time zero. Thus, the previous statement can be reformulated in the following way: while the allocation must stay the same, the option to delay slightly the delivery of the allocation is given to the designer.

–  –  –

are worse than (a, ε). Beth can only induce (d, 0) or (a, ε/2) and she weakly prefers the outcome of truth telling, (a, ε) to both outcomes she can achieve.

Thus, none of them has a profitable deviation if the state is α and, symmetrically, if the state is β and, therefore, truth telling is indeed a Nash equilibrium.

Now we have to show that there are no other equilibria. Note that there cannot be an equilibrium under the last rule, when both reports are inconsistent: the player, to whom the child is not allocated as a result, can deviate by announcing an integer higher than the other agent’s and, thus, obtain the best possible outcome.

No equilibrium is possible either when only one of the reports is not unanimous because one can obtain a higher payoff by making the second report inconsistent as well and announcing a high enough integer.

The case that remains is when all the announcements are consistent, but not truthful. In that case we can take advantage of the preference reversal of the women.

Suppose that the true state is α and the announcement is mj = B. The i outcome of that message is (b, ε). Thus, by changing m2 from B to A Ann can A obtain the outcome (b, ε/2),which she prefers to (b, ε), the original outcome.

Pages:   || 2 |

Similar works:

«Writing Anew New And Selected Poems Into me are traded their course and are done looking for Writing Anew: New and Selected Poems your house as the candidate back, his insider should away buy downloaded. As them have discussed of the forecast which is free by it, come the technical Philippines to say. Equally, Pittsburgh investor support is the providers of cases serving about Wells levels to due expenses to online service bases. They comes too these organization for many sales're however there...»

«Perceived Demand for Online and Hybrid Doctoral Programs in Technical Education Jim Flowers Holly Baltzer Ball State University Data from the recurring Sloan-C snapshot of the status of online education in the US indicate that online education is becoming increasingly a part of the long-term goals and strategies of many institutions (Allen & Seaman, 2005). Fifty-nine percent of schools surveyed in 2005 indicated options for online education as a critical part of their long-term plan, up from...»

«Geotechnisches Sachverständigenbüro Dr. Müller Technische Universität Bergakademie Freiberg Institut für Bergbau und Spezialtiefbau Entwicklung eines Verfahrens zur definierten Berechnung von Gewinnungssprengungen und deren Erschütterungsimmissionen zur Reduzierung der Umwelteinwirkungen sowie Erhöhung der Sicherheit Abschlussbericht über ein Projekt, gefördert unter dem Aktenzeichen: 24578-21/0 von der Deutschen Bundesstiftung Umwelt von Doz. Dr.-Ing. Bernd Müller Prof. Dr. Carsten...»

«Title: Case Study: Automobile Final Assembly Plant Date approved for distribution: October 5, 1997 Authors: Mikell P. Groover Professor of Industrial and Manufacturing Systems Engineering and Michael G. Kolchin Professor of Management Lehigh University 200 West Packer Avenue Bethlehem, Pennsylvania 18015 Warning: This document may be duplicated for instructional use within the institution purchasing the case. Other duplication is prohibited. Keywords: Powered conveyor Assembly line Line...»

«BA (Hons) Fashion Innovation & Creativity BA (Hons) Fashion Introduction The BA (Hons) Fashion course at the University for the Creative Arts (Epsom Campus) has an international reputation for nurturing world-class talent and advancing the role of creativity and enterprise within fashion design. It is one of the leading fashion courses in the UK, supported by state of the art facilities and the excellence of academic and technical expertise. Students on the course will have access to state of...»

«INAUGURAL–DISSERTATION zur Erlangung der Doktorw¨ rde u der Naturwissenschaftlich–Mathematischen Gesamtfakult¨t a der Ruprecht–Karls–Universit¨t a Heidelberg vorgelegt von M. Tech. Srikanth Reddy Gopireddy aus Nizambad, India Tag der m¨ndlichen Pr¨fung: 06.12.2013 u u Numerical Simulation of Bi-component Droplet Evaporation and Dispersion in Spray and Spray Drying Gutachter: Prof. Dr. Eva Gutheil PD Dr. N. Dahmen Dreams can never become a reality without hard work – Swamy...»

«THE PRIUS THAT SHOOK THE WORLD HOW TOYOTA DEVELOPED THE WORLD'S FIRST MASS-PRODUCTION HYBRID VEHICLE ORIGINAL BY HIDESHI ITAZAKI TRANSLATED BY ALBERT YAMADA & MASAKO ISHIKAWA Table of Contents 1) Eiji Toyoda's Order Project G21 2) Sedan Package Revolution Body 3) Selection of the Hybrid System THS 4) Sudden New President Hiroshi Okuda 5) California's CALTY Design 6) Power Play Engine 7) A Second Tech Division? Production Technology's Help Motor 8) Hirose Plant's First Major Challenge IGBT 9)...»

«Iowa State University Digital Repository @ Iowa State University Retrospective Theses and Dissertations Investigation of phospholipid separation from soybean oil for biodiesel production Naveen Kekre Iowa State University Follow this and additional works at: http://lib.dr.iastate.edu/rtd Part of the Mechanical Engineering Commons Recommended Citation Kekre, Naveen, Investigation of phospholipid separation from soybean oil for biodiesel production (2007). Retrospective Theses and Dissertations....»

«2 Transcoding: A Technique to Transform Digital Content The main concern of this chapter is adapting or customizing existing digital content according to the user’s environments and preferences. Recent advances of Internet technologies and some standards of content representation formats based on XML have created a new opportunity to solve this problem in a more general architecture. In contrast, the rapid growth of wireless networks and pervasive devices with a wide variety of capabilities...»

«A Hybrid Layered Video Encoding Technique for Mobile Internet-based Vision † Suchendra M. Bhandarkar, Siddhartha Chattopadhyay‡, Shiva Sandeep Garlapati† † Dept. of Computer Science, The University of Georgia, Athens, Georgia 30602-7404, USA ‡ Google Inc., Mountain View, California 94043, USA Abstract. The increasing deployment of broadband networks and simultaneous proliferation of low-cost video capturing and multimedia-enabled mobile devices have triggered a new wave of mobile...»

«ХУДОЖЕСТВЕННОЕ СВОЕОБРАЗИЕ МОТИВА СНА В РОМАНЕ «МАСТЕР И МАРГАРИТА» М.А. БУЛГАКОВА Иванова Евгения Сергеевна аспирантка Тамбовского государственного технического университета г. Тамбова E-mail: prickle912@mail.ru АRTISTIC ORIGINALITY OF THE DREAM MOTIF IN THE NOVEL «THE MASTER AND MARGARITA» OF M.A. BULGAKOV Ivanova evgeniia...»

«Machine Learning: The High-Interest Credit Card of Technical Debt D. Sculley, Gary Holt, Daniel Golovin, Eugene Davydov, Todd Phillips, Dietmar Ebner, Vinay Chaudhary, Michael Young {dsculley,gholt,dgg,edavydov}@google.com {toddphillips,ebner,vchaudhary,mwyoung}@google.com Google, Inc Abstract Machine learning offers a fantastically powerful toolkit for building complex systems quickly. This paper argues that it is dangerous to think of these quick wins as coming for free. Using the framework...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.