INCENTIVE COMPATIBLE TICKET BOOKING SCHEME FOR SPORTING EVENTS

Project Submitted by:

KANCHAN JHA(07/IT/21)
BACHELOR OF TECHNOLOGY INFORMATION TECHNOLOGY Under the Guidance of: SR. SAJAL MUKHOPADHYAY ASSISTANT PROFESSOR INFORMATION TECHNOLOGY

NATIONAL INSTITUTE OF TECHNOLOGY DURGAPUR, INDIA

April 26, 2011

Abstract Here we have investigated the problem of allocating tickets in the big sporting events, where the demand is more than the supply and the competitors for the tickets arrive dynamically. We have proposed a novel auction based truthful online mechanism for allocating ticket in this dynamic environment.

Contents
1 Introduction 1.1 Example 1: Dynamic auction . . . . . . . . . . . . . 1.2 Motivation to the Problem . . . . . . . . . . . . . . . 2 Related Literature 3 Mechanism Design 3.1 Mechanism . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Dominate Strategy . . . . . . . . . . . . . . . 3.1.2 Truthful Mechanism . . . . . . . . . . . . . . 3.1.3 Dominate Strategy Incentive Compatible Mechanism . . . . . . . . . . . . . . . . . . . . . . 3.1.4 Bayes-Nash Incentive Compatible . . . . . . . 3.2 Vickrey Clarke Groves Auction . . . . . . . . . . . . 3.2.1 Preposition 1 . . . . . . . . . . . . . . . . . . 3.2.2 Example 1: . . . . . . . . . . . . . . . . . . . 3.2.3 Vickrey Auction for Multiple Units . . . . . . 3.2.4 Example 2: . . . . . . . . . . . . . . . . . . . 4 Online Mechanism Design 4.1 Challenges of OMD . . . . . . . 4.2 The Model for dynamic setting 4.3 Dynamic Second Price Auction 4.3.1 Theorem . . . . . . . . 4.3.2 Proof . . . . . . . . . . . 4.4 Some Terminology . . . . . . . 4.4.1 Monotonic . . . . . . . . 4.4.2 Critical Value . . . . . . 4.4.3 Lemma . . . . . . . . .
1

3 5 5 8 9 9 9 10 10 10 10 11 11 12 12 13 13 14 15 15 15 16 16 16 16

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

4.5

Competitive Analysis of the online auction . . . . . .

17 18 18 18 19 19 20 20 21 21 23

5 Our Mechanism 5.1 Proposed Mechanism . . . 5.1.1 Example . . . . . . 5.1.2 Theorem . . . . . 5.1.3 Limited misreports

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

6 Experiment and Result 6.1 Pseudo code of Algorithm . . . . . . . . . . . . . . . 6.2 Computational Analysis . . . . . . . . . . . . . . . . 6.3 Result . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Conclusion and Future Research

Chapter 1

Introduction
A market where there is a limited supply of goods, and demand is more than the supply, needs a suitable mechanism to maximize the sellers prot as well as the buyers utility. Ticket booking market are such an example where the demand for the tickets are very high, i.e. n people(henceforth will be calling agents or bidders), give demand for k tickets, as for example, booking tickets in airlines, ticket booking scheme for big railway systems that are as big as Indian railways, ticket booking markets when the hit movies are released for any lm industry, ticket booking markets for any grandslam tournament in tennis or sporting events like a match in English Premiership League or la liga, the IPL cricket tournament in India, exhibit this scenario. In these environments k tickets are available and n number of agents(k < n) try to buy those k tickets. The existing schemes allocates the tickets in rst come rst service basis. As k < n in this environment and tickets are sold in rst come rst service basis many agents do not get the tickets as they have arrived late in the market. Out of the many agents who do not get the tickets, may be willing to pay much more than the agents who are allocated the tickets in rst come rst get basis with a xed price. Up-till now in the ticket booking market we have given importance on the time of the agents when they are arriving i.e. the agents came rst got the ticket but when the demand is very high we can look for alternative ticket booking schemes that will utilize the motivation of the agents to pay more than the xed price. There is an interesting scenario coming up from the sellers perspective i.e. they can earn more in these environments. So the problem here is that k tickets i.e. k resources is to be allocated to n agents and how much extra each agent
3

