Betting on Permutations
 
The permutations paper provides important results regarding the computational 
complexity of auctioneer problem of risklessly matching up wagers in permutation 
betting. The matching problem for subset betting and pair betting result in 
different complexities, where the first can be solved in polynomial time, but 
the second cannot. It is important to point out that the state space for subset 
betting grows much larger than for pair betting. If I have n horses, then there 
are 2*(n choose 2) possible pairwise comparisons, but there are a much greater 
number of subset bets I can make. I also find it interesting that the idea of 
A>B cannot be expressed in terms of some combination of subset bets.
 
I think a possible direction for future research, empirical or theoretical, 
would be to examine how well these markets work with regard to efficiency of 
information aggregation. I also wonder how a bidding language that allowed both 
types of bets would perform under the same metrics.
 


Pricing Combinatorial Markets For Tournaments
 
The second paper considers combinatorial markets for tournaments and uses a 
Bayesian network to represent market distributions. I found it interesting that 
the paper mentioned the NCAA tournament. I wonder whether it would be practical 
to allow for combinatorial bets in such a tournament. The reason is that assuming 
players have a fixed budget and limited time to process information before 
submitting bids for such a tournament, it is possible that a larger state space 
of events will result in each estimate being less likely. For example, if I believe 
Stanford and Duke will both lose in round 1 and are on separate sides of the draw, 
why would I even bother betting on Stanford vs Duke? Does this limit the potential 
efficiency/information aggregation gains of this type of market? If they are 
allowed to place odds on every combination, they might be less likely to make an 
accurate prediction of each individual combination.

Betting on Permutation

Basically, subset betting is betting on the specific rankings for a few horses,
and pair betting is betting that horse X will beat horse Y. This paper looks at
pair betting and subset betting proving that it is NP-hard for the matching
problem. The verification can be done in polynomial time. I think further
explanation of the intuition and implication of the results of this paper would
be helpful.

Something that potentially interests me about these two papers, is that if the
implication is that the computational complexity is unrealistic for these types
of betting situations, what types of approximation methods are generally used? I
would be interested in learning more about those. The paper mentioned something
about a natural greedy alorithm being ineffective, but what, if any, other
methods are there?

Pricing Combinatorial Markets for Tournaments

Combinatorial markets are able to approximate an entire joint distribution. This 
paper claims that they are NP-hard in computational complexity, meaning that they 
are at least as hard as the hardest non-deterministic polynomial problem. The paper 
shows that one can represent the distributions as Bayesian networks. For any change 
in distribution following from a purchase of bets, any resulting distribution can 
still be modeled by a Bayesian network.

This paper shows that single-elimination tournaments can be represented as stated. 
I am not sure that I fully understand the full breadth of the results presented. 
Perhas that would be useful to discuss more.

The first paper "Betting on Permutations" by Y. Chen, et al, seeks to analyze the 
auctioneer problem of matching up wagers in permutation betting. The paper looks 
at subset betting and permutation betting. Both of these scenarios are important 
because they directly correlate to real-world applications of the stock market and 
horse race betting, to name a few examples. The paper states that buying or selling 
a stock is equivalent to betting on the stock's value. In the case of subset 
betting, where participants decide which positions a candidate will fall, the 
authors show that there is a polynomial time algorithm for the subset matching 
problem. The key insight is to show the reduction of the problem to a maximum 
weighted bipartite graph, and, since this solution has a polynomial time result, 
the original problem can be solved similarly. In the scenario of pair betting, 
however, optimal matching of pair bets is shown to be NP-hard. One limitation 
in the paper is the bound set on the bets of any property and ordering. It is 
stated that allowing this would increase the computational complexity too 
drastically. A previous paper on the market scoring rule is used as a basis along 
with previous work on combinatorial auctions. In an attempt to solve the problem in 
pair betting, a greedy algorithm is used but is shown to be a poor approximation. 
This idea can be extended beyond this paper by conducting research to find an 
algorithm that gives a closer approximation. One project idea that could result 
from this paper is to actually apply the concepts into a software implementation 
and simulate the stock market. This will verify the usefulness and accuracy of this 
model to real life scenarios and could provide insight into flaws or inadequacies.

