Misplaced Pages

#267732

37-581: The abbreviation NEIC may refer to: Nash equilibrium incentive compatibility, see Myerson–Satterthwaite theorem § Requirements National Earthquake Information Center Navy Expeditionary Intelligence Command , a component of Navy Expeditionary Combat Command Nigerian National Economic Intelligence Committee, see Garba Ali Mohammed Nordic e-Infrastructure Collaboration, see Advanced Resource Connector § Nordic DataGrid Facility and NeIC Northeast Illinois Council , an administrative district of

74-439: A double auction is stock exchange . As well as their direct interest, double auctions are reminiscent of Walrasian auction and have been used as a tool to study the determination of prices in ordinary markets. A double auction is also possible without any exchange of currency in barter trade . A barter double auction is an auction where every participant has a demand and an offer consisting of multiple attributes and no money

111-560: A joint misreport of their preferences). The basic double auction model involves two categories of traders: buyers and sellers. Babaioff and Nisan extended it to handle a supply chain - a chain of markets, in which the buyers in one market become sellers in the next market. E.g., farmers sell fruits in the fruit market; juice makers buy fruits in the fruit market, make juice and sell it in the juice market to consumers. Babaioff and Walsh extended it to handle markets in an arbitrary directed acyclic graph . Gilor, Gonen and Segal-Halevi study

148-455: A multilateral market, with a set G of agent categories. he market is characterized by an integer vector r of size | G |, called the recipe of the market. Each trade in the market involves r g agents of category g , for each g in G . The standard double auction market is a special case in which there are two categories (buyers and sellers), and the recipe is r =(1,1). They present algorithms that are SBB, IC, IR and attain (1-1/ k ) of

185-415: A risk-neutral trader cannot gain in expectation by misreporting his value, but after he knows the results of the lot, he might feel regret for not reporting otherwise. Segal-Halevi, Hassidim and Aumann present a trade-reduction mechanism that is SBB, in addition to being IR and IC and attains (1-1/k) of the optimal GFT. Babaioff and Nisan provide both a theoretic comparison and an empirical comparison of

222-413: Is an equilibrium when both players' bids are some linear functions of their valuations. It is also brings higher expected gains for the players than any other Bayesian Nash equilibrium (see Myerson–Satterthwaite theorem ). How should the auctioneer determine the trading price? An ideal mechanism would satisfy the following properties: 1. Individual Rationality (IR): no person should lose from joining

259-422: Is an excess supply. When B < S , any price in the range ( B , S ) is an equilibrium price, since both the supply and the demand equal 0 (the price is too high for the buyer and too low for the seller). In a more general double auction, in which there are many sellers each of whom holds a single unit and many buyers each of whom wants a single unit, an equilibrium price can be found using the natural ordering of

296-442: Is different from Wikidata All article disambiguation pages All disambiguation pages Myerson%E2%80%93Satterthwaite theorem#Requirements The Myerson–Satterthwaite theorem is among the most remarkable and universally applicable negative results in economics—a kind of negative mirror to the fundamental theorems of welfare economics . It is, however, much less famous than those results or Arrow's earlier result on

333-411: Is involved. For the mathematical modelling of satisfaction level Euclidean distance is used, where the offer and demand are treated as vectors. A simple example of a double auction is a bilateral trade scenario, in which there is a single seller who values his product as S (e.g. the cost of producing the product), and a single buyer who values that product as B . From an economist's perspective,

370-486: The Myerson-Satterthwaite theorem . Babaioff, Nisan and Pavlov generalised the trade reduction mechanism to a market that is spatially-distributed , i.e. the buyers and sellers are in several different locations, and some units of the good may have to be transported between these locations. The cost of transport is thus added to the cost of production of the sellers. McAfee presented the following variation on

407-513: The Trade reduction mechanism with probability p and the VCG mechanism with probability 1- p . This mechanism inherits all the properties of its parents, i.e. it is IR and IC. The parameter p controls the tradeoff between EE and BB: In a variant of this mechanism, after the bids are submitted, the k -1 cheap sellers trade with the k -1 expensive buyers; each of them receives/pays the expected payment of

SECTION 10

#1732852377268

444-539: The Boy Scouts of America Northeast Iowa Conference Topics referred to by the same term [REDACTED] This disambiguation page lists articles associated with the title NEIC . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=NEIC&oldid=1042640679 " Category : Disambiguation pages Hidden categories: Short description