is willing to pay is there private information. When the data are held privately with the agents mechanism design approach could be the obvious choice. Very few eort, to the best oered knowledge have been made to make an alternative model to maximize the sellers revenue or to allocate the tickets in a socially ecient way[29, 12, 15]. Auctions are a commonly used tool for selling goods in such markets. With the growing computer networks application requirements for such incentive compatible mechanism has arises[8]. There are dierent types of auction has been proposed till now. Standard auction models usually assume that all potential buyers are available at the same time, and that the valuations of buyers do not depend on the time of allocation. In such scenario the designer knows the crowed as well as there bids, is known as static auction or oine auction, VCG auction(known as second price auction)[21, 25] is one IC mechanism, for such scenario, but there are some cases where the designer dont know the future crowed and there bid in advance. The agents come dynamically and as they dont want to wait longer than a specic time therefore they have a denite departure time. The truthful mechanism design for such case known as online mechanism design (OMD)[10, 20, 18] is bit complicated as it is time dependent. The selsh agents tries to maximize there utility, hens they report false massages. Therefore the mechanism designer has to develop such a mechanism which maximizes the sellerss valuation as well as the bidders utility, as well retain the property of truthfulness The mechanism is consist of an allocation rule and a payment rule, which balance the goal of maximizing the sellers revenue and encouraging truthful declaration of bidders by maximizing there utility. As the selsh agents tries to maximize their utility, therefore they try to report false, and manipulate the system solution, which decreases the total valuation of the system therefore introduction of truth telling is a very crucial part of the mechanism, i.e. the mechanism must guarantee truthfulness. Introduction of truthfulness in online domain is even more challenging. One of the solution is truthful or IC direct revelation mechanism, where revelling the true value is the dominant strategy for the agents. Vickrey Auction allocates the goods by maximizing the declared value of allocations and adopts a generalized second price payment scheme to enforce truthfulness
4

in oine setting,but it is not applicable for online demand. Competitiveness of the OMD with optimal mechanism in terms of revenue and social value maximization is another challenge in online era. No constant competitive OM has been proposed till now.

1.1

Example 1: Dynamic auction

Assume Indian Airlines has k tickets to sale, one ticket in per unit of time, customers comes over time, and based on their need for ticket they submit some value as well as their deadline time called their type (a, d, v) where a, d, v are their arrival time, departure time and valuation for ticket respectively. Dierent customers has dierent value for the same ticket, and this value as well as there time duration for which they are in the auction is private to the customer only. The seller wants to maximize his income. This is an example of dynamic mechanism design, all allocations has to be done dynamically and payment also has to be collected before the customer leave. 1.2 Motivation to the Problem

In each of the following ticket booking market we have observed a huge gathering.
English Premiership League

When the six big giants- Manchester United, Chealsea, Liverpool, Arsenal, Manchester City, Everton- play against each other, we observe a jam-packed stadium, in each of the match on an average 30000 crowds are present. The price of the ticket of dierent sections of Manchester United v Everton Match at Old Traord on Saturday, 23 April 2011 15:00 are presented in the table 1.1. The same environment we nd in la liga and Italian serie-a.
Wimbledon Championship

Same as EPL, for Wimbledon championship matches also, there is a craze for the center court tickets. For gentlemen quarter-nals,
5

Table 1.1: Match

EPL Ticket Rate: 2010-2011[1]

Price() 90.25 94.05 284.99 142.50 166.25 118.75 123.50 152.00

Manchester United Section Ocial Everton Fans Tickets Executive Seating(South Stand) South Stand(Managers Stand)Row 2 MSouth Stand East Stand Man UD Section South Stand(Managers Stand)Row 1

seminals and nals there is a huge rush for tickets same for ladies quarter-nals, seminals and nals also. The overall attendance during Wimbledon 2009 was 511,043 whereas it was around 489,946 during Wimbledon 2010, with an daily average of 40,000 in 2009 and 37500 in 2010. And there is a continuous demand for tickets before months.
Indian Premier League(IPL)