The second paper, "Pricing Combinatorial Markets for Tournaments" by Y. Chen, et. al.,
also covers combinatorial market concepts by applies them to the specific case of 
tournaments. The authors consider single-elimination tournaments, which somewhat 
limits the complexity of the calculations. They reach the conclusion that the solution 
to the pricing problem in this is NP-hard. This leads to the conclusion that 
considering non-single elimination tournaments would yield the same result. By choosing 
to represent the market distributions as Bayesian networks, the authors assume that at 
each stage, the available and past moves are known. Through extensive mathematical 
proofs, the solution is shown to be NP-hard. One idea that the paper uses that I found 
interesting was representing each game as if it were an independent market. This 
assumes, of course, that the result of another game does not affect the outcome of 
another game in the same round. One project idea from this paper is the application of 
this model to real sports tournaments. In those tournaments, the victory of one team 
over another has minimal impact on other games in the same round. This would give 
insight into the accuracy of this model and possibly give way to approximate solutions 
that are at least polynomial in complexity.

Betting on Permutations:

This paper discusses the case of permutation betting. This type of betting is
applicable to most types of markets where people wager including the financial
market where people wager on the security's value. This paper also examines a
scheme called Subset betting that simplifies the the complexity of the
auctioneer problem where bidders have large number of subsets of orderings. The
scheme proposed tries to offer an expressive bidding language that is still
feasible to compute. Having bidders bid on sets rather than individual
positions simplifies the computation tasks and minimizes the number of
orderings subsets. The other proposed scheme is Pair betting where bidders bid
on final outcome.

In general permutation betting markets, an auctioneer needs to solve both
matching, a decision problem, and optimal matching problems. In other words,
the matching problem, also called the existence of a match, is fact that the
auctioneer needs to find a subset of orders submitted by bidders that can be
matched in a risk free manner that will give a non negative profit. Te other
problem that the auctioneer needs to address is the optimal matching where
he/she needs to take into consideration other factors such as profit or volume.

On the other hand, in the Subset betting markets, traders can bet on subsets of
positions a player might end up at or bet on subset of players to occupy a
particular position. In this type of market, the matching problem is more
complex than in the general permutation betting markets due to the fact that
the number of available securities to bet on is exponential. So, the matching
problems in this kind of markets have large number of constraints.Finally, pair
betting markets allow traders to bet on weather a candidate will rank higher
than the other. This type of betting is very complex.

In conclusion, we can see from this paper that an auctioneer can find the
optimal set  in the Subset betting. An unexplored area left in this paper is
the computational complexity of optimal indivisible matching for subset
betting.

--------------------------------------

Pricing Combinatorial Markets for Tournaments:

This paper discusses the problem of pricing combinatorial markets for
single-elimination tournaments arising from the fact that the probability
distribution over a set is exponentially larger than the number of base bets.
This paper also demonstrates a pricing algorithm by restricting to a natural
betting language.

Consider a n team tournaments represented as a set of binary vectors of length
n-1 where agents can bet on the 2^2n-1 subsets of the entire outcome space.
This paper shows that in this example, the pricing problem is #p hard. When
types of bets agents are  restricted, Bayesian network structure is not
preserved.

This paper also discusses other problems but i found it hard to follow.

Betting on Permutations (1) and Pricing Combinatorial Markets for Tournaments (2)

The main contribution of the first paper is in establishing the hardness of two bidding 
languages that allow for fairly expressive bids in a market where the outcome is a 
permutation. In subset betting, where a bidder is allowed to bet on multiple candidates 
landing at a particular location or a particular candidate landing at multiple locations, 
the authors prove that an auctioneer can compute the optimal match (e.g., maximize worst 
case profit) in polynomial time. The result is surprising in that there are exponential 
number of possible bids that a bidder can submit. By using the ellipsoid method and a 
theorem on its polynomial time complexity as long as there exists a polynomial time 
algorithm to solve the separation problem may give non-positive outcome. Here the 
authors give an ingenious reduction via bipartite matching that uses weights depicting 
payout to link candidates to orderings, which has a polynomial time solution despite an 
exponential number of possible orderings. The authors then considered pair betting and 
showed that it was surprisingly NP-hard. I find this to be quite a negative result because 
it seems fairly natural for bidders to have beliefs about relative likelihoods of victory 
over candidates than positional estimates.

The main contribution of the second paper is in establishing the hardness of the general 
pricing problem for tournaments and providing a tractable bidding language for expressive 
bidding in tournaments. The bidding language allows for bids over teams winning particular 
games, possibly conditioned on reaching that game, as well as pairwise bids over winners, 
given that two teams face off. The authors show that under this bidding language, updating 
probabilities via the log market scoring rule can be done by updating the Bayesian network. 
Given the tournament tree structure of the Bayes net, updates can be done in polynomial 
time. The authors then show that the expressiveness of the language leads to voiding 
independence assumptions among different branches of the tournament, but that these 
assumptions are preserved by restricting the language to be conditional on teams winning.