481-400: The auction. In particular, for every trading buyer: p ≤ B , and for every trading seller: p ≥ S . 2. Balanced Budget (BB) comes in two flavors: 3. Incentive compatibility (IC) also called truthfulness or strategy-proofness : also comes in two flavors (when unqualified IC generally means the stronger version): 4. Economic efficiency (EE): the total social welfare (the sum of

518-429: The buyer will be able to gain by declaring a lower value, or the seller will be able to gain by declaring a higher value. In an incomplete information (asymmetric information) case a buyer and a seller know only their own valuations. Suppose that these valuations are uniformly distributed over the same interval. Then it can be shown that such a game has a Bayesian Nash equilibrium with linear strategies. That is, there

555-489: The buyers and sellers: Every price in the range [max( s k , b k+1 ),min( b k , s k+1 )] is an equilibrium price, since both demand and supply are k . It is easier to see this by considering the range of equilibrium prices in each of the 4 possible cases (note that by definition of k , b k+1 < s k+1 ): A double auction can be analyzed as a game. Players are buyers and sellers. Their strategies are bids for buyers and ask prices for sellers (that depend on

592-402: The case of private goods; in the case of public goods the inefficiency is aggravated when the number of agents becomes large. 2. Myerson and Satterthwaite considered an asymmetric initial situation, in the sense that at the outset one party has 100% of the good and the other party has 0% of the good. It has been shown that ex post efficiency can be attained if initially both parties own 50% of

629-477: The following two assumptions are true: then, there is no mechanism which satisfies the four properties mentioned above (IR, WBB, NEIC and PE). Various variants of the Myerson–Satterthwaite setting have been studied. 1. Myerson and Satterthwaite considered a single buyer and a single seller. When there are many buyers and sellers, the inefficiency asymptotically disappears. However, this is only true in

666-477: The general double auction setting, the mechanism orders the buyers and sellers in the Natural ordering and finds the breakeven index k . Then the first k sellers give the item to the first k buyers. Each buyer pays the lowest equilibrium price max( s k , b k+1 ), and each seller receives the highest equilibrium price min( b k , s k+1 ), as in the following table: Similar to the bilateral trade scenario,

703-419: The good from seller k who receives min ( s k + 1 , b k ) {\displaystyle \min {(s_{k+1},b_{k})}} . Like the first variant, this variant is IR and has the same expected efficiency and surplus. Its advantage is that it "hides" its randomized character from almost all traders. The downside is that now the mechanism is truthful only ex-ante; i.e.,

740-505: The good to be traded. 3. The latter result has been extended to settings in which the parties can make unobservable ex ante investments in order to increase their own valuations. Yet, ex post efficiency cannot be achieved if the seller's unobservable investment increases the buyer's valuation, even if only the buyer has private information about his or her valuation. 4. Another impossibility result where only one party has private information about its valuation can be shown to hold when

777-438: The impossibility of satisfactory electoral systems . There are two agents: Sally (the seller) and Bob (the buyer). Sally holds an item that is valuable for both her and Bob. Each agent values the item differently: Bob values it as v B {\displaystyle v_{B}} and Sally as v S {\displaystyle v_{S}} . Each agent knows his/her own valuation with certainty, but knows

SECTION 20

#1732852377268

814-422: The interesting problem is to find a competitive equilibrium - a situation in which the supply equals the demand. In the simple bilateral trade scenario, if B ≥ S then any price in the range [ S , B ] is an equilibrium price, since both the supply and the demand equal 1. Any price below S is not an equilibrium price since there is an excess demand, and any price above B is not an equilibrium price since there

851-535: The item should be finally given to the agent who values it the most. Formally: t ( v B , v S ) = 1 {\displaystyle t(v_{B},v_{S})=1} if v B > v S {\displaystyle v_{B}>v_{S}} and t ( v B , v S ) = 0 {\displaystyle t(v_{B},v_{S})=0} if v B < v S {\displaystyle v_{B}<v_{S}} . If

888-430: The mechanism is IR, IC and EE (optimizes the social welfare), but it is not BB - the auctioneer subsidizes the trade. The uniqueness-of-prices theorem implies that this subsidy problem is inevitable - any truthful mechanism that optimizes the social welfare will have the same prices (up to a function independent of the ask/bid prices of each trader). If we want to keep the mechanism truthful while not having to subsidize

925-960: The mechanism. Hence, every agent can calculate his expected gain from the trade. Since we are interested in mechanisms which are truthful in equilibrium, we assume that each agent assumes that the other agent is truthful. Hence: Myerson and Satterthwaite study the following requirements that an ideal mechanism should satisfy (see also Double auction#requirements ): 1. individual rationality (IR): The expected value of both Bob and Sally should be non-negative (so that they have an initial incentive to participate). Formally: U S ( v S , v S ) ≥ 0 {\displaystyle U_{S}(v_{S},v_{S})\geq 0} and U B ( v B , v B ) ≥ 0 {\displaystyle U_{B}(v_{B},v_{B})\geq 0} . 2. Weak balanced budget (WBB): The auctioneer should not have to bring money from home in order to subsidize

962-670: The original mechanism, i.e. each buyer pays p b k + ( 1 − p ) max ( b k + 1 , s k ) {\displaystyle pb_{k}+(1-p)\max {(b_{k+1},s_{k})}} and each seller receives p s k + ( 1 − p ) min ( s k + 1 , b k ) {\displaystyle ps_{k}+(1-p)\min {(s_{k+1},b_{k})}} . Then, with probability p , buyer k pays max ( b k + 1 , s k ) {\displaystyle \max {(b_{k+1},s_{k})}} and buys

999-583: The outside option payoffs are not exogenously given. Double auction#requirements A double auction is a process of buying and selling goods with multiple sellers and multiple buyers. Potential buyers submit their bids and potential sellers submit their ask prices to the market institution, and then the market institution chooses some price p that clears the market: all the sellers who asked less than p sell and all buyers who bid more than p buy at this price p . Buyers and sellers that bid or ask for exactly p are also included. A common example of

1036-404: The previous section can be generalized to n players in the following way. This mechanism is: A VCG mechanism is a generic mechanism which optimizes the social welfare while achieving truthfulness. It does so by making each agent pay for the "damage" that his desires cause to society. In the simple bilateral trade setting, this translates to the following mechanism: This mechanism is: In

1073-521: The price in the following way: The utility of the buyer is: The utility of the seller is: In a complete information case when the valuations are common knowledge to both parties, it can be shown that the continuum of pure strategy efficient Nash equilibriums exists with b = s = p ∈ [ B , S ] . {\displaystyle b=s=p\in [B,S].} This means that, if B>S , there will be no equilibrium in which both players declare their true values: either

1110-419: The social welfare is not optimal, it is near-optimal, since the forbidden deal is the least favorable deal. Hence the gain-from-trade is at least 1 − 1 / k {\displaystyle 1-1/k} of the optimum. Note that in the bilateral trade setting, k =1 and we give up the only efficient deal, so there is no trade at all and the gain-from-trade is 0. This is in accordance with

1147-406: The trade, we must compromise on efficiency and implement a less-than-optimal social welfare function. The following mechanism gives up a single deal in order to maintain truthfulness: This mechanism is: If we tried to make this mechanism efficient by letting the k th buyer and seller trade, this would make it untruthful because then they will have an incentive to change their prices. Although

NEIC - Misplaced Pages Continue

1184-406: The trade-reduction mechanism: Similarly to the trade-reduction mechanism, this mechanism is IR, IC, WBB but not SBB (in the second case) and not EE (in the second case). Assuming that the values of the buyers and sellers are all bounded above zero, McAfee proves that the loss of trade efficiency is bounded by 1/min(num-of-buyers,num-of-sellers). Given a p ∈[0,1], after the bids are submitted, use

1221-901: The trade. 3. Nash equilibrium incentive compatibility (NEIC): for every agent, if the other agent reports the true value, then the best response is to report the true value too. In other words, no one should want to lie. Formally: ∀ v s ′ : U S ( v S , v S ) ≥ U S ( v S , v S ′ ) {\displaystyle \forall v'_{s}:U_{S}(v_{S},v_{S})\geq U_{S}(v_{S},v'_{S})} and ∀ v B ′ : U B ( v B , v B ) ≥ U B ( v B , v B ′ ) {\displaystyle \forall v'_{B}:U_{B}(v_{B},v_{B})\geq U_{B}(v_{B},v'_{B})} . 4. ex-post Pareto efficiency (PE):

1258-439: The valuation of the other agent only probabilistically: A direct bargaining mechanism is a mechanism which asks each agent to report his/her valuation of the item, then decides whether the item will be traded and at what price. Formally, it is represented by two functions: Note that, thanks to the revelation principle , the assumption that the mechanism is direct does not lose generality. Every agent knows his value and knows

1295-435: The valuations of buyers and sellers). Payoffs depend on the price of the transaction (determined by the auctioneer) and the valuation of a player. The interesting problem is to find a Nash equilibrium - a situation in which no trader has an incentive to unilaterally change their bid/ask price. Consider the bilateral trade scenario, in which the buyer submits a bid of b and the seller submits s . Suppose an auctioneer sets

1332-400: The values of all players) should be the best possible. In particular, this means that, after all trading has completed, the items should be in the hands of those that value them the most. Unfortunately, it is not possible to achieve all these requirements in the same mechanism (see Myerson–Satterthwaite theorem ). But there are mechanisms that satisfy some of them. The mechanism described in

1369-543: The various mechanisms. Dütting, Roughgarden and Talgam-Cohen proposed a modular approach to the design of double auctions. Their framework views double auctions as being composed of ranking algorithms for each side of the market and a composition rule, and can be applied to complex markets. An immediate consequence of this framework is that classic double auction mechanisms such as the trade reduction mechanism are not only strategyproof but also weakly group-strategyproof (meaning that no group of buyers and sellers can benefit by

#267732