In India cricket is like a religion. IPL is the most popular and richest cricket league of the world, which attracts on an average attendance of 57000. The crazy fans of cricket wait for the release of its tickets, and start to grab it from the day of opening. The ticket prices for Royal Challengers Bangalore Vs Mumbai Indians at [Link] Stadium, is given in table 1.2.
Table 1.2: Match

IPL 2010 Ticket Prices/Rates for Bangalore [2]

Price(Rs) 33000.00 55000.00 4400.00 2725.00 1650.00 550.00

KINGFISHER FIRST CORPORATE LOUNGE (J) WHYTE & MACKAY PAVILION (P2) ROYAL CHALLENGE LOUNGE - (E) EXECUTIVE BLACK DOG PAVILION (P1) ROYAL CHALLENGE PAVILION (P3) ROMANOV MEMBERS STAND (M3)

On the release of hit movies

Whenever a movie of any famous director is released or a new series of any famous series movie like Harry Porter, James Bond or Star
6

war releases, people try to get the ticket and watch the rst show. With the introduction of 3D movies in holly-wood the revenue of lm industry started to grow more rapidly. The theatre count for such biggies are so high, and the movies runs for weeks over weeks in the cinema halls. The tickets get booked weeks before the day. In all these markets there is always a rush for the ticket. Therefore they are some good area for the use of mechanism design.

Chapter 2

Related Literature
In resent years, with the involvement of computer applications, networks in trade, like e-commerce, allocation of computational and network resources, the pricing of Wi-Fi at starbucks, are some examples, mechanism design has become an active area of research in economics and computer science. Many works have been done in this area, and dierent kinds of mechanism have been proposed till now. Nisan and Ronen 2001[21] in there studies had aimed about the problem of dealing with selsh agents in concern with prot maximization of the mechanism. The design of online mechanisms has attracted research interest with emergence of the need of dynamic market (see,e.g., a survey by Parkes in (Nisan et al. 2007)). [Link] has proposed the method of mechanism design in online settings with multiple agents and private informations[23, 22], and has presented truthful auction for expiring and limited supply items, and has dened a dynamic BNIC VCG mechanism, assuming the existence of a probabilistic model private informations, and has also proposed a pricing system for Wi-Fi at starbucks in online domain[11]. He has also proposed an ironing based approach[24]. [Link] and [Link] has proposed an IC online auction and has shown its optimal competitive ratio, both in terms of sellers revenue and in terms of the total social eciency obtained[13][14]. Athey and Segal (2007)[4], Bergemann and V lim ki (2010)[5],Said (2008) has also proposed ecient allocation rules[27].Babaio, Blumrosen, and Roth studied the case where supply is not constant[20]. Pavan,Segal and Toikka has studied for an IC mechanism for prot maximization[3]

Chapter 3

Mechanism Design
3.1 Mechanism

A mechanism denes the rule for any system. The design setting includes n number of players ,where n I = {1, 2, ...n}, a set of private informations of the players = {i i I} called their type, a set of strategies Si i. A player can choose any strategy from Si , its priority is to maximize its utility. The mechanism is consist of two elements, M = {(), P } i. Allocation function : B O; where B = {bi i I}, is the input bid vector and O = {j j I} which were allocated the goods. ii. payment function P : B {pi i I} which gives the payment collected from each allocated player. An agent is utility is dened as ui = vi pi where pi is the payment made by i. Value of the mechanism is given by
n

Vmech =
i=1

pi

where is the charge for running the mechanism. The main objective of a mechanism is to provide prot maximization as well as social welfare maximization.
3.1.1 Dominate Strategy

For each agent i and each type i there exist a strategy si which maximizes is utility, no matter what is the strategy of other players.
9

For agent i, a strategy s Si is dominate strategy s Si if si Si [ui (s , si ) > ui (s , si )]

3.1.2 Truthful Mechanism