In both papers, I found the application of known theoretical results relating to LP, 
bipartite matching, and Bayes Nets to be crucial to finding tractable expressive 
languages. It seems that future progress may also rely on breaking down the combinatorial 
problem via the considerations of known effective restrictions of the known, e.g., tree 
structures and bipartite graphs. One part that strikes me is how pairwise bidding is 
NP complete in the permutations case but similar pairwise bidding in tournaments is not, 
which seems intuitive in that we need not consider all permutations in tournaments but still 
baffling at the same time. One question I have for future work is whether any of the results 
can be extended to non-permutation/tournament settings, whether seemingly general settings 
via restricted languages or other games where the outcome space is structured.

Pricing Combinatorial Markets for Tournaments

This paper discussed combinatorial betting, such as in a single-elimination tournament. 
The paper was interesting in that it uses the framework of a Bayesian network to represent 
the tournament and how parent games relate to child games. All in all, the paper had two 
main contributions - it determined that generally, pricing for this tournament was #P Hard 
because a game of n players can have up to 2^(n-1) different ways to bet.  In addition, it 
developed a polynomial-time algorithm to price the tournament bets on a restricted betting 
space. Furthermore, it determined that it is necessary to limit the space of possible bets 
to those that allow independent events to remain independent - thus, the only type of 
conditionally dependent bets that are allowed are of the form "x will beat y given that 
they face off." This way, the Bayesian network relationships and unrelated probabilities 
remain unchanged, while overall probabilities change slightly.

This paper was different from the other one we read because it uses Bayesian networks rather 
than graphs to match bets / make the market. However, they are similar in that they both 
concern a betting space that is exponentially large. One difficulty I had while reading 
this paper was understanding some of the terminology - specifically, I had no idea what 
#P hard meant and so I did not know why having a #P hard problem was a bad thing. However, 
overall the structure of the paper was good and it presented an interesting approach, the 
Bayesian network, to solving this problem. A possible extension to this paper may be to 
look at tournaments with different elimination rules, such as double elimination or round 
robin, and see if we apply the same methods to those types of tournaments.

Betting on Permutations

I thought this paper was very interesting - it addresses the matching problem that auctioneers 
face when people bet on permutations of an outcome.  For example, a horse race will have many 
different outcomes depending on which horse places where, and the auctioneer will want to 
aggregate all these bets to accept or reject them in order to minimize the maximum loss, and 
hopefully always make a profit. The main contribution of this paper was proving that matching 
subset bets with divisible amounts can be done in polynomial time, while matching pair bets 
(both divisible and indivisible amounts) is an NP-hard problem, which is interesting because 
the space of possible matches is much smaller in pair matching than subset matching. Finally, 
this paper proved that figuring out if a solution exists can be done in polynomial time. I 
thought it was particularly interesting that most of the proofs were done by reducing problems 
in graph theory and changing the problem into a problem that we already know is NP-hard or 
NP-complete. I guess I had never thought to have bets placed in a graph in order to match them.

An aspect of the problem that I think would be interesting to examine is the optimizations. 
In all the problems examined in this paper it has attempted to maximize the auctioneer's profit 
and attempted to minimize the worst case scenario loss. Even though these are NP-hard problems, 
I am wondering if there are randomized algorithms and/or optimizations that can be done while 
actually computing the solution in order to reach a good, but not perfect solution in polynomial 
time. In addition, it would be interesting to compare the results of these optimizations to 
auctioneers in real life who may not have the time to figure out how to best match different 
bets. How do auctioneers decide on the spot whether to accept or reject a bid?

The papers [CFNP] and [CGP] both studied prediction market on permutations. In markets of 
such setting, the only information to be aggregated is the ranking of a set of items. It 
is slightly surprising that in this restricted problem, we still cannot do much to design 
a computational feasible mechanism (or maybe the emphasis on the negative results on both 
papers gives this illusion…). In [CFNP], both the subset betting and the pair betting 
problems are reduced to optimization problems in more conventional form such as linear 
programming or finding some specific properties over the graph. Some of the techniques 
appeared in the reduction are quite neat. In [CGP], they studied the complexity of 
logarithm scoring rule and obtained a few immediate impossible results. When imposing 
further constraints in betting language, polynomial running time algorithm becomes 
possible. 
After reading an array of “theory” papers in prediction markets, I start to be confused 
about some high level questions. Perhaps the most important question is that I am not 
sure that whether the model of the market or the technical part in proving the theorems 
is more important in papers of such type. When facing a computational complexity paper, 
the techniques used in the proofs are arguably the soul of the paper and ultimately we 
would like to build up a systematic toolset to approach complexity problems. And we 
expected the invented techniques can be reused. For these theory paper, on the other 
hand, the techniques appeared in the proofs seem to be isolated and it is not clear how 
we shall treat these proofs. A second confusion is that the distance between theory and 
practice in the prediction market seems to be even larger than such distance in computer 
science. Even using the most abstract model, a theoretical computer science result has a 
direct and clear implication in the “real world”. Meanwhile, perhaps it is not even easy 
to validate any model in real market, the connection between theory and practice seems to 
be quite remote in prediction market studies.  
 
[CFNP] Y. Chen, L.Fortnow, E.Nikolova, D.Pennock “Betting on Prediction Markets”
[CGP] Y.Chen, S.Goel, and D. Pennock, “Pricing Combinatorial Markets for Tournaments”. 

Betting on Permutations
By Chen et. al.

Pricing Combinatorial Markets for Tournaments
By Chen, Goel, and Pennock

"Betting on Permutations" explores the auctioneer's order matching problem in auctions 
involving the outcomes/ordering of candidates, e.g. participants in a race. Since allowing 
all n! different possible bets would make the auctioneer's problem computationally hard, 
the authors provide two betting languages to restrict the betting space. The first is subset 
betting, which allows bets of the form "some candidate in subset A will finish in position b" 
and bets of the form "candidate a will finish in some position in subset B". Even though the 
number of such bets in exponential in the number of candidates, the authors prove that the 
auctioneer can solve the order matching problem in polynomial time complexity. The second 
betting language is pair betting, which allows bets of the form "candidate a will finish 
ahead of candidate b". Even though the number of such bets is only polynomial in the number 
of candidates, the auctioneer's corresponding matching problem is NP-hard. 

"Pricing Combinatorial Markets for Tournaments" focuses on the market-maker's pricing problem 
in a single-elimination tournament setting. The authors show that the general problem (i.e. 
all possible bets are accepted) is #P complete. However, the authors give polynomial algorithms 
for computing restricted bets of the following types: "team i wins game k", "team i wins game k 
given that they make it to game k", and "team i beats team j given that they face-off".

Several interesting questions for further research come to mind. First, what makes an 
expressive betting language easy to compute? Or perhaps, how can you construct a betting 
language so that it is easy to compute? Second, what is the underlying difference between 
the market maker's problem and the auctioneer's problem? 

1. Computation in a Distributed Information Market, Feigenbaum et al
2. Betting on Permutations, Chen et al
3. Pricing Combinatorial Markets for Tournaments, Chen et al

In [1] the authors introduce a prediction market model in which players are assumed to 
bet truthfully. The focus of this paper is to study the conditions under which the 
market price converges to the correct probability of observing the event underlying 
the security. It turns out that we obtain convergence of the market price to the true 
value of underlying if and only if the payoff is giving by threshold functions of the 
information available to investors. A major strength of this paper is it's use of 
helpful simplifications e.g. uniform distribution of information bits over a binary 
outcome space (0,1); and it's explanation using clever examples, e.g. Example #1 where 
it is shown that two agents can have common priors but different posteriors owing to 
their different information (Example #3 is also an excellent example!).  One weakness 
of the paper is that it does not specify why investors trade, which is an important 
piece of information when it comes to defining the investors motivations and possibly 
can speak to whether not the investor will play truthfully or bluff or be reticent.

1. Why is price defined p = (sum b_i)/(sum q_i)?
2. How do we understand the weights specifically if w < 0? Also what does the condition 
sum x_i *w_i >= 1 correspond to physically?
3. A priori, why would we expect C(x,y) -- the carry bit to be an interesting physical 
quantity?
4. In the paper the authors claim that the result of the paper would hold even if there 
were "super investors" who knew all the information. Is this trivially evident? 
Additionally what would happen if we did not require that each investor have a unique 
bit of information, e.g. two players share the same bit of information (and know, or 
maybe are unaware) that other players possess that same bit of information. It seems 
like having this bit of information diminishes in value given that another player also 
hold this information, is this intuition correct?
5. "The effect of price accuracy and precision": the authors make an interesting point 
here for future research -- investigating the stability of these threshold  influence 
of convergence equilibria, by introducing noise arising from irrational traders. It 
could be however that this model incorporates irrational traders already, given that 
the motivation of players is not specified in the paper: "We sidestep this issue by 
simply assuming that the informed agents will trade (for unspecified reasons)" (pg. 6)
6."Incremental updates": this recommendation for future research would investigate the 
effect of changing the information bits as the system updates. This is quite an 
interesting proposal. A similar proposal would be to increase the total amount of 
information in the market over time and study it's effects on the results presented in 
the paper e.g. during the course of a primary election and a general election we learn 
more about candidates as voters and this undoubtedly affects how we would vote and also 
how we believe our neighbors would vote in the election as well, e.g. Barack Obama's 
relationship with Ayers, Rezko & Rev Wright being revealed at various points in the 
primary and general election campaign; analogously for John McCain, his selection of 
Sarah Palin as his VP in addition to the Keating 5 scandal.


In [2] the authors study markets governed by games in which investors bet on the 
ordering of n outcomes. This general game subdivides into "pair betting" in which 
a player can wager on one candidate beating another; and in "subset betting," which 
centers on a candidate having a given ranking in a range that is a subset of the 
total outcome space. The central result of this paper is that the case of pair 
betting is an NP-hard problem, where as the game involing subset betting can be 
solved in polynomial time. This is a surprising result given that we would naively 
expect the pair betting game to be more tractable than the subset betting, which 
has a potentially larger outcome space. One of my hope for this classes presentation 
is that the speaker elucidates why this is the case. Indeed this is explained in the 
paper, nonetheless, I'm hoping for a intuitive reasoning. I would also appreciate a 
demonstration of how we could construct graphs of the type in Figure 3 to understand 
the games studied in this paper.


In [3] the authors consider pricing of contracts governing "combinatorial markets 
for single-elimination tournaments," e.g. NCAA tournament. As a member of the Duke 
class of 2006, I especially appreciated the reference to Duke in the beginning! The 
case for studying these kinds of markets is made convincingly give that combinatorial 
markets provide a means of connecting securities/bets that are related to each other, 
e.g. the probability that Duke wins the tournament, and the probability that Duke 
beats UConn for the title. A surprising result in the paper relates to how the 
authors condition on the outcome of a game acausally. While, I don't fully understand 
how this arises (Figure #1), it reminds me of a Bayesian game in perfect information, 
where we know the full game tree and work using backwards induction to find the BSPE. 
There is something unnaturally about this concept and I would be curious to see how 
this type of acausal condition compares to causal condition when it comes to 
predicting the outcome of NCAA tournaments. If one were to run an experiment testing 
these two types of condition using NCAA data (from previous brackets filled out: 
"bracketology"), what would be the best way to structure an experiment of this nature?

Aside:
Can we have a section on Computational concepts e.g. NP Hard etc. where we also touch 
on some of the terminology of the stock market and perhaps go over some of the 
logarithmic scoring rules that are so important to the previous 5 papers that we have 
read. This would help people encountering these concepts for the first time to feel 
more at home with them?

Pricing Combinatorial Markets for Tournaments, by Yiling Chen, Sharad Goel, and David Pennock

Betting on Permutations, by Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock

These papers focus on the difficulty of aggregating information about complicated probability 
spaces, like single-elimination tournaments or permutations.  What these probability spaces 
have in common is that their outcome space grows exponentially with the number of parties 
involved (like teams in a tournament, or horses in a race), and thus lend themselves to much 
more difficult algorithmic questions regarding matching interested betters.  I thought that 
one of the main contributions of these papers was in describing the tradeoff between the 
expressiveness of a certain betting language, and the computational complexity of solving its 
respective matching problem.  I think it’s an insightful realization that people could have 
opinions about a wide range of aspects of the eventual outcome, and that the market would 
ideally be able to gather as many of these opinions as possible.  The applications of these 
papers are extremely diverse – to any scenario where people are betting on single-elimination 
tournaments (eg, NCAA), or any competition in which the contestants are ranked.  One assumption 
which was made throughout both of these papers was that the auctioneer would be unwilling to 
take on any risk whatsoever.  Often the optimization problem was the auctioneer attempting to 
maximize worst-case profit.  This seemed like a very strong assumption; it would seem more 
reasonable to me to assume that the auctioneer was attempting to maximize expected profit, or 
something more along those lines.

General pricing problem for tournaments is #P-hard in general, but can be simplified using the 
polynomial-time pricing algorithm when asset types are appropriately restricted to a natural 
betting language. As an example to the tractable market-maker driven combinatorial market, 
single-elimination tournaments is investigated, and the side effect of the expressiveness of 
this natural betting language – introducing inexisting dependencies between games (sequential 
games in a game tree) – is recognized, with a possible solution as further restricting the 
language (however, many real-world pricing problems may not be simply restricted). In the case 
of "match-up winners", the global distribution is constructed from the independent market via 
the Bayesian network, and each trade updates only a single parameter of the Bayesian network. 
These significantly alleviate the computational complexity, and the execution time for traders 
is linear in the number of teams.

"Betting on Permutation" discloses some fairly interesting characteristics of two expressive 
betting languages -- subset betting and pair betting as well as shows that the exponentially 
big linear subset betting program has a corresponding separation problem that reduces to 
maximum weighted bipartite matching and consequently can be solved in time polynomial in the 
number of orders, because for example the existence of a match and the optimal match problems 
can be solved as long as the corresponding separation problem can be reduced to the maximum 
weighted bipartite matching problem. If orders are divisible, an auctioneer can find the 
optimal set and quantity of orders such that his worst-case profit is maximized in polynomial 
time. In contrast, pair betting suffers NP-hard complexity. By reducing to the minimum feedback 
arc set problem, pair betting still leave an auctioneer with an NP-hard optimal matching 
problem. A sufficient condition for the existence of a match for pair betting is proved, but 
necessary conditions are not pretty much identified. Given the greedy algorithm gives poor 
approximation for indivisible pair betting, better approximation for the pair betting markets 
are still an open question. Other possible expressive betting languages for permutation betting 
scenario, which can overcome the side effects and weak points of these mentioned ones, need to 
be explored as well.

Paper A (Betting on Permutations) considers the auctioneer problem of risklessly matching up 
bets when the market uses a call market mechanism.  The authors are really using this scenario 
to examine the issue of designing market mechanisms.  Some design goals are: (1) The language 
should be expressive.  It should be able to reveal as much information as possible for each 
order.  (2) It should be intuitive and easy for traders to use.  For instance, high-level 
description of things might appeal to the natural way of thinking used by most people.  
(3)  It should be computationally feasible for the auctioneer to match up bets.  The central 
concern for this paper is in a way how to balance the trade off between expressiveness of the 
language and computational complexity of the matching problem.

Paper B (Pricing Combinatorial Prediction Market for Tournaments) considers a market run by 
the logarithmic market maker mechanism.  In particular, this paper considers the problem of 
pricing combinatorial markets for single-elimination tournaments.  The main result is a 
polynomial-time algorithm for the pricing problem when only certain types of bets are allowed.  
This is the first example of a tractable market-maker driven combinatorial market.

In general, these two papers leave me with the impression that designing combinatorial markets 
is a very hard problem.  These two papers only examined a tiny fraction of the possible questions 
that could be asked, and we have already had to use so much theoretical arguments.  

Moreover, It seems to me that different types of combinatorial markets might have different 
special structures within them.  Paper B would be an example of taking advantage of some special 
structure of the combinatorial market to find a tractable market mechanism.  So a natural 
direction of future work would be regarding a classification of combinatorial markets and their 
similarities and differences, with special regard to the topic of market mechanism design.  

Paper B also mentioned an important point: The large number of bet types typical in the 
combinatorial setting would require liquidity added by a market-maker in order to aggregate 
information effectively.  Indeed, paper A was mainly concerned with finding a betting language 
that will be computationally feasible for the market maker and they have not tackled the question 
of the effects of different betting languages on information aggregation.  In particular, the 
usefulness of a betting language should in part be quantified by how their usages would help with 
the information aggregation.

One of the central problems of prediction market design is to create markets that both reveal 
substantial amounts of information and do not overwhelm traders with possibilities.  This creates 
a key tradeoff, as gathering additional information requires additional markets, which makes it 
more difficult to establish markets between willing buyers and sellers.  The two papers we examine 
for this week propose optimal solutions for this tradeoff.
 
In “Betting on Permutations,” the authors propose that there are two key types of information that 
market-makers are seeking to elicit in combinatorial markets – markets in which there are many 
candidates competing.  The first is called “pair betting,” and is a bet on whether candidate A beats 
candidate B; the second is called subset betting, and allows betting on the subset of candidates 
that can finish at a particular position, or a subset of positions that a particular candidate could 
end at.  The paper shows that subset betting probabilities can be computed in polynomial time, and 
pair betting is NP-hard.  
 
Similarly, in “Pricing Combinatorial Markets for Tournaments,” the authors propose that the key 
questions that market-makers seek to elicit in tournaments are:  “will team i win game k,” “will 
team i win game k given they make it to game k,” and “will team i beat team j at game k given that 
they face off.”  The paper shows that this set of questions can be answered in polynomial time by 
representing market distributions as a Bayesian network. 
 
Determining an entire joint probability distribution is inefficient and computationally costly, 
typically provides much more information than what market designers seek to elicit.  The papers 
each show that there are much more efficient methods than computing a full joint distribution, 
allowing markets to more effectively reveal relevant information.
 

Betting On Permutations
The main contribution of this paper was to determine how an auctioneer in a permutation betting 
setting can match up bets. The paper deals with whether a match exists, and the computational 
complexity of finding the optimal match. The types of permutation bets include subset betting, 
where bets are placed for whether a certain outcome will fall within a range, or pair betting, 
where bets are placed on the relative order of two candidates in the permutation. The matching 
problem is examined in the divisible and indivisible cases. The results of the paper showed that 
subset betting can be represented as a weighted bipartite graph, and solving for the optimal 
solution in the worst case can be achieved in polynomial time. (Which is the solution to the 
maximum wighted bipartite matching problem). The pair betting solutions were not as easily 
solved and both the optimal indivisible and divisible matching problems were both NP-hard. 
The paper shows how bets normally placed in different categories, ie the winner category, 2nd 
place category, can all be aggregated together to give more information regarding the outcome 
of the permutations. Since this paper shows that the matching problem in subset betting can be 
solved in polynomial time, it is possible for auctioneers/book makers, to combine certain betting 
categories. Any betting market, where the out come of the events are a permutation of candidates, 
can use the results from this article to create a single subset betting scheme. Furthermore, since 
the matching problem that is solved is also giving the auctioneer the optimal profit (no risk), 
they would have incentive to implement such a scheme.
I was unclear on the benefit of finding whether a match existed in pair betting. If one cannot 
find the actual optimal solution, then is the notion of the existence of match of any use? Perhaps 
it can be used by the auctioneer to determine whether to accept a bet, since it will know if a match 
exists?
 
Pricing Combinatorial Markets For Tournaments
The main contribution of this paper is to show how to price a sale of a combinatorial outcome, and 
how the sale affects the overall distribution of the combinatorial market. First the paper shows 
that a tournament outcome type game can be expressed as a Bayesian network. Then a purchase of 
team j winning game g, will only cause the distribution of game g and it's ancestors in the network 
to change. The paper further shows that having this type of distribution calculation was a result of 
the language being used, such as "team i wins game k", which leads to an unexpected dependencies in 
the distribution. To reintroduce the Independence, a language for betting only allowed bets such as 
"team i beats team j, given they face off". This change maintains the over structure of the Bayesian
network, however the arrows are now pointing to the final game. In this manner, when betting occurs, 
only the game at stake's distribution changes.
The paper also shows that pricing the combinatorial market is #P-hard, and presents an approximation 
method in the appendix. This approximation can be used to help implement a market, where combinatorial 
betting can occur as described in the paper. Further more the paper also shows how to place bets that 
are conditional events, ie to bet A|B, is to buy AB, and short ~AB. This can be used by investors to 
make conditional bets in a market where it is not supported.
Finally one project that can be done for this paper, is to implement the approximation tool to see its 
effectiveness in pricing bets. This will be interesting, since we can see if the resulting 
distributions are close to the actual distributions of event outcomes.

Betting on Permutations

In markets, bilateral agreements do sometimes not exist.
However, multilateral agreements may be possible, so it's not a problem.
In our case, traders are going to bet on the outcome of a competition among n candidates.
In order to build on exchange, we need to find two or more that together form an agreeable match.
The problem is the following one :
It's too heavy to compute the n! possible outcomes for the final order. And the probability 
of convergence between two traders, would be very small.
So the solution is to try to divide each order.

We have of course to care about the heaviness, I mean, the time we need to compute it. Here, it 
is a polynomial time.

2 different kinds of bet :
1) the subset betting
2) the pair betting

The drawback with the indivisible bet is that it is an all or nothing order.

If we compare with financial markets :
These markets are not exactly complete. Indeed there are more states than securities. However, the 
dynamic trading allow us to consider these markets as complete.
This is very convenient, because if this hypothesis is true, it means that the "law of one price" 
can be apply. This is the most basic concept in Finance.

The goal here of the researcher is to find a language that :
- reveal as much information as possible
- maintain computational feasibility

The concrete goal is to define the optimal matching problem for the auctioneer.
The existence of a match is a decision problem. It only returns wheter trade can occur without any 
risks to the auctioneer.
In a subset betting market an auctioneer can find the optimal set and quantity of orders to accept 
such that his worst-case profit is maximized in polynomial time IF orders are divisible.
In a pair betting market, the optimal matching problem  is NP-Hard with both indivisible and 
divisible orders.

Pricing Combinatorial Markets for tournaments

Goal of combinatorial markets :
work to more efficiently aggregate information by estimating the entire joint distribution 
of dependent observations.

In the betting language, agents can buy and sell assets of the form "team i wins game k", or 
conditional assets.
Unfortunately, it is impossible to preserve independence in an aggregate information.
Thus, the usual relationships are restored if we only permit bets of the form "team i beats 
team j given that they face off".

The main argument is that the general pricing problem for tournament is #P-Hard.
Here is the framework of the paper :

the general pricing problem for tournament is #P-Hard ---> This is a difficulty----> We need to 
derive a polynomial-time pricing algorithm by restricting to a natural language.
----> As a consequence, dependencies are introduced between games which we would think they are 
independent This is due to the fact that it is impossible to preserve independence in an 
aggregate distribution. ---> If we restrict the language, we can however restore the usual 
independence. This is the strongest point.

1. Betting on Permutations
2. Pricing Combinatorial Markets for Tournaments
 
Both of these two papers address the relations between the expressiveness of the 
bidding language and the computational complexity. In the first paper, the authors 
proposed two types of betting: subset betting and pair betting and discussed about 
two problems: matching and optimal matching problems, correspondently. Each problem 
is investigated in both divisible and indivisible ordered. It is showed that the 
corresponding separation problem, which can be reduced to the maximum weighted 
bipartite matching problem, of the subset betting can be efficiently solved in 
polynomial time by ellipsoid algorithm. The statement is true for the two problems. 
As for the pair betting type, it can be illustrated as a directed graph problem. By 
graph algorithm, it is showed that finding the optimal match in either indivisible 
or divisible pair betting is NP-hard. In the final part of the paper, the sufficient 
condition for the existence of a match for pair betting is stated, and the 
calculation is showed to be in polynomial time. In the second paper, it is showed 
that the general pricing problem for tournaments is NP-hard, and a polynomial-time 
algorithm is derived when applying appropriate restricted betting types. The whole 
deriving process is based on the Bayesian networks.
 
There are several terminologies I want to make clear in these two papers. The first 
is the "minimum feedback arc set problem." The second is the "greedy algorithm." 
Can I have the descriptions of them? In addition, on page 4 in the first paper, 
it says: "since in the worst-case state the auctioneer needs to pay $1 to every 
order in the cycle except one." Why is that? How come there is an exception of 
one? One more question is about the Theorem 3.1 in the second paper. What does 
it mean? I don't fully understand the statement of the theorem. 
 
I think the idea to apply graph algorithms on betting market is very interesting, 
and surprisingly, each type in the paper can find its corresponding graph model 
to solve the matching problem. I am wondering if there is any other application 
of graph algorithms in market. Since graph algorithms are well developed in the 
field of computer science, if we can find other explicitly/implicitly related 
market problems, we can solve these problems efficiently. 

Betting on Permutations (Chen, Fortnow, Nikolova, Pennock)

Pricing Combinatorial Markets for Tournaments (Chen, Goel, Pennock)

We have discussed general prediction markets in previous classes; problems we have seen 
include betting on conditional outcomes, which tends to cause a great deal of blowup in 
the amount of space required, as well as in complexity of finding a match. Both papers 
for Monday focus on specific areas in which conditional betting might be more feasibly 
computed, specifically, permutations and tournaments.

Permutation betting is appropriate for situations in which we might wish to determine 
the relative orders of candidates. The paper discusses two possible questions we might 
ask: in which positions could a given candidate wind up in (subset betting), or which 
of two candidates will finish better in relation to one another (pair betting). 
Surprisingly, attempting to match traders in subset betting, which intuitively seems 
to involve more options, actually reduces to a polynomial-time-solvable problem, while 
doing the same for pair betting proves less computationally tractable; finding the optimal 
pair-betting match is NP-hard, while a greedy algorithm achieves only a O(n^0.5) 
approximation.

Tournament betting is based on the situation of competitors playing single-elimination, 
head-to-head matches until only one remains. The paper models this using market scoring 
rules and attempts to figure out how difficult it is to determine the price of any 
particular security. Although doing this for general betting is #P-hard, we can restrict 
the permissible bets such that the new problem is tractable.

I found the conclusions reached by both papers fascinating; my questions mostly relate to 
how reasonable it is to examine these particular types of scenarios. How generalizable are 
these results? Might there be some way to convert more general cases into instances of 
permutation- or tournament-style scenarios? Most examples that we have seen of the use 
of prediction markets involve a set of outcomes, only one of which can actually occur; 
for many of these, it seems unnatural to try to assign places or ordering to the remaining 
cases. (Reasoning from the suggestion of elections, some fairly natural cases suggest 
themselves: the relative popularity of various options, for example, or the percentage 
of something, be it votes or money or otherwise, assigned to the options.)

As for tournaments, outside of sports and similar competitions, I can think of very few 
situations that involve this kind of progressive elimination. However, can we generalize 
these results beyond single-elimination tournaments to more complicated formats?