formulasearchengine - User contributions [en]

Courant algebroid

2013-11-15T00:33:52Z

130.56.87.237: Corrected a sign error in definition of a Lie bialgebroid as the dual exterior derivative acting as a derivation on the bracket.

In [[computer science]], a '''succinct data structure''' is a [[data structure]] which uses an amount of space that is "close" to the [[information-theoretic]] lower bound, but (unlike other compressed representations) still allows for efficient query operations. The concept was originally introduced by Jacobson <ref name="jacobson1988succinct"/> to encode [[bit vector]]s, (unlabeled) [[tree (data structure)|trees]], and [[planar graph]]s. Unlike general [[lossless data compression]] algorithms, succinct data structures retain the ability to use them in-place, without decompressing them first. A related notion is that of a [[compressed data structure]], in which the size of the data structure depends upon the particular data being represented.

Suppose that <math>Z</math> is the information-theoretical optimal number of bits needed to store some data. A representation of this data is called

* ''[[implicit data structure|implicit]]'' if it takes <math>Z + O(1)</math> bits of space,
* ''succinct'' if it takes <math>Z + o(Z)</math> bits of space, and
* ''compact'' if it takes <math>O(Z)</math> bits of space.

Implicit structures are thus usually reduced to storing information using some permutation of the input data; the most well-known example of this is the heap.

==Succinct dictionaries==

Succinct indexable dictionaries, also called ''rank/select'' dictionaries, form the basis of a number of succinct representation techniques, including [[binary trees]], <math>k</math>-ary trees and [[multisets]],<ref name="raman2002succinct"/> as well as [[suffix tree]]s and [[suffix array|arrays]].<ref name="sadakane2006squeezing"/> The basic problem is to store a subset <math>S</math> of a universe <math>U =
[0 \dots n) = \{0, 1, \dots, n - 1\}</math>, usually represented as a bit array <math>B[0 \dots n)</math> where <math>B[i] = 1</math> iff <math>i \in S</math>. An indexable dictionary supports the usual methods on dictionaries (queries, and insertions/deletions in the dynamic case) as well as the following operations:

* <math>\mathbf{rank}_q(x) = |\{ k \in [0 \dots x) : B[k] = q \}|</math>
* <math>\mathbf{select}_q(x)= \min \{k \in [0 \dots n) : \mathbf{rank}_q(k) = x\}</math>

for <math>q \in \{0, 1\}</math>.

In other words, <math>\mathbf{rank}_q(x)</math> returns the number of elements equal to <math>q</math> up to position <math>x</math> while <math>\mathbf{select}_q(x)</math> returns the position of the <math> x</math>-th occurrence of <math> q </math>.

There is a simple representation <ref name="jacobson1989space"/> which uses <math>n + o(n)</math> bits of storage space (the original bit array and an <math>o(n)</math> auxiliary structure) and supports '''rank''' and '''select''' in constant time. It uses an idea similar to that for [[Range Minimum Query|range-minimum queries]]; there are a constant number of recursions before stopping at a subproblem of a limited size. The bit array <math>B</math> is partitioned into ''large blocks'' of size <math>l = \lg^2 n</math> bits and ''small blocks'' of size <math>s = \lg n / 2</math> bits. For each large block, the rank of its first bit is stored in a separate table <math>R_l[0 \dots n/l)</math>; each such entry takes <math>\lg n</math> bits for a total of <math>(n/l) \lg n = n / \lg n</math> bits of storage. Within a large block, another directory <math>R_s[0 \dots l/s)</math> stores the rank of each of the <math>l/s = 2 \lg n</math> small blocks it contains. The difference here is that it only needs <math>\lg l = \lg \lg^2 n = 2 \lg \lg n</math> bits for each entry, since only the differences from the rank of the first bit in the containing large block need to be stored. Thus, this table takes a total of <math>(n/s) \lg l = 4 n \lg \lg n / \lg n</math> bits. A lookup table <math>R_p</math> can then be used that stores the answer to every possible rank query on a bit string of length <math>s</math> for <math>i \in [0, s)</math>; this requires <math>2^s s \lg s = O(\sqrt{n} \lg n \lg \lg n)</math> bits of storage space. Thus, since each of these auxiliary tables take <math>o(n)</math> space, this data structure supports rank queries in <math>O(1)</math> time and <math>n + o(n)</math> bits of space.

To answer a query for <math>\mathbf{rank}_1(x)</math> in constant time, a constant time algorithm computes

<math>\mathbf{rank}_1(x) = R_l[\lfloor x / l \rfloor] + R_s[\lfloor x / s\rfloor] + R_p[x \lfloor x / s\rfloor, x \text{ mod } s]</math>

In practice, the lookup table <math>R_p</math> can be replaced by bitwise operations and smaller tables to perform find the number of bits set in the small blocks. This is often beneficial, since succinct data structures find their uses in large data sets, in which case cache misses become much more frequent and the chances of the lookup table being evicted from closer CPU caches becomes higher.<ref name="gonzález2005practical" /> Select queries can be easily supported by doing a binary search on the same auxiliary structure used for '''rank'''; however, this takes <math>O(\lg n)</math> time in the worst case. A more complicated structure using <math>3n/\lg \lg n + O(\sqrt{n} \lg n \lg \lg n) = o(n)</math> bits of additional storage can be used to support '''select''' in constant time.<ref name="clark1998compact" /> In practice, many of these solutions have hidden constants in the <math>O(\cdot)</math> notation which dominate before any asymptotic advantage becomes apparent; implementations using broadword operations and word-aligned blocks often perform better in practice.<ref name="vigna2008broadword" />

===Entropy-compressed dictionaries===

The <math>n + o(n)</math> space approach can be improved by noting that there are <math>\textstyle \binom{n}{m}</math> distinct <math>m</math>-subsets of <math>[n)</math> (or binary strings of length <math>n</math> with exactly <math>m</math> 1’s), and thus <math>\textstyle \mathcal{B}(m,n) = \lceil \lg \binom{n}{m} \rceil</math> is an information theoretic lower bound on the number of bits needed to store <math>B</math>. There is a succinct (static) dictionary which attains this bound, namely using <math>\mathcal{B}(m,n) + o(\mathcal{B}(m,n))</math> space.<ref name="brodnik1999membership" /> This structure can be extended to support '''rank''' and '''select''' queries and takes <math>\mathcal{B}(m,n) + O(m + n \lg \lg n / \lg n)</math> space.<ref name="raman2002succinct" /> This bound can be reduced to a space/time tradeoff by reducing the storage space of the dictionary to <math>\mathcal{B}(m,n) + O(n t^t / \lg^t n + n^{3/4})</math> with queries taking <math>O(t)</math> time.<ref name="patrascu2008succincter" />

==Examples==

When a sequence of variable-length items needs to be encoded, the items can simply be placed one after another, with no delimiters. A separate binary string consisting of 1s in the positions where an item begins, and 0s every where else is encoded along with it. Given this string, the <math>select</math> function can quickly determine where each item begins, given its index.<ref>{{cite web|url=http://cmph.sourceforge.net/papers/esa09.pdf |title=Hash, displace, and compress|last=Belazzougui|first=Djamal}}</ref>

Another example is the representation of a [[binary tree]]: an arbitrary binary tree on <math>n</math> nodes can be represented in <math>2n + o(n)</math> bits while supporting a variety of operations on any node, which includes finding its parent, its left and right child, and returning the size of its subtree, each in constant time. The number of different binary trees on <math>n</math> nodes is <math>{\tbinom{2n}{n}}</math><math>/(n+1)</math>. For large <math>n</math>, this is about <math>4^n</math>; thus we need at least about <math>\log_2(4^n)=2n</math> bits to encode it. A succinct binary tree therefore would occupy only <math>2</math> bits per node.

==References==
<references>
<ref name="jacobson1988succinct">
{{Cite journal
| last = Jacobson
| first = G. J
| title = Succinct static data structures
| year = 1988
}}
</ref>
<ref name="raman2002succinct">
{{Cite conference
| isbn = 0-89871-513-X
| pages = 233–242
| last = Raman
| first = R.
| coauthors = V. Raman, S. S Rao
| title = Succinct indexable dictionaries with applications to encoding k-ary trees and multisets
| booktitle = Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms
| date = 2002
| url = http://www.cs.cmu.edu/afs/cs.cmu.edu/project/aladdin/wwwlocal/hash/RaRaRa02.pdf
}}
</ref>
<ref name="sadakane2006squeezing">
{{Cite conference
| isbn = 0-89871-605-5
| pages = 1230–1239
| last = Sadakane
| first = K.
| coauthors = R. Grossi
| title = Squeezing succinct data structures into entropy bounds
| booktitle = Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
| date = 2006
| url = http://www.dmi.unisa.it/people/cerulli/www/WSPages/WSFiles/Abs/S3/S33_abs_Grossi.pdf
}}
</ref>
<ref name="jacobson1989space">
{{Cite journal
| last = Jacobson
| first = G.
| title = Space-efficient static trees and graphs
| year = 1989
| url = http://www.cs.cmu.edu/afs/cs/project/aladdin/wwwlocal/compression/00063533.pdf
}}
</ref>
<ref name="gonzález2005practical">
{{Cite conference
| pages = 27–38
| last = González
| first = R.
| coauthors = S. Grabowski, V. Mäkinen, G. Navarro
| title = Practical implementation of rank and select queries
| booktitle = Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA)
| date = 2005
| url = http://www.dcc.uchile.cl/~gnavarro/algoritmos/ps/wea05.pdf
}}
</ref>
<ref name="clark1998compact">
{{Cite journal
| last = Clark
| first = D.
| title = Compact pat trees
| year = 1998
| url = https://uwspace.uwaterloo.ca/bitstream/10012/64/1/nq21335.pdf
}}
</ref>
<ref name="vigna2008broadword">
{{Cite journal
| pages = 154–168
| last = Vigna
| first = S.
| title = Broadword implementation of rank/select queries
| journal = Experimental Algorithms
| year = 2008
| url = http://sux.dsi.unimi.it/paper.pdf
| doi = 10.1007/978-3-540-68552-4_12
| series = Lecture Notes in Computer Science
| isbn = 978-3-540-68548-7
| volume = 5038
}}
</ref>
<ref name="brodnik1999membership">
{{Cite journal
| volume = 28
| issue = 5
| pages = 1627–1640
| last = Brodnik
| first = A.
| coauthors = J. I Munro
| title = Membership in constant time and almost-minimum space
| journal = SIAM J. Comput.
| year = 1999
| url = http://www.cs.cmu.edu/afs/cs.cmu.edu/project/aladdin/wwwlocal/compression/BM99.pdf
| doi = 10.1137/S0097539795294165
}}
</ref>
<ref name="patrascu2008succincter">
{{Cite conference
| pages = 305–313
| last = Pătraşcu
| first = M. | authorlink = Mihai Pătraşcu
| title = Succincter
| booktitle = Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on
| date = 2008
| url = http://people.csail.mit.edu/mip/papers/succinct/succinct.pdf
}}
</ref>
</references>

{{DEFAULTSORT:Succinct Data Structure}}
[[Category:Data structures]]

Simply connected at infinity

2013-09-18T04:19:10Z

130.56.26.195: Stallings theorem only works for high dimensional manifolds. Added a reference.

{{No footnotes|date=March 2011}}

The two person '''bargaining problem''' is a problem of understanding how two agents should cooperate when non-cooperation leads to [[Pareto efficiency|Pareto-inefficient]] results. It is in essence an equilibrium selection problem; many games have multiple equilibria with varying payoffs for each player, forcing the players to negotiate on which equilibrium to target. The quintessential example of such a game is the [[ultimatum game]]. The underlying assumption of bargaining theory is that the resulting solution should be the same solution an impartial arbitrator would recommend. Solutions to bargaining come in two flavors: an axiomatic approach where desired properties of a solution are satisfied and a strategic approach where the bargaining procedure is modeled in detail as a sequential game.

==The bargaining game==

The '''bargaining game''' or '''[[John Forbes Nash | Nash]] bargaining game''' is a simple two-player [[game theory|game]] used to model bargaining interactions. In the Nash bargaining game, two players demand a portion of some good (usually some amount of money). If the total amount requested by the players is less than that available, both players get their request. If their total request is greater than that available, neither player gets their request. A '''Nash bargaining solution''' is a ([[Pareto efficiency|Pareto efficient]]) solution to a Nash bargaining game.
According to Walker (2005), Nash's bargaining solution was shown by [[John Harsanyi]] to be the same as [[Zeuthen Strategy|Zeuthen]]'s solution of the bargaining problem (''Problems of Monopoly and Economic Warfare'', 1930).

==An example==

{|align=right
|
{{Payoff matrix | Name = Battle of the Sexes 1
| 2L = opera | 2R = football |
1U = opera | UL = 3,2 | UR = 0,0 |
1D = football | DL = 0,0 | DR = 2,3 |
Float = none }}
|}

The [[battle of the sexes (game theory)|battle of the sexes]], as shown, is a two player [[coordination game]]. Both opera/opera and football/football are [[Nash equilibria]]. Any probability distribution over these two Nash equilibria is a [[correlated equilibrium]]. The question then becomes which of the infinitely many possible equilibria should be chosen by the two players. If they disagree and choose different distributions, they are likely to receive 0 payoffs. In this symmetric case the natural choice is to play opera/opera and football/football with equal probability. Indeed all bargaining solutions described below prescribe this solution. However, if the game is asymmetric---for example, football/football instead yields payoffs of 2,5--- the appropriate distribution is less clear. The problem of finding such a distribution is addressed by the bargaining theory.

==Formal description==

A two person bargain problem consists of a disagreement, or threat, point <math>v=(v_1, v_2)</math>, where <math>v_1</math> and <math>v_2</math> are the respective payoffs to player 1 and player 2, and a feasibility set <math>F</math>, a closed convex subset of <math>\textbf{R}^2</math>, the elements of which are interpreted as agreements. Set <math>F</math> is convex because an agreement could take the form of a correlated combination of other agreements. The problem is nontrivial if agreements in <math>F</math> are better for both parties than the disagreement. The goal of bargaining is to choose the feasible agreement <math>\phi</math> in <math>F</math> that could result from negotiations.

=== Feasibility set ===

Which agreements are feasible depends on whether bargaining is mediated by an additional party. When binding contracts are allowed, any joint action is playable, and the feasibility set consists of all attainable payoffs better than the disagreement point. When binding contracts are unavailable, the players can defect (moral hazard), and the feasibility set is composed of correlated equilibria, since these outcomes require no exogenous enforcement.

=== Disagreement point ===

The disagreement point <math>v</math> is the value the players can expect to receive if negotiations break down. This could be some [[Focal point (game theory)|focal equilibrium]] that both players could expect to play. This point directly affects the bargaining solution, however, so it stands to reason that each player should attempt to choose his disagreement point in order to maximize his bargaining position. Towards this objective, it is often advantageous to increase one's own disagreement payoff while harming the opponent's disagreement payoff (hence the interpretation of the disagreement as a threat). If threats are viewed as actions, then one can construct a separate game wherein each player chooses a threat and receives a payoff according to the outcome of bargaining. It is known as Nash's variable threat game. Alternatively, each player could play a [[minimax]] strategy in case of disagreement, choosing to disregard personal reward in order to hurt the opponent as much as possible should the opponent leave the bargaining table.

== Equilibrium analysis ==

Strategies are represented in the Nash bargaining game by a pair (''x'', ''y''). ''x'' and ''y'' are selected from the [[interval (mathematics)|interval]] [''d'', ''z''], where ''z'' is the total good. If ''x'' + ''y'' is equal to or less than ''z'', the first player receives ''x'' and the second ''y''. Otherwise both get ''d''. ''d'' here represents the disagreement point or the threat of the game; often <math>d=0</math>.

There are many [[Nash equilibria]] in the Nash bargaining game. Any ''x'' and ''y'' such that ''x'' + ''y'' = ''z'' is a Nash equilibrium. If either player increases their demand, both players receive nothing. If either reduces their demand they will receive less than if they had demanded ''x'' or ''y''. There is also a Nash equilibrium where both players demand the entire good. Here both players receive nothing, but neither player can increase their return by unilaterally changing their strategy.

== Bargaining solutions ==

Various solutions have been proposed based on slightly different assumptions about what properties are desired for the final agreement point.

=== Nash bargaining solution ===

John Nash proposed that a solution should satisfy certain axioms:

#Invariant to affine transformations or Invariant to equivalent utility representations
#[[Pareto optimality]]
#[[Independence of irrelevant alternatives]]
#[[Symmetry]]

Let ''u'' and ''v'' be the utility functions of Player 1 and Player 2, respectively. In the ''Nash bargaining solution'', the players will seek to maximize <math>(u(x)-u(d))*(v(y)-v(d))</math>, where <math>u(d)</math> and <math>v(d)</math>, are the [[status quo]] utilities (i.e. the utility obtained if one decides not to bargain with the other player). The product of the two excess utilities is generally referred to as the ''Nash product''. Intuitively, the solution consists of each player getting her status quo payoff (i.e., noncooperative payoff) in addition to an equal share of the benefits accruing from cooperation (Muthoo 1999, pp. 15–16).

=== Kalai-Smorodinsky bargaining solution ===

Independence of Irrelevant Alternatives can be substituted with a monotonicity condition, as demonstrated by [[Ehud Kalai]] and Meir Smorodinsky. It is the point which maintains the ratios of maximal gains. In other words, if player 1 could receive a maximum of <math>g_1</math> with player 2’s help (and vice-versa for <math>g_2</math>), then the Kalai-Smorodinsky bargaining solution would yield the point <math>\phi</math> on the Pareto frontier such that <math>\phi_1 / \phi_2 = g_1 / g_2 </math> .

=== Egalitarian bargaining solution ===

The egalitarian bargaining solution, introduced by Ehud Kalai, is a third solution which drops the condition of scale invariance while including both the axiom of [[Independence of irrelevant alternatives]], and the axiom of monotonicity. It is the solution which attempts to grant equal gain to both parties. In other words, it is the point which maximizes the minimum payoff among players. Kalai notes that this solution is closely related to the ideas of [[John Rawls]].

== Applications ==

Some [[philosophy|philosophers]] and [[economics|economists]] have recently used the Nash bargaining game to explain the emergence of human attitudes toward [[distributive justice]] (Alexander 2000; Alexander and Skyrms 1999; Binmore 1998, 2005). These authors primarily use [[evolutionary game theory]] to explain how individuals come to believe that proposing a 50-50 split is the only [[justice|just]] solution to the Nash bargaining game.

==See also==
*[[Bargaining]]
*[[Rubinstein bargaining model]]
*[[Nash equilibrium]]
*[[Ultimatum game]]

== References ==
*{{cite journal |last=Alexander |first=Jason McKenzie |year=2000 |title=Evolutionary Explanations of Distributive Justice |journal=[[Philosophy of Science]] |volume=67 |issue=3 |pages=490–516 |doi= |jstor=188629 }}
*{{cite journal |last=Alexander |first=Jason |first2=Brian |last2=Skyrms |year=1999 |title=Bargaining with Neighbors: Is Justice Contagious |journal=[[Journal of Philosophy]] |volume=96 |issue=11 |pages=588–598 |doi= |jstor=2564625 }}
*{{cite journal |last=Binmore |first=K. |last2=Rubinstein |first2=A. |last3=Wolinsky |first3=A. |year=1986 |title=The Nash Bargaining Solution in Economic Modelling |journal=[[RAND Journal of Economics]] |volume=17 |issue= |pages=176–188 |doi= |jstor=2555382 }}
*{{cite book |authorlink=Kenneth Binmore |last=Binmore |first=Kenneth |year=1998 |title=Game Theory and the Social Contract Volume 2: Just Playing |location=Cambridge |publisher=MIT Press |isbn=0-262-02444-6 }}
*{{cite book |last=Binmore |first=Kenneth |year=2005 |title=Natural Justice |location=New York |publisher=Oxford University Press |isbn=0-19-517811-4 }}
*{{cite journal |last=Kalai |first=Ehud |year=1977 |title=Proportional solutions to bargaining situations: Intertemporal utility comparisons |journal=[[Econometrica]] |volume=45 |issue=7 |pages=1623–1630 |doi= |jstor=1913954 }}
*{{cite journal |last=Kalai |first=Ehud |lastauthoramp=yes |first2=Meir |last2=Smorodinsky |year=1975 |title=Other solutions to Nash’s bargaining problem |journal=Econometrica |volume=43 |issue=3 |pages=513–518 |doi= |jstor=1914280 }}
* Muthoo, Abhinay (1999). ''Bargaining theory with applications''. Cambridge University Press.
*{{cite journal |last=Nash |first=John |year=1950 |title=The Bargaining Problem |journal=Econometrica |volume=18 |issue=2 |pages=155–162 |doi= |jstor=1907266 }}
*{{cite web |last=Walker |first=Paul |year=2005 |title=History of Game Theory |url=http://www.econ.canterbury.ac.nz/personal_pages/paul_walker/gt/hist.htm#ref94 }}

==External links==

* [http://www.cse.iitd.ernet.in/~rahul/cs905/lecture15/ Nash bargaining solutions]

{{Game theory}}

[[Category:Game theory]]
[[Category:Cooperative games]]

Hermitian symmetric space

2012-06-28T04:42:07Z

130.56.101.100: added the word "involutive" before the word "biholomorphism" in the definition of bounded symmetric domain

I would like to introduce myself to you, I am Jayson Simcox but I don't like when people use my complete title. I've usually cherished residing in Mississippi. What I adore performing is soccer but I don't have the time recently. He is an order clerk and it's some thing he truly enjoy.<br><br>Have a look at my web-site - [http://www.seekavideo.com/playlist/2199/video/ free psychic]