A mechanism is truthful or strategyful or intensive compatible(IC)if true type revelation is the dominant strategy , i.e. every player reveal its true value. i.e. i si = ti where ti is the true valuation of i.
3.1.3 Dominate Strategy Incentive Compatible Mechanism

M is DSIC if every agent uses its dominant strategy, and truthtelling is the dominant strategy of each player, i.e. mechanism is design such that utility of the agent maximizes when it reports truly without concern of other agents report, and the stochastic environment therefore, vi (i , i , ) pi (i , i , ) vi (i , i , ) pi (i , i , ) for all i , i C(i ) and for all i C(i ).
3.1.4 Bayes-Nash Incentive Compatible

M is a BNIC if truth telling is the dominant strategy if other bidders also report their true value, i.e. expected utility of the agent is maximum when it reports truly given the probability distribution of other agents, i.e. E{vi (i , i , ) pi (i , i , )} E{vi (i , i , ) pi (i , i , )} for all i , i C(i ) and for all i C(i ). 3.2 Vickrey Clarke Groves Auction

The mechanism M = {(), P (O)} denes the allocation and payment rule as:
10

i. Allocation function maps the given types to output function to maximize the output : O s.t. () = argmaxoO
i

vi (i , o) o O

where O is the set of all output functions, and vi is the valuation of i. ii. Payment collected from i is given as, pi (vi o) = 0
j=i vj (o)

+ h(vi )

if i win otherwise

where h(vi ) = the maximum social welfare in the case that player i does not participate and it doesnt depend on i. The utility of i can be given as ui = vi (o) pi (o) = vi (o) ( 0
j=i vj (o)

+ h(vi ))

if i win otherwise

From the Clarke-Pivot Rule we get h(vi ) = maxo O

j=i

vj (o )

The intuitive idea is that the ith player should pay the damage he caused to others. Without him the output would be o, whereas when he participate the output will become o [29].
3.2.1 Preposition 1

VCG mechanism is a truthful mechanism.

For proof consider the paper Algorithmic Mechanism Design of Noan Nisan and Amir Ronen [21]

3.2.2

Example 1:

Let there is one unit of a good to sell and n number of potential buyers. Acc. to VCG mechanism the good is sold to the person for which total output will be maximum, therefore the highest bidder is the obvious choice, Now for the payment, as here say agent i is the highest and j is second highest bidder. Therefore damage caused by
11

i to j = vj , and damage caused to others equals to 0, therefore the payment he has to made is the second highest bid. This is known as Vickrey auction or the second price auction.
3.2.3 Vickrey Auction for Multiple Units

Vickrey auction addresses the allocation problem where the mechanism needs to allocate single indivisible good among dierent possible buyers. But the case where mechanism needs to allocate several units of the goods to several buyers, each buyer is interested in one unit of good, Vickreys second price auction generalizes as[28], i. Allocate k goods to k buyers s.t. total surplus will be maximum, to k highest bidder. ii. Collect a payment equals to k + 1st bid from all the winners.
3.2.4 Example 2:

Suppose there are two identical goods. Suppose bidder 1 has value v1 = 120, bidder 2 has value v2 = 110 and bidder 3 has value 1v3 = 100. In the Vickrey auction, they submit their values, the seller gives 1 and 2 each a single unit, and collect a payment equals to 100 from both of them.

12

Chapter 4

Online Mechanism Design

4.1 Challenges of OMD

A dynamic mechanism has to deal with multidimensional private informations. The dynamic nature of online mechanism, posses some dierent issues from the oine mechanism. Dynamic arrival and departure of agents makes the decisions time dependent. With the valuation of the agent for a good, his time duration also plays an important role in decision making and prot maximization. At a certain time the mechanism doesnt have any information of the future state[26]. There is uncertainty about the available bids and the stochastic environment, therefore generates uncertainty about the future decisions. Below is listed some major issues of OMD: I. With the false valuation, agents can also misreport their arrival and departure time. They may try to eect the decision by reporting false time, and by this way try to increase their utility. For example say there are 2 units of a good and the true types of agent a, b, &c is given as a = (1, 3, 100), b = (1, 2, 80) and c = (1, 3, 40). If we use second price auction in every time unit, then at t = 1 a will win and has to pay 80, at t = 2 b will win and has to pay 40. But to increase his utility, a can misreport his type as a = (2, 3, 100), then at t = 1 b will win and has to pay 40 and at t = 2 a will win and he also has to pay 40, therefore increasing his utility but decreasing the value of the system. II. There is no information available about the type of an agent before he arrives, therefore at a time t decision is made without concern of all the types comes after t. It eects the total e13

ciency of the system in terms of revenue heavily. For example say there is a single unit of a good to sale, at t = 1 two types are available 1 = (1, 2, 100) and 2 = (1, 1, 150) and at t = 2 another type 3 = (2, 2, 200) is submitted. The oine MD will allocated the good to 3 and collect a payment of 200, whereas OMD will allocate it to 2 and collect a payment of 100. Above examples shows that how dynamic nature eects the mechanism. The decisions has to be made in a partial information environment. Also it rises the question of optimality, i.e. how much competitive the mechanism is with respect to the optimal mechanism in terms of revenue as well as social welfare maximization. 4.2 The Model for dynamic setting Our model can be dened as: i. k units of tickets, each ticket per unit time, will be sold. ii. n(where n > k) risk neutral and selsh buyers, these buyers always tries to maximize there utility. iii. T = {1, 2, ....} is the discrete time period indexed by t, in which the auction runs. iv. It is the set of active players present in the auction at time t. v. type of agent i = i (ai , bi , vi ), i It is is private information. ai is the arrival time, di is departure time and vi is its value for the ticket. vi. Vt = {v1 , v2 , ...vi } is the set of all valuations know at the time t by the mechanism. vii. t is the set of all types available at time t. viii. i C(i ) is the set of all possible types of agent i and i C(i ) is the set of valuation of all other buyer except i. ix. si Si is the strategies of i, and si Si is strategy of all players other than i. St is the set of all strategies at time t

14

It is assumed that the bidder can not make its declaration before coming to the auction and makes the declaration of its type as soon as it arrives.

4.3

Dynamic Second Price Auction

It says that, allocate the item to the highest bidder in each time slot and collect the rst highest unassigned bid of the time slot from the winner. If the type of the bidder is (ai , di , vi ) and he wins at ai t di therefore his payment pi = where is the second highest b b bid at the time t[22, 17].
4.3.1 Theorem

Dynamic VCG mechanism is not truthful.

4.3.2 Proof

Let 1 (a1 , d1 , v1 ), 2 (a2 , d2 , v2 ), 3 (a3 , d3 , v3 ) are the type of three bidders and v1 > v2 > v3 such that agent 1 wind in t = a1 and pays p1 = v2 agent 2 wins in next time slot and pays p2 = v3 . Say agent 1 is suciently patient then he can wait for a longer time, then he will try to report false value v1 = v3 + < v2 where << v1 and let agent 2 win rst and then he will win in the next time unit. Therefore his utility increases by v2 (v3 ), therefore bidder can increase its utility by false reporting. This shows that this mechanism is not truthful. Take an example(Example 4) as 1 = (1, 3, 140), 2 = (1, 2, 80), 3 = (2, 3, 40) therefore the mechanism will allocate the good to agent 1 in t = 1 and collect a payment equals to 80, and in t = 2 it will be allocated to agent 2 and a payment of 40 is taken from him, but agent 1 can report false as 1 = (1, 3, 60), therefore in t = 1 agent 2 will be allocated, and in t = 2 agent 1 will be allocated and he has to pay only 40, therefore his utility will increase by ((140-40)-(140-80))=40.

15

4.4
4.4.1

Some Terminology
Monotonic

A deterministic policy is monotonic, if an agent will must win in a arrival-departure period [ai , di ] with type i (ai , di , vi ) if he is winning in more tighter interval [ai , di ] with typei (ai , di , vi ) where ai ai and di di , i.e. (i , i , ) = 1 (i , i , ) = 1 for all i , i C(i ) and for all i C(i ). The monotone property restricts the players to report a false arrival-departure time.
4.4.2 Critical Value

In a deterministic monotonic mechanism M , the critical value for agent i is equals to the minimum bid vmin for the time slot t = [ai , di ], such that he never losses if he bids vi vmin in [ai , di ]. Therefore critical value of agent i can be given as v c t () = vmin if (i , i , ) = 1 for i = (ai , di , vi ) if (i , i , ) = 0

. To insure positive total valuation of the mechanism vi v where v is some x value[22].

4.4.3 Lemma

Critical value for agent i is independent of its bid, and weakly monotonic increasing in tighter arrival-departure intervals.
Proof

Let assume i = (ai , di , vi ) and i = (ai , di , vi ), t = [ai , di ] is a tighter bound over t = [ai , di ], and let us assume v c t (i i ) vi v c t (i i ) therefore (i , i , ) = 1 and (i , i , ) = 0 but this contradict the monotonic policy therefore (i , i , ) = 1 is must but to full this conditionv c t (i i ) vi therefore v c t (i i ) v c t (i i )
16

4.5

Competitive Analysis of the online auction

Competitive analysis measures that how eciently a mechanism can compete with the optimal mechanism[6, 30]. For the adversarial environment it is given by the worst case analysis, but where there is a known probabilistic distribution an average case analysis is performed. However worst case analysis gives more prominent result than the average case analysis as it provides the lower bound on the eciency of the mechanism[4, 16]. In case of online mechanism optimality analysis is very important, as in this case future in unknown and in adversarial environment it is unpredictable[7]. Decisions made without concerning future information, whereas in oine environment the mechanism has all information available at the time of decision making, therefore the oine mechanism can choose the optimal one, but due to lake of all information at any time t online setting may not be able to choose the optimal decision[9]. Therefore the study that how efciently online mechanism can compete oine one is necessary. Consider the value of optimal mechanism is V () and total value of the online mechanism is Vol (), then the mechanism is c-competitive for eciency if E V () Vol () =c

where c 1. The mechanism will achieve at least V /c value of that of the optimal mechanism. For example consider, three bidders want to purchase single unit of a indivisible good, given their type as 1 = (1, 1, 100), 2 = (1, 2, 50), 3 = (2, 2, 150), the oine mechanism will allocate the good to agent three and collect a payment equals to 100, whereas the online mechanism will sell the good to agent one and collect a payment equals to 50, therefore online mechanism is here 100/50=2 competitive.

17

Chapter 5

Our Mechanism
Based on Auction 2 of [Link] literature, we have proposed a ticket booking scheme in dynamic environment. To make the analysis more clear we have taken the scenario of ticket booking for EPL as our example. As the existing scheme for EPL ticket booking is the window system which is a FCFG method, where each agent has to go to the booking center wait in a long queue up-till your turn and then pay a xed price for the ticket and get it. There are some EPL lovers who are willing to get a ticket even at a very high cost. In such scenario to maximize the prot some tickets from every category can be sold through online auction method, where the buyers do not have to wait for a very long period to know the result. 5.1 Proposed Mechanism

Our proposed mechanism states that i. In each period t, allocate the ticket to highest unassigned active bidder, breaking ties at random. ii. Collect a payment equals to the critical value for him at the time of his reported departure.
5.1.1 Example

Consider the above example (Example 4), our mechanism will allocate the good in t = 1 to agent 1 and in t = 2 to agent 2, and will collect a payment equals to 40 from both of them because this the critical value for t = [1, 3]. Therefore reporting false will not increase the utility of agent 1.
18

5.1.2

Theorem

The mechanism is strongly truthful.

Proof

Let us consider the two usual cases: Case 1. i wins with type i , therefore he has to pay v c i , if he reports false type i , and if vi v c i then his utility will not change, but if he will pay vi < v c i he will denitely loss and his utility will be zero. Case 2. i lose with type i , therefore if he tries to submit false type i , and if vi v c i then he will win but his utility will become negative which is not an obvious choice. Therefore truthtelling will become the only choice for the player, hence the theorem.
5.1.3 Limited misreports

We assume that agent reports its bid direct upon arrival, and there is no early arrival and late departure misreports. Now as c our mechanism is a deterministic monotonic one, therefore v[a ,d ] c v[a,d] a a, d d, therefore if the player reports ai > ai or di < di , his payment will increase lowering his utility, therefore the player must report his true arrival-departure time.

19

Chapter 6

Experiment and Result

6.1 Pseudo code of Algorithm

Construct two structures s1 , with elds a, d, v which will store arrival time, departure time and valuation respectively and s2 with the same elds as s1 with an extra eld p to store the payment. Construct an array of s1 as la and that of s2 as lw to store the information of coming bids and the winners respectively. N is the total time duration for which the auction will run, nt is the number of players arrived at time t, 1. initialize list la and lw and an integer variable val 2. for t = 1 to N 3. for j = 1 to nt 4. la = bid 5. sort la in ascending order of v 6. lw = la last insert in decreasing order of d 7. la last 8. lw.p = la last.v 9. for k = lw last to 0 10. if((la[k].a lw last.a && la[k].d lw last.a)||(la[k].d lw last.d && la[k].a lw last.d)) 11. lw last.p = la[k].v 12. val = lw [Link] break 13. for m = 0 to lw last 14. if(lw[m].d t && lw[m].p > val)lw[m].p = val

20

6.2

Computational Analysis

The computational complexity of the algorithm can be given as: line 2. (N ) line 3. (nt ) line 5. (nt log nt ) line 6. (t) line 9. (t) line 13. (t) Therefore total complexity is (N )((nt log nt )+t) = (N nt log nt ) where N = k the number of tickets. Say n is the upper bound of nt i.e. nt n, therefore k = (n) therefore (N nt log nt ) = O(n2 log n) .Therefore complexity of our algorithm can be given as O(n2 log n). 6.3 Result

A programme is written in C to simulate our scheme, bids are submitted dynamically, (for the feasibility of the simulation and to make it resemble with real world situation we have assumed that the bidders value lies between some x minimum and maximum bound which we have assumed min = 90 and max = 3 90,where 90 is the price of some EPL 2010-2011 ticket match mentioned below) and have determined the total income earned in case of xed price method, Vickrey auction and for our proposed mechanism. Fig1 is the graphical representation of our output, where the number of tickets sold are plotted against x-axis and the income is plotted against y-axis. The price is taken in . For our example case we have considered the price of ticket of Manchester United v Everton Match at Old Traord on Saturday, 23 April 2011 15:00 . The price of the Manchester United Section is 90.25 which we have taken as 90 for simplicity of our computation. Let analyze the result for x = 30000 seats the income from window system is y1 = 2700000, from Vickrey auction is y2 = 6270000, and from online auction is y3 = 6065725. The comparative analysis shows that the percentage increase in income from oine auction is ((y2 y1 )/y1 ) 100 = 132.22, and that of from online auction is ((y3 y1 )/y1 ) 100 = 124.65. By taking Vickrey auction as optimal mechanism the competitive eciency of online mechanism is given by y3 /y2 = 1/1.034. Therefore our mechanism is 1.034 ecient with the Vickrey auction.
21

Figure 6.1:

Result of simulation

22

Chapter 7

Conclusion and Future Research

The scheme proposed here opens a new era for prot maximization in ticket booking markets, it may be for any sports event or for airlines or for any special social program. Here we simulated a truthful mechanism for dynamic environment, and analyzed its eciency, which is one more step towards the study of online mechanism design, as well it studies a real-world case, which can now be employed in dierent real-world settings. This project only studies the case of allocation of single unit of ticket at a time, whereas a real-world situation demands more then a single unit at a time[19, 7]. Again in most of the cases we have the past data of the ticket booking markets we have taken as examples in this project. Therefore in our future project we will try to develop a mechanism which will deal with these two aspects, we will consider the advantage of probabilistic distribution of bids and will try to develop a mechanism for multi-unit online auction.

23

Bibliography
[1] [Link] english-premiership-manchester-united-v-everton-tickets/ [Link].

[2] [Link] [3] Alessandro Pavan ;Ilya Segal ; and Juuso Toikka. Dynamic Mechanism Design: Incentive Compatibility, Prot Maximization and Information Disclosure . 2009. [4] S. Athey and I. Segal. An Ecient Dynamic Mehcanism. Mimeo, Stanford University, 2007. [5] Dirk Bergemann and Juuso Valimaki. Ecient Dynamic Allocation with Uncertain Valua- tions, . Cowles Foun- dation Discussion Paper 1584, 2006. [6] Borodin and R. El-Yaniv. Online Computation and Competitive Analysis . 1998. [7] Sourav Chakraborty and Nikhil Devanur. An Online Multi-unit Auction with Improved Competitive Ratio . [8] E. H. Clarke. Multipart Pricing of Public Goods . 1971. [9] [Link] D.C. Parkes, [Link]. Approximately Ecient Online Mechanism Design. TUGBoat, 14(3):342351, 1993. [10] E. H. Gerding; V. Robu; S. Stein; [Link];[Link] and [Link]. Online Mechanism Design for Electric Vehicle Charging. [11] Eric J. Friedman and David C. Parkes. Pricing WiFi at Starbucks Issues in Online Mechanism Design. Technical report, 2002.
24

[12] [Link]. Dynamic Mechanism Design for Online Commerce . Opera- tions Research, 54(2), 291310., 14(3):342351, 2006. [13] R. Lavi and N Nisan. Competitive analysis of incentive compatible on-line auctions. 2000. [14] R. Lavi and N. Nisan. Online ascending auctions for gradually expiring items. ACM-SIAM Symposium On Discrete Algorithms (SODA ), page 11461155, 2005. [15] R. P. McAfee and V. te Velde. Dynamic Pricing in the Airline Industry. 1, 2007. [16] K. Mierendor. Deadlines. Optimal Dynamic Mechanism Design With

[17] K. Mierendor. The Dynamic Vickrey Auction . [18] Konrad Mierendor. Essays on Dynamic Mechanism Design. 2010. [19] Amin Saberi Mohammad Mahdian. Multi-unit Auction with Unknown Supply. ACM Conference on Electronic Commerc, 14(3):243249, 2006. [20] Aaron Roth Moshe Babaio, Liad Blumrosen. Auctions with Online Supply. [21] N. Nisan and A. Ronen. Algorithmic Mechanism Design. The Thirty-First Annual ACM Symposium om Theory of Computing (STOC99), 1999. [22] D. C Parkes. Online mechanisms, chapter 16. Cambridge University Press. [23] D. C. Parkes and Singh. An MDP-based approach to Online Mechanism Design. 17th Annual Conf. on Neural Inf. Proc. Systems (NIPS03), 2003. [24] David C. Parkes and Quang Duong. An Ironing-Based Approach to Adaptive Online Mechanism Design in Single-Valued Domains. [25] Andreas Geiger Paul Dutting. Algorithmic Mechanism Design . Technical report, 2007.
25

[26] R. Porter. Mechanism design for online real-time scheduling . the 5th ACM Conf. on Electronic Commerce (EC04, pages 6170, 2004. [27] M. Said. Auctions with Dynamic Populations: Eciency and Revenue Maximization . Yale University, 2008. [28] Jaya Bhattacharjee D. Ghosh Sajal Mukhopadhyay, Nivedita Mukherjee. An Ecient Auction Based TATKAL Scheme for Indian Railway. International Conference on Innovative Computing and Communi- cation and 2010 Asia-Pacic Conference on Information Technology and Ocean Engineering (CICC-ITOE 2010, 2010. [29] [Link] [Link] [Link], [Link]. An Ecient Multiunit VCG Mechanism for the Ticket Booking Scheme of the Indian Premiere League Cricket Tournament . [30] Andrew V. Goldberg ;Jason D. Hartline ;Anna R. Karlin;Andrew Wright and Michael Saks. Competitive Auctions.

26