extfieldsofstudy:
Computer Science
Mathematics

text:
Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions

We study the communication complexity of combinatorial auctions via interpolation mechanisms that interpolate between non-truthful and truthful protocols. Specifically, an interpolation mechanism has two phases. In the first phase, the bidders participate in some non-truthful protocol whose output is itself a truthful protocol. In the second phase, the bidders participate in the truthful protocol selected during phase one. Note that virtually all existing auctions have either a non-existent first phase (and are therefore truthful mechanisms), or a non-existent second phase (and are therefore just traditional protocols, analyzed via the Price of Anarchy/Stability). The goal of this paper is to understand the benefits of interpolation mechanisms versus truthful mechanisms or traditional protocols, and develop the necessary tools to formally study them. Interestingly, we exhibit settings where interpolation mechanisms greatly outperform the optimal traditional and truthful protocols. Yet, we also exhibit settings where interpolation mechanisms are provably no better than truthful ones. Finally, we apply our new machinery to prove that the recent single-bid mechanism of Devanur et. al.~\cite{DevanurMSW15} (the only pre-existing interpolation mechanism in the literature) achieves the optimal price of anarchy among a wide class of protocols, a claim that simply can't be addressed by appealing just to machinery from communication complexity or the study of truthful mechanisms.

Introduction
In a combinatorial auction, a single designer has m items available for purchase to n buyers. Each buyer has some private valuation function v i (·) : 2 [m] → R + over subsets of items, and the seller aims to partition the items into S 1 ⊔ . . . ⊔ S n so as to optimize the social welfare, i v i (S i ). Much recent work addresses the design of combinatorial auctions, targeting the desiderata of optimality, simplicity (from both a design and strategic perspective), and computational tractability. For instance, the celebrated Vickrey-Clarke-Groves mechansim achieves the optimal social welfare, and is truthful (therefore it is strategically simple: no bidder need consider any strategy except for honest behavior) [Vic61, Cla71,Gro73]. However, in virtually all settings of interest, the VCG mechanism is not computationally tractable, making it unusable in practice.
Much recent work of computer scientists has targeted the design of auctions that are instead approximately optimal, but computationally tractable. One active line of work searches for truthful mechanisms [LS05,DNS05,DNS06,Dob07,DRY11,KV12]. While these results all achieve computational tractability and strategic simplicity in the strongest possible way, the mechanisms are quite involved and therefore don't achieve design simplicity. More importantly, many of these mechanisms can only guarantee approximation ratios that are polynomial in m. When buyers are assumed to be submodular 1 or subadditive, 2 the best achieve ratios just logarithmic in m. A central open problem is the design of computationally tractable truthful mechanisms that guarantee a constant-factor approximation when valuation functions are submodular or subadditive.
Another exciting line of work has shown simple mechanisms that achieve a low price of anarchy at various equilibrium concepts [BR11, PLST12, ST12, ST13, FFGL13]. These results show, for instance, that as long as buyers are subadditive and interact at equilibrium, auctioning each item simultaneously via a firstprice auction achieves half the optimal social welfare [FFGL13]. All of these auctions are computationally tractable and simple in design, and many achieve approximation ratios that are very small constants, via the price of anarchy. However, none of the equilibria at which these results hold are known to arise naturally, and some are even known to be computationally intractable [CP14,DFK15]. 3 Note that even distributed regret minimization may be computationally intractable in these settings, as each buyer has exponentially many (in m) strategies to consider. Therefore, these mechanisms are all extremely complex from a strategic perspective, as buyers would have to reason about exponentially many different strategies in order to approach an equilibrium at which good approximation guarantees hold.
So, truthful mechanisms are strategically simple but achieve poor approximation ratios, and simple mechanisms achieve good approximation guarantees but are strategically complex. As an alternative to pursuing each direction separately, we propose taking ideas from each and introduce interpolation mechanisms. An interpolation mechanism has two phases. In the first phase, buyers participate in some nontruthful mechanism whose output is itself a truthful mechanism. In the second phase, buyers participate in the truthful mechanism selected during phase one. In this language, all truthful mechanisms are interpolation mechanisms with a non-existent first phase, and the simple mechanisms referenced above are interpolation mechanisms with a non-existent second phase.
What might interpolation mechanisms bring to the table that truthful mechanisms and existing simple mechanisms don't? This question is best addressed with an example. Recent work of Devanur et. al. [DMSW15] designs the first interpolation mechanism (although they did not consider this classification), the single-bid mechanism. Phase one of the single-bid mechanism asks each buyer to report just a single real number, b i , as their bid. Phase two visits the buyers one by one in decreasing order of b i , and allows the buyer to purchase any number of remaining items at b i per item (so more items are available to higher bidders, but lower bidders pay less per item). It is easy to see that once the bids are fixed and order determined in phase one, phase two constitutes a truthful mechanism. Note that phase one by itself is extremely limited: buyers are asked to represent their entire valuation function (of which there are doubly-exponentially many) with just log m bits. Unsurprisingly, no protocol using this limited amount of communication can possibly find a good allocation directly. Note also that phase two by itself is also quite limited: an ordering of the bidders along with a single price is set ahead of time, then buyers do as they please. Also unsurprisingly, such truthful mechanisms (that we call single-price mechanisms) can't guarantee any non-trivial approximation ratio. From our perspective, the single-bid mechanism is interesting because it takes two useless mechanisms, neither of which can guarantee a sub-polynomial approximation ratio on even 0/1-additive buyers, 4 and combines them into a mechanism with a price of anarchy O(log m) at correlated equilibria when buyers are subadditive. Importantly, because the per-bidder communication in phase one is only logarithmic, each bidder can actually implement any standard regret minimization algorithm over possible bids in poly time. Therefore, the mechanism achieves design simplicity, strategic simplicity, and computational tractability. The main open problem left following their work is the design of mechanisms that achieve these three desiderata with a constant price of anarchy.
Interpolation mechanisms are a natural avenue to tackle this problem, and therefore lower bounds on their capability are important to guide their research. Following Devanur et. al.'s work, questions arose such as: what if bidders make a constant number of bids instead of just one? What if the posted prices are different for each item? What if we restrict attention to a much smaller class than subadditive bidders? What if we consider price of stability instead of anarchy? Surprisingly, a subset of our results shows that none of these relaxations suffice to (significantly) beat the O(log m) bound attained by the single-bid mechanism. The remainder of our results show that lower bounds known for various classes of truthful mechanisms also extend to interpolation mechanisms with little first-phase communication. One should interpret these results not as claiming that the limits of interpolation mechanisms have already been reached, but as guiding future research towards other classes of truthful mechanisms (specifically, we identify posted-price mechanisms as a natural candidate in Section 1.2).

Our Results
In addition to formally identifying interpolation mechanisms as an important avenue of study, we identify their connection to the price of anarchy and stability, and provide numerous lower bounds. Our lower bounds consider interpolation mechanisms where the phase-two mechanism comes from a certain class. The goal of these lower bounds is to identify which classes of mechanisms are incompatible with interpolation (MIR and value-query, below), and for which classes of mechanisms the limits have already been reached (singleprice and non-adaptive posted-price, below) to guide future research towards others (adaptive posted-price mechanisms, Section 1.2). Our results all lower bound the amount of first-phase communication necessary to find a suitable phase-two mechanism from the desired class. Note that even for truthful mechanisms, no unconditional communication lower bounds are known outside of artificial settings, so it is outside the scope of this paper to suddenly provide unconditional lower bounds in the strictly more general setting of interpolation mechanisms.
Price of Anarchy and Price of Stability. Any bidder participating in an interpolation mechanism with O(log m) first-phase communication per bidder can run any standard regret minimization algorithm in poly-time. Because bidders need not strategize over their phase-two behavior, they need only optimize over their possible strategies in phase one, of which there are at most poly(m). Therefore, price of anarchy bounds for correlated equilibria of interpolation mechanisms with logarithmic first-phase communication have some extra bite, as bidders can be reasonably expected to converge to a correlated equilibria and the bound will hold. We call such mechanisms a priori learnable, and formally define this in Section 2.
Because we lower bound the first-phase communication complexity, we not only lower bound the achievable price of anarchy by such mechanisms, but also the price of stability. In this context, our bounds are strong in the sense that they don't rely on equilibrium behavior of the buyers, and apply no matter how the buyers interact. Prior to this work, Roughgarden provides the only general approach for proving price of anarchy lower bounds [Rou14], and no general approach was known for price of stability at all. Our approach is similar to Roughgarden's in the sense that both identify settings in which communication lower bounds imply "the right" price of anarchy lower bounds. Still, our approach differs signifcantly as Roughgarden's work specifically targets equilibrium concepts that are not efficiently computable, and doesn't apply to price of stability. We discuss formally the connection between first-phase communication bounds and price of anarchy/stability in Section 2.
Single-Price Mechanisms. A single-price mechanism fixes a price p i for buyer i, then visits the buyers one at a time and offers buyer i any remaining items for p i each. Devanur et. al.'s single-bid mechanism has O(log m) first-phase communication per bidder, and obtains a price of anarchy at correlated equilibria of O(log m) whenever buyers are subadditive. We show in Section 3 that even when buyers are just additive, no amount of first-phase communication suffices for an interpolation mechanism whose second phase is a single-price mechanism to obtain an approximation ratio o(log m/ log log m). Note that this significantly improves a lower bound shown in [DMSW15], which simply proved that the single-bid mechanism itself could not guarantee an approximation ratio o(log m/ log log m).
Non-Adaptive Posted-Price Mechanisms. Non-adaptive posted-price mechanisms generalize single-price mechanisms by allowing the mechanism to set a price p ij for buyer i to purchase item j. The mechanism still visits the buyers one at a time, and allows buyer i to purchase any remaining items at the designated price. We show in Section 4 that even when buyers are just additive, any interpolation mechanism whose second phase is a non-adaptive posted-price mechanism and guarantees an o(log m/ log log m) approximation ratio has Ω(m 1−ǫ ) first-phase communication per bidder, for all ǫ > 0. Therefore, the single-bid mechanism cannot be improved by restricting attention to a smaller class of valuations, restricting attention to a smaller class of equilibrium concepts, setting different prices for different items, or allowing significantly more (but still sublinear) first-phase communication.
Maximal-In-Range, Value Query, and Computationally Efficient Mechanisms. Several recent works have identified lower bounds on approximation ratios that can possibly be obtained by these classes of mechanisms, which we will define in the corresponding sections. We extend these lower bounds to mechanisms with low first-phase communication that induce a mechanism in one of these classes. In Section 5, we extend techniques of Daniely et. al. based on generalizations of the VC-dimension [DSS15], and in Section 6, we extend the techniques of Dobzinski and Vondrak based on structured sub-menus [Dob11,DV12].

Discussion and Future Work
Motivated by impossibility results associated with truthful mechanisms, and concerns regarding the strategic simplicity of existing simple mechanisms analyzed via price of anarchy, we propose the study of interpolation mechanisms. Using this new notion, we show that the single-bid mechanism of Devanur et. al. [DMSW15] is essentially optimal for its class, even subject to quite significant generalizations. We note that, prior to our work, it was unclear even how to define a class containing this mechanism, let alone prove lower bounds against mechanisms "like this." We also identify several classes of truthful mechanisms that are incompatible with interpolation in the sense that low first-phase communication doesn't allow for better approximation guarantees than no first-phase communication.
Our work identifies adaptive posted-price mechanisms (where the mechanism may choose what prices to set based on what items have already sold) as an intriguing class of mechanisms to study with interpolation, as none of the lower bounds from this work apply. Furthermore, Dynkin's secretary algorithm [Dyn63] immediately implies an adaptive posted-price mechanism that gets a 1/e approximation for additive bidders, so mild adaptations of our lower bounds for non-adaptive posted-price mechanisms are unlikely to apply. Can an interpolation mechanism with O(log m) per bidder first-phase communication and an adaptive postedprice mechanism for its second phase guarantee a constant price of anarchy?
Our results also fit into a line of work designing combinatorial auctions with low price of anarchy via valuation compression [DFP11, HS13, DFP14, BLNL14]. These mechanisms restrict the allowable valuation reports from buyers to a space where the VCG mechanism is computationally tractable, even though the buyers may have much more complex valuations. In our context, these mechanisms still consist of just a first phase, and therefore rich valuation classes (like submodular, subadditive, or even just additive) cannot be compressed all the way down to a class that can be indexed with just O(log m) bits without super-constant loss. On this front, interpolation mechanisms provide a new style of two-phase valuation compression where this level of compression may be attainable.
Additionally, many existing truthful auction formats are naturally parameterized by parameters that are assumed to be known to the designer (e.g. buyers' budgets in a clinching auction [GML12, GML13,GML14] or buyers' interest sets in single-minded combinatorial auctions). Our framework provides a natural extension of such mechanisms to settings where these parameters are instead private. For instance, one could take any clinching auction where the budgets are assumed to be known, and add a first phase where buyers are asked to report their private budget. It would be very interesting to analyze the price of anarchy of such interpolation mechanisms, as these parameters are often not public knowledge in practice.
Finally, while we were motivated to study interpolation mechanisms for welfare maximization in combinatorial auctions, interpolation will also be useful in any setting where unfortunate lower bounds are known for truthful mechanisms but strategic simplicity is still a concern. A natural generalization of the presented setting, which we omit due to space constraints, is a model where rounds of truthful and non-truthful interaction might be interleaved (instead of having all non-truthful interaction come before all truthful interaction). It would be interesting to understand the power and complexity of such mechanisms in settings beyond necessarily just combinatorial auctions.

Preliminaries
In a combinatorial auction, the designer has m items to allocate to n buyers. Each item can be allocated to at most one buyer, and the buyers can be charged any non-negative price. Agents have a valuation function v i (·) mapping subsets of items to non-negative real values. Agents are quasi-linear, meaning that their utility for receiving items S i and paying price A mechanism is truthful if it is in every buyer's interest to tell the truth, no matter their type. Formally, if p i ( v) denotes the expected price paid by buyer i when the reported types are v, and S i ( v) denotes the (possibly random) set that buyer i receives, then we must have: We define various classes of mechanisms and subclasses of valuation functions within the following sections.

Interpolation Mechanisms
An interpolation mechanism is a communication protocol with two phases. The first phase is non-truthful, and the output is a truthful mechanism. The second phase is the truthful mechanism output in phase one, and the output is an allocation of items and prices to charge.
Definition 1. (Interpolation Mechanism) Let M denote the space of all truthful mechanisms for a combinatorial auction setting. Note that the output space of all M ∈ M is an allocation of items and charged prices. An interpolation mechanism provides a communication protocol, P , that outputs a mechanism M ∈ M based on the transcript of P . In phase one, bidders participate in the protocol P . In phase two, bidders participate in the truthful mechanism output by P during phase one. After phase two, the items are allocated and prices charged according to the bidders' play of the phase two mechanism. If the second phase of an interpolation mechanism always lies inside a restricted class C of truthful mechanisms, then we call this a "C interpolation mechanism." Our main results provide lower bounds on the per-bidder communication necessary during the first phase in order to possibly select a good truthful mechanism for the second phase. Formally, we say that an interpolation mechanism guarantees an approximation ratio of c when buyers have types in V if for all i, v i ∈ V, there exists a phase-one strategy for buyer i, s i (v i ), such that for all v ∈ V n , if buyers use the strategies s i (v i ) during phase one, and report truthfully during phase two, the resulting allocation obtains a 1/c-fraction (in expectation) of the optimal social welfare for v.
Note that this approximation guarantee is not tied to any particular equilibrium concept. It is strictly easier to design an interpolation mechanism that guarantees an approximation ratio of c than one that has a price of anarchy/stability of c (stated formally in the following section), so lower bounds on the approximation ratio imply lower bounds on attainable price of anarchy/stability.
Of specific interest are interpolation mechanisms that have poly(n, m) total communication, and only require bidders to consider poly(m) strategies. Note that bidders must, at least a priori, consider every possible strategy during phase one (but need only consider telling the truth during phase two). So in order to guarantee that bidders have at most poly(m) strategies to consider, the first phase must be especially simple.
Definition 2. (a priori learnable) We say that an interpolation mechanism is a priori learnable if the first phase contains a single simultaneous broadcast round of communication, and the per-bidder communication is O(log m). 5 Observation 1. Any buyer can run any standard regret minimization algorithm (for instance, Multiplicative Weights Updates) over her strategies in an a priori learnable interpolation mechanism in time/space poly(m). Therefore, a correlated equilibrium of any a priori learnable interpolation mechanism can be found in polytime, and correlated equilibria arise as the result of poly-time distributed regret minimization.
Proof. As the second phase is a truthful mechanism, each buyer need not strategize over possible actions during the second phase. Therefore, buyers should always play their dominant strategies during phase two and need only learn over their strategies during phase one; this can only decrease their regret. As phase one is a normal form game and there are only poly(m) such strategies, each buyer can just run a standard regret minimization algorithm in time/space poly(m). If each buyer does this, their play will converge to a correlated equilibrium [FV97,HMC00]. ✷ Note that price of anarchy bounds for correlated equilibria in a priori learnable interpolation mechanisms have more bite than price of anarchy bounds for solution concepts that don't arise naturally. The single-bid mechanism, for instance, is a priori learnable.

Connection to Price of Anarchy and Stability
The main application of our first-round communication lower bounds is on the price of anarchy or stability achievable for any a priori learnable interpolation mechanism. Price of anarchy/stability is typically defined for the social welfare, but has recently been considered also for revenue [HHT14], and is well-defined for more general objectives as well. The observation below holds for any objective, but we state it for social welfare in combinatorial auctions since that is the focus of this paper.
Definition 3. Let E denote any solution concept (i.e. Nash equilibria) for the mechanism M , and V denote any set of valuation functions. Then the price of anarchy (PoA) and Price of Stability (PoS) of M with respect to E when buyers have valuations in V are: Observation 2. If an interpolation mechanism has price of anarchy or price of stability α at any nonempty equilibrium concept, then that same interpolation mechanism guarantees an approximation ratio of α. Therefore, lower bounds on the approximation ratios of interpolation mechanisms imply lower bounds on the possible price of anarchy/stability obtainable by those same mechanisms.
Proof. Just sample each strategy s i (v i ) from any equilibrium where the price of anarchy/stability holds. This strategy immediately witnesses that the interpolation mechanism guarantees an α-approximation. ✷

Single-Price Mechanisms
In this section, we consider single-price mechanisms. A single-price mechanism visits bidders one at a time and offers the current bidder the opportunity to buy any number of remaining items at p i per item. The main result of this section is the following: Theorem 3.1. There exist profiles of additive buyers for which the best single-price mechanism achieves an Ω(log m/ log log m)-approximation. Therefore, for all C > 0, no single-price interpolation mechanism with first-round communication C per bidder obtains an o(log m/ log log m)-approximation on all profiles of additive buyers. This holds even when each buyer values each item at an integer between 1 and m.
Proof. Consider the following example. There are b buckets of items (indexed from 0 to b − 1), with bucket i containing c b−i items, for some constants b, c to be set later. The value of (almost) every bidder for each item in bucket i is c i . Each item is "special" for exactly one bidder, who values it instead at c i+1 . Each bidder has exactly c b−i /n special items in bucket i. It is clear that the optimal allocation in this instance is to award each bidder each of their special items, which has welfare bc b+1 . Now consider any single-price mechanism, with prices p 1 , . . . , p n . We want to consider when bidder i will get his special items in bucket j. Notice that bidder i's special items in bucket j are available to her if and only if p k > c j for all k < i. Bidder i will choose to purchase her special items in bucket j if and only if p i ≤ c j+1 .
So for each bucket j, let i j denote the first bidder for which p i ≤ c j (w.l.o.g. such a bidder exists as it is always optimal to set p n = 0), and n j denote the number of bidders before i whose price is at most c j+1 . Then the number of bidders who get their special items in bucket j is exactly n j + 1. So the total number of pairs (i, j) such that bidder i gets her special items in bucket j is exactly b + b j=1 n j . It's also clear that b j=1 n j ≤ n, as p i ∈ (c j , c j+1 ] for at most one j. So the number of pairs (i, j) such that bidder i gets her special items in bucket j is at most b + n.
Finally, observe that if the number of pairs (i, j) such that bidder i receives her special items in bucket j is x, then the welfare is exactly xc b+1 /n + (bn − x)c b /n, which achieves at most a ( x nb + 1 c )-fraction of the optimal welfare. Plugging in for x = n + b, this is a 1/(1/n + 1/b + 1/c)-approximation.
Setting b = c = n provides an example with m = Θ(n n ) items (so n = Θ(log m/ log log m)) for which no single-price mechanism obtains an o(n) = o(log m/ log log m)-approximation. ✷ Notice that the impossibility above is quite strong: no amount of communication suffices to find a good single-price mechanism (because it is possible that one simply doesn't exist). This greatly strengthens an inapproximability result of [DMSW15], which just shows that their specific procedure (the single-bid mechanism) for selecting one doesn't obtain a better approximation ratio.
Corollary 3.1. No single-price interpolation mechanism obtains a price of anarchy or price of stability o(log m/ log log m) at any solution concept that is guaranteed to exist on all profiles of additive buyers.

Non-Adaptive Pricing Mechanisms
In this section, we consider non-adaptive posted-price mechanisms. A non-adaptive posted-price mechanism orders the bidders however it wants (possibly randomly), then selects a price vector p i for each bidder i. The bidders are visited one at a time, and offered the opportunity to purchase any subset S i of remaining items for price j∈Si p ij . The main result of this section is below. Our proof uses the probabilistic method, which has also been used in [DK15] to prove price of anarchy lower bounds.
Theorem 4.1. Any non-adaptive posted-price interpolation mechanism that guarantees an approximation ratio of o(log m/ log log m) on all profiles of additive bidders has first-round communication at least m 1−ǫ per bidder, for all ǫ > 0. This holds even when each buyer values each item at an integer between 1 and m.
Proof. We will use the probabilistic method to define a set of profiles of additive bidders such that no nonadaptive posted-price mechanism does well on much of the set. Let each v j (the vector of values of each bidder for item j) be drawn independently, and be equal to a random permutation of (c k+1 , c k , . . . , c k ) with probability 1/c k for each k ∈ {1, . . . , b}, and (0, . . . , 0) with probability 1 − b k=1 1/c k for constants c ≥ 2, b to be set later.
It is clear that the expected maximum value per item is exactly bc, so the expected optimal welfare is bcm. Consider now any non-adaptive posted-price mechanism, and restrict attention to prices for item j. For each k, let i k denote the first bidder such that p i k j ≤ c k , and n k denote the number of bidders before i k such that p ij ≤ c k+1 . Then the probability that this mechanism awards the item to the "special" bidder when the profile is a random permutation of (c k+1 , c k , . . . , c k ) is exactly 1+n k n . Therefore, the expected welfare of this posted-price mechanism, just considering contributions from item j, is b k=1 c(1 + n k )/n + (n − 1 − n k )/n. It is also clear that b k=1 n k ≤ n, as each p ij ∈ (c k , c k+1 ] for at most one k. So the expected welfare per item of this non-adaptive posted-price mechanism is at most cb/n + c + b, and the total expected welfare is at most (cb/n + c + b)m.
Because the values for each item are drawn independently, the optimal welfare and the welfare of this non-adaptive posted-price mechanism is the sum of m independent random variables, each in [0, c b+1 ]. Therefore, we can use the Chernoff bound to bound the probability that these random variables deviate from their expectation.
Set b = c = n. Then the probability that the welfare of any fixed item pricing exceeds 2(3n)m is at most e −m/n n . The probability that the optimal welfare is less than (n 2 m)/2 is at most e −m/(4n n−1 ) . So consider any set P of at most 2 m/n n different non-adaptive posted-price mechanisms. Taking a union bound over all mechanisms M ∈ P , we see that with non-zero probability, the welfare of M is at most 6nm while the optimal welfare is at least n 2 m/2. Therefore, there exists a profile of additive bidders for which no mechanism in P is an n/12-approximation.
If the first-round communication of each player is at most m/n n+1 , then there are only 2 m/n n possible transcripts from the first round, and therefore only 2 m/n n different non-adaptive posted-price mechanisms can possibly result. By the above reasoning, this implies the existence of a profile for which every possible mechanism selected (and therefore every outcome selected by the protocol) does not obtain an n/12approximation. For any fixed ǫ, setting m = n n/ǫ yields an instance with n = Θ(ǫ log m/ log log m) that requires m 1−ǫ first-round bits per bidder to optain an n/12 approximation. ✷ Interestingly, there is always a non-adaptive posted-price mechanism that allocates the items optimally: set p ij = max i ′ =i v i ′ j for all i, j. Each v i ′ j can be communicated with log m bits, so the entire mechanism can be found with m log m bits of communication per bidder. The theorem states that sublinear communication doesn't suffice to find a very good mechanism.
Corollary 4.1. No a priori learnable non-adaptive posted-price interpolation mechanism obtains a price of anarchy or price of stability o(log m/ log log m) at any solution concept that is guaranteed to exist on all profiles of additive buyers.

Maximal-In-Range Mechanisms
In this section, we consider maximal-in-range (MIR) mechanisms.
A maximal-in-range mechanism selects some subset F ′ ⊆ 2 [n]×[m] of feasible allocations, and always selects an outcome in arg max x∈F ′ {Welfare(x)} (where the welfare is computed with respect to the valuation profile). In other words, a maximal-in-range mechanism always optimizes welfare exactly over a restricted set of possible outcomes. We provide a mild generalization of the techniques of Daniely et. al. [DSS15] that apply to MIR interpolation mechanisms rather than just MIR mechanisms. With these new techniques, we show the following theorem. All proof details are in Appendix B for space considerations.
Theorem 5.1. For all δ > 0, the following hold: • Assuming N P P/poly, any poly-time (runs in time poly(n, m)) MIR interpolation mechanism that obtains an approximation ratio m 1/3−2δ/3 whenever buyers are single-minded 6 has first-round communication at least m δ per bidder.
• Assuming N P P/poly, any poly-time (runs in time poly(n, m)) MIR interpolation mechanism that obtains an approximation ratio m 1/3−δ /5 whenever buyers are capped-additive 7 has first-round communication at least m 1/3 per bidder.
• Any poly-communication (total communication poly(n, m)) MIR interpolation mechanism that obtains an approximation ratio m 1/3−δ whenever buyers are submodular 8 has first-round communication at least m 1/3 per bidder.
Corollary 5.1. Assuming N P P/poly, no a priori learnable, computationally efficient MIR interpolation mechanism obtains a price of anarchy or price of stability o(m 1/3 ) at any solution concept that is guaranteed to exist on all profiles of single-minded buyers, capped-additive buyers, or submodular buyers.

Value Query and Computationally Efficient Mechanisms
In this section, we consider value query mechanisms and arbitrary computationally efficient mechanisms. A mechanism is a value query mechanism if it only interacts with buyer valuations with queries of the form: "what is your value for set S?" A computationally efficient mechanism is any mechanism that terminates in polynomial time in m, n, and the space it takes to describe a valuation function. Note that for single-minded and capped-additive functions, the space required is also poly(m, n), but for submodular functions the space required may be larger. We provide a mild generalization of techniques of Dobzinski and Vondrak [Dob11,DV12] that apply to interpolation mechanisms rather than just truthful mechanisms. With these new techniques, we show the following theorem. All proof details are in Appendix C for space considerations.
Theorem 6.1. For all δ > 0, the following hold: • Any value query interpolation mechanism that makes at most e m 1/3 10m 8 − 1 queries that obtains an approximation ratio m 1/3−δ /20 whenever buyers have submodular valuations has first-round communication at least m δ per bidder. • Assuming RP = N P , any computationally efficient interpolation mechanism that obtains an approximation ratio m 1/3−δ /20 has first-round communication at least m δ per bidder.
Corollary 6.1. Assuming RP = N P , no a priori learnable computationally efficient mechanism or a priori learnable value query mechanism that makes at most e m 1/3 10m 8 − 1 queries guarantees a price of anarchy or price of stability o(m 1/3 ) at any solution concept that is guaranteed to exist on all profiles of submodular buyers.

A A Second Round is Necessary
In this section, we show that indeed something is gained by including a second round, if the goal is a priori learnability. Specifically, we show that just a low amount of first-round communication (but no truthful communication) can't beat a poly(m)-approximation. One should contrast this with the singlebid mechanism of Devanur et. al. which shows that exponentially less first-round communication plus a single-price mechanism obtains an O(log m)-approximation.
Theorem A.1. For all ǫ > 0, consider any (not necessarily truthful) protocol for combinatorial auctions with communication complexity O(m ǫ ) per party. Then this protocol does not guarantee an approximation ratio better than m 1/2−ǫ on all instances with 0/1-additive buyers. This bound holds against non-deterministic and randomized protocols as well.
Proof. Let n = 2m 1/2−ǫ . Consider the following random valuation: Each item interests only one bidder chosen uniformly randomly and also independently from other items. Each bidder values items they are interested in at 1, and all others at 0. For any fixed allocation, let's define X i to be the indicator variable that item i is assigned to the bidder who is interested in this item. Then the total welfare of this allocation can be defined as X = n i=1 X i . It's easy to see that E[X] = m/n, and that the optimal allocation has welfare m. By Chernoff bound, we have Since each party communicates only O(m ǫ ) bits, the mechanism uses at most 2 n·O(m ǫ ) different allocations. And from the above probabilistic argument, we know that each allocation can only obtain a m 1/2−ǫ with probability e −m 1/2+ǫ /6 on the random valuations described above. For all ǫ > 0, when m is large enough, 2 n·O(m ǫ ) × e −m 1/2+ǫ /6 < 1/m. We know that the protocol can't possibly get an m 1/2−ǫ approximation on all additive valuations. Because we only counted the number of transcripts, this holds against non-deterministic protocols as well.
In fact, we have also shown that the probability that any set of 2 n·O(m ǫ ) allocations achieves welfare larger than m 1/2+ǫ is at most 1/m. Clearly, no allocation can achieve welfare larger than m, so we have also shown that the expected welfare of any set of 2 n·O(m ǫ ) allocations is at most m 1/2+ǫ on this distribution as well. Now we can apply Yao's minimax principle to claim that no randomized protocol beats welfare m 1/2+ǫ on all instances generated by our probabilistic construction. Therefore, no randomized protocol guarantees a m 1/2−ǫ -approximation on all instances of 0/1-additive buyers. ✷

B Omitted Proofs from Section 5
In this section, we provide a proof of Theorem 5.1. Our proof technique is based on techniques developed in [DSS15]. In [DSS15], they present a generalization of VC dimension and used it to unify all previous inapproximability results for maximal-in-range mechanisms. Proof overview: We will first show that if the first-round communication C ≤ m δ , then the auctioneer is choosing a truthful mechanism from exponentially many but not too many maximal-in-range mechanisms. And then we generalize the results in [DSS15] to show that if the mechanism is potentially running a bounded number of maximal-in-range mechanisms and this mechanism has good approximation ratio, then one of the maximal-in-range mechanism it uses will shatter a large set. Finally, we will use results from [DSS15] to show that shattering a large set implies inefficiency in computation or communication by reducing from hard problems.
The results of Daniely et. al. are not such that we can apply them in a black-box manner, and we must actually introduce and mildly generalize their techniques. We do so below.

B.1 Notations
Definition 4. ( [DSS15]) (Duplicate Allocation) A d-duplicate allocation of a set X to indices Y is a collection {S y } y∈Y of subsets of X such that every x ∈ X belongs to at most d subsets from {S y } y∈Y . We use P d (X, Y ) to denote the set of all d-duplicate allocations. If d = 1, we will use P (X, Y ).
∃Y a ⊆ Y of size k and the following holds: For each a ∈ A, choose y a ∈ Y A arbitrarily, then no matter how you choose these y a 's, we can find f ∈ H such that ∀a ∈ A, f (a) = y a . We define Dim k (H) as the maximal cardinality of a k-shattered set.
In other words, H has the α-containment property if for any possible allocation, S, there is an allocation T in H such that rat least a 1/α fraction of players who get something in S get in T at least what they got in S.

B.2 Proof
We first prove the following simple lemma to show that if the first-round communication C ≤ m δ per bidder, the protocol is choosing a truthful mechanism from exponentially many but not too many maximal-in-range mechanisms. It is easy to get the following observations: Observation 3. If a protocol has first-round communication m δ per bidder, then the number of possible truthful mechanisms that can be selected for phase two is at most 2 n·m δ .
It is easy to get the following observation from the definition of MIR mechanisms: Observation 4. If phase two is choosing from t MIR mechanisms with sets of allocations H 1 , ..., H t , then the resulting no matter how phase one selects an MIR mechanism, the combined interpolation mechanism does no better than the MIR mechanism with set of allocations H = ∪ t i=1 H i . By this observation, we will start to consider the MIR mechanism with set of allocations H. We are going to show that if the MIR mechanism with set of allocations H has good approximation ratio, then one of the maximal-in-range mechanism among H 1 , ..., H t will shatter a large set. We need the generalization of the Sauer-Shelah lemma from [DSS15]: For every H ⊆ Y X , and every 2 ≤ k ≤ |Y |, We will generalize Theorem 2.6 and Theorem 2.8 in [DSS15] as the following two theorems. . If H has the m 1−ǫ -containment property, then there exists i ∈ [t] and a shattered pair S ⊆ X, A ⊆ Y of sizesΩ(m 3ǫ/4 ) and m ǫ/4 , such that the pair S,A is shattered by H i S,A .
Proof. Let k = m ǫ/4 . Let {T y } y∈Y to be a partition that is uniformly randomly chosen from all the partitions that give m n = m 3ǫ/4 items to each index. Let A to be chosen from all the sets of indices of size k uniformly randomly and independently from {T y } y∈Y .
Since H has the m 1−ǫ -containment property, there is a partition {S y } y∈Y ∈ H such that T y ⊆ S y for at least k y's. We call these y's are covered. The probability that T y ⊆ S y for all y ∈ A is ≥ 1 ( n k ) By linearity of expectation, we can find a fixed set A of k indices such that with probability ≥ m −k (over the randomness in {T y } y∈Y ), A is covered. We fix this A. By linearity of expectation again, there exists a set S ⊂ X and |S| = m ǫ such that if we only count A as covered when ∪ y∈A T y = S, the probability that A is covered is still ≥ m −k . Fix this S. If a function f : S → A is uniformly randomly chosen from all functions with the property that ∀i, j ∈ A, |f −1 (i)| = |f −1 (j)|, then with probability ≥ m −k , f ∈ H S,A . The number of these functions is k m ǫ · m −ǫk , m −ǫk comes from the fact that a random function from S to A will satisfy ∀i, j ∈ A, |f −1 (i)| = |f −1 (j)| with probability m −ǫk .
Then we have |H S,A | ≥ k m ǫ · m −k · m −ǫk . By an averaging argument, there exists i ∈ [t], such that |H i S,A | ≥ 1 t · k m ǫ · m −k · m −ǫk . Fix this i. By the generalized Sauer-Shelah Lemma above, we have (note that we are using just the first inequality in the Theorem statement, and that |Y | = k) Then we have Proof. We use the following lemma from [BDF + 10] Lemma B.1. Assume H ⊆ P (X, Y ) has the ( n 1+2k )-intersection property. There exists a set S ⊆ X such that |S| ≥ km/n and |H S,Y | ≥ (1 + k) km/n . By this lemma, there is a set S ′ ⊆ X such that |S ′ | ≥ km/n and |H S ′ ,Y | ≥ (k + 1) km/n . By averaging argument, there exists i ∈ [t] such that |H i S ′ ,Y | ≥ 1 t · (k + 1) km/n = (k + 1) −m/n · (k + 1) km/n ≥ (k + 1) m/n .
By generalized Sauer-Shelah Lemma, we have (k + 1) m/n ≤ m Dim k (H i S ′ ,Y ) · n kDim k (H i S ′ ,Y ) · (k − 1) m/n ≤ m 2Dim k (H i S ′ ,Y ) · (k − 1) m/n . Taking logarithms we have Therefore, there exists a set S ′′ ⊆ S ′ of size m 2n(k−1) log 2 (m) that is k-shattered by Y . By definition of kshattering, let {Y a } a∈T (each Y a has size k) be a collection of subsets of Y that indicates S ′′ is k-shattered. By averaging argument, since the total number of different Y a is at most n k ≤ n k (k−1) 2 , there is a subset S ⊆ S ′′ of size m n k+1 log 2 (m) ≥ m m 1−(k+1)ǫ log 2 (m) = m (k+1)ǫ log 2 (m) such that for all a ∈ S, Y a are the same. Let this Y a to be A, we have that the pair S,A is shattered by H i S,A . ✷ Observation 5. ( [DSS15]) H has the α containment property if and only if the MIR mechanism with set H has an approximation ratio of α with respect to single minded valuations. H has the α intersection property if and only if the MIR mechanism with set H has an approximation ratio of α with respect to 0/1-additive valuations. 9 By putting Observation 3, Observation 4, Observation 5, Theorem B.2 and Theorem B.3 together, we get the following two Corollaries: Corollary B.1. For all δ > 0, if an MIR interpolation mechanism has first round communication at most m δ per bidder and guarantees approximation ratio m 1/3−2δ/3 when all buyers are single minded, then one of the MIR mechanisms selected for phase two maximizes over a set of allocations H i that shatters a pair of subsets S ⊆ [m] and A ⊆ [n] of sizesΩ(m 1/2+δ/2 ) and m 1/6+δ/6 , respectively.
Corollary B.2. For all δ > 0, if a MIR interpolation mechanism has first round communication at most m 1/3 per bidder and guarantees approximation ratio m 1/3−δ 5 when all buyers are 0/1-additive, then one of the MIR mechanisms selected for phase two maximizes over a set of allocations H i that shatters a pair of subsets S ⊆ [m] and A ⊆ [n] of sizes m 3δ log 2 (m) and 2. Finally, these two corollaries provide the proof of Theorem 5.1. Proof of Theorem 5.1: First, it is clear that both capped-additive and submodular valuations contain 0/1additive valuations. At a high level, the fact that H i shatters a large pair of subsets means that any mechanism that optimizes over H i can solve instances over S, A exactly. If it is computationally hard (or impossible with low communication) to optimize over sets of the corresponding sizes exactly, then it must be the case that the MIR mechanism optimizing over H i isn't computationally efficient (or communication efficient).
To prove the three bullets formally, one just needs to encode problems that are NP-hard to solve (or require exponential communication) into welfare maximization for the appropriate valuation classes. Daniely et. al. provides such reductions for each of the three problems, so we use exactly the same reductions as them. We refer the reader to [DSS15] for further detail. ✷


text:
TransCut: Transparent Object Segmentation from a Light-Field Image

The segmentation of transparent objects can be very useful in computer vision applications. However, because they borrow texture from their background and have a similar appearance to their surroundings, transparent objects are not handled well by regular image segmentation methods. We propose a method that overcomes these problems using the consistency and distortion properties of a light-field image. Graph-cut optimization is applied for the pixel labeling problem. The light-field linearity is used to estimate the likelihood of a pixel belonging to the transparent object or Lambertian background, and the occlusion detector is used to find the occlusion boundary. We acquire a light field dataset for the transparent object, and use this dataset to evaluate our method. The results demonstrate that the proposed method successfully segments transparent objects from the background.

Introduction
Image segmentation is a fundamental problem in computer vision. The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze [26]. For example, it is very important to separate foreground objects from the background in applications such as object detection, object recognition [19], and surveillance tasks [8]. Numerous methods have been developed to deal with the image segmentation problem, including techniques based on thresholding [20], partial differential equations [7], and graph partitioning [27,4]. However, none of these methods are suitable for the segmentation of transparent objects from an image. The difficulty of dealing with such objects means that transparent object segmentation is a relatively untouched field.
Although there are few techniques for separating transparent objects from an image, many tasks in our everyday life deal with transparent objects. For example, when a machine is operating in kitchens, living rooms, and offices, it should avoid touching fragile objects such as glasses, vases, Figure 1. Input and output of our system. The left side shows the captured light-field image, and the right-hand side is a magnification of the central viewpoint. The output after segmentation of the transparent object is shown on the bottom-right. bowls, bottles, and jars. One way of detecting these transparent objects is to segment them from captured images of the scene. The appearance of a transparent object is highly dependent on the background, from which its texture and colors are largely borrowed. Thus, it is extremely challenging to separate the transparent object from the background.
It is almost impossible to achieve stable transparent object segmentation in a 2D image using conventional image segmentation approaches. In this paper, we utilize a lightfield camera to capture 4D light-field images, and propose a method that can segment the transparent objects from the captured 4D light-field image (see Fig. 1). Our method can automatically segment the transparent objects without any interaction. The main idea is to take advantage of the lightfield distortion (LFD) feature [14] that has been proposed for transparent object recognition. LFD does not rely on the appearance of the background, and LFD features from the Lambertian and non-Lambertian areas have different properties. As shown in Fig. 2, the features from the Lambertian area are almost linearly distributed with respect to the viewpoints, unlike features from transparent objects. We call this property light-field linearity (LF-linearity). However, features from the background will be nonlinear when occlusion occurs, and features from the transparent object will be linear when the distortion is relatively mild. This does not present a problem when LFD is used for recognition tasks, because several dominant features can determine what type of transparent object is contained in the image. We cannot completely separate the transparent object from the background using LFD alone, but we can use this feature to obtain a rough estimate of the position of the transparent object and the background.
To completely segment the transparent object from an image, we utilize the graph-cut optimization method [4] with LF-linearity and occlusion detection from the 4D lightfield image. Our method only uses information from a geometric relationship that is independent of the color and texture.
The contributions of this paper are as follows: 1) we propose a method for a challenging computer vision problem, transparent object segmentation, and the method is automatic, requiring no human interaction; 2) an energy function is defined using the LF-linearity, and occlusion detector; and 3) comparisons show that the proposed method obtains better results than previous method for finding glass [16].

Related work
There are various strategies for optimizing energy functions. The combinatorial min-cut/max-flow graph-cut algorithm is widely used for energy functions defined on a discrete set of variables. Greig et al. [12] were the first to realize that powerful min-cut/max-flow algorithms could be used to minimize certain energy functions in computer vision applications. The energy function encodes both regional object information and the regularization of the image smoothness. The regional information usually comes from user interaction [4,22], particularly in image editing applications. Automatic segmentation approaches that do not require user interaction have been developed in recent years. An object segmentation framework [6] has been proposed for the automatic extraction of candidate objects by solving a sequence of constrained parametric min-cut problems. Another method [21] estimates whether a pixel is inside the foreground object based on the point-in-polygon problem, whereby any ray starting from a point inside the polygon will intersect the boundary of the polygon an odd number of times. In our method, we use occlusion to detect the boundary of a transparent object, and this occlusion boundary also allows us to determine which side is the background. We detect the occlusion boundary by designing a series of occlusion detectors to check the pattern of forward-backward matching consistency in all viewpoints. The forward-backward matching consistency has been used in many previous studies such as [1]. For more sophisticated occlusion detection strategies, we refer to [2] and the references therein.
From a different perspective, a number of studies have analyzed images captured by special optics or devices to obtain the physical parameters of the transparent object, such as its refractive index and surface normal. Schlieren photography [24,25] has been used to analyze gas and fluid flows and shock waves. This method requires highquality and precisely aligned optics to visualize the refraction response in a scene as a gray-scale or color image. Wetzstein et al. [30] extended this technique to light-field background-oriented Schlieren photography, using a common digital camera and a special optical sheet, known as a light-field probe (LF-probe), to reconstruct the transparent surface [31]. Similarly, Ji et al. [13] used an LF-probe and multiple viewpoints to reconstruct an invisible gas flow. The light refracted by transparent objects tends to be polarized, meaning that polarizing filters can be used to measure their light intensity [17,18]. Ding et al. [10] used a camera array and checkerboard pattern to acquire dynamic 3D fluid surfaces. Ye et al. [33] acquired dynamic 3D fluid surfaces with a single camera, but they used a special "Bokode" background (which emulates a pinhole projector) to capture ray-ray correspondences. All of the above methods require some special optics or devices, so their applicability is restricted to laboratory environments, and they are not feasible for common practical use. Similar to our target, learning-based method [15,16] has been proposed for finding glass in a single view image. Fritz et al. [11] used SIFT feature and LDA for learning a transparent object and detecting its location and region as a bounding box. Wang et al. [28,29] used RGB-D image for glass object segmentation. The depth image was utilized as one of the cues for transparency that the depth information is missing in the glass region, since the glass refracts the active light from the sensor. For multi-view images as input, the epipolar-plane-image (EPI) analysis method was used to extract layers with specular properties [9]. Multi-view images with known camera motion has been used to recover shape and pose of transparent object [3]. Our method utilize the characteristic that transparent objects distort the background by refraction to derive the LFD feature [14] which was originally proposed for transparent object recognition. We take advantage of occlusion information and the distortion feature for transparent object segmentation from a single-shot light-field image, and the proposed method also has the potential for glass and specular objects.

Feature descriptors from light field
In this section, we define LF-linearity and occlusion detector for describing feature of transparent object.

Light-field linearity
The LFD feature was proposed by Maeno et al. [14]. They used this feature to classify different shapes of transparent objects. We will utilize an important property of this  feature to the likelihood of a pixel being the Lambertian background.
Similar to [14], we define the LFD as the set of relative differences between the coordinates of the corresponding points: where (s, t) is the viewpoint coordinate, and (∆u, ∆v) is the difference between point p(0, 0, u, v) in the central viewpoint view(0, 0) and its corresponding point In the experiments, we use an optical flow algorithm to obtain the correspondences between the central viewpoint view(0, 0) and viewpoints view(s, t).
As described in Fig. 2, the disparities in a transparent object include the refraction effect. Thus, the LFD features coming from the transparent object are more distorted than features from the background, and these features deviate from the hyperplane given by the Lambertian reflection in the phase space. The hyperplane in the stuv-space containing point p(0, 0, u, v) can be described as: where (s, t, ∆u, ∆v) is as before, i.e., the viewpoint coordinates and the difference between the corresponding image view(0,0) forward matching backward matching points. The positions of the viewpoints can be obtained by camera array calibration [32]. (n 1 , n 2 , n 3 , n 4 ) is the unit normal vector n of the hyperplane. This vector is estimated by fitting (s, t, ∆u, ∆v) from all M viewpoints: We then use singular value decomposition to calculate A ⊤ A = UDU ⊤ , and the linear least-squares solution to n is the column of U associated with the smallest eigenvalue in D, where the smallest eigenvalue is the least-squares error E(u, v). Smaller errors imply better linearity, and larger errors indicate that the feature deviates strongly from the hyperplane. Because this error E(u, v) describes the linearity of the LFD feature, we call this the LF-linearity. This important property is used to define the regional term in the energy function. Figure 6(b) shows an example of the visualized LF-linearity.

Occlusion detector
The background can be occluded by foreground objects in different viewpoints. This is an important cue for determining the boundaries between the foreground and background. The occlusion boundary is often detected by comparing the appearance of points over time as the camera or object moves. In a light-field image, we detect occlusion points by checking the consistency of the forward and backward matching between a pair of viewpoints, as illustrated in Fig. 3.
We denote an arbitrary point in the image captured by the central viewpoint view(0, 0) as p(0, 0, u, v), and the corresponding point in the image captured by another viewpoint view(s, t) as p ′ (s, t, u ′ , v ′ ). Here, (s, t) are the coordinates of the viewpoint view(s, t), and (u, v) are the coordinates of the point in the image plane (as shown in Fig.  2). We also attempt to find the point in the central viewpoint view(0, 0) that corresponds to p ′ (s, t, u ′ , v ′ ), which we denote as p ′′ (0, 0, u ′′ , v ′′ ).
The consistency is independent of the intensity at each point, so we can simply calculate the geometric error of the forward and backward matching: where dist(p, p ′′ ) is the Euclidean distance between p and p ′′ .
In the non-occlusion case, points p(0, 0, u, v) and p ′′ (0, 0, u ′′ , v ′′ ) should be very close, which means the error e(s, t, u, v) will be very small. If this consistency requirement is not satisfied, the point is either occluded in the corresponding viewpoint, or the optical flow has been incorrectly estimated. The small values are mainly from noise, and the large error values do not have much physical meaning. Hence, we define the LF-consistency c(s, t, u, v) by binarizing the error e(s, t, u, v).
where τ is a tolerance interval that allows the noise introduced by the optical flow calculation. We assign zeros to consistent points and ones to inconsistent points. The LF-consistency has different patterns when the occlusion boundary appears in different directions. Fig. 4 shows an example of a point that has both consistency and inconsistency in different viewpoints. Based on our observations, we have designed a series of occlusion detectors F (s, t, θ) to detect the occlusion boundaries between foreground and background. The detectors of 5 × 5 case, which are used in our experiments, are shown in Fig. 5, and θ is the normal direction of the occlusion boundary. The size of (a) θ = 0 The direction with largest response of all the detectors will be chosen as the occlusion direction: An example of the detected occlusion is shown in Fig. 6(c).

TransCut: graph-cut segmentation for transparent object
The goal of this work is to segment transparent objects by using LF-linearity and occlusion detector. We formulate the segmentation task as a pixel labeling problem with two labels (transparent objects as the foreground and other objects as the background). Later part of this paper, we describe each pixel as p = (0, 0, u, v) and some variables with subscript p indicate the variables at pixel p of the center viewpoint, since we solve the pixel labeling problem in 2D image space. Similar to other segmentation methods  Figure 7. Properties of different components in an image containing a transparent object. The Lambertian background (blue) has good LF-consistency, the transparent object (red) has poor LFlinearity excludes the occlusion area, and the occlusion boundary (orange) can be detected by occlusion detector. [4,22], we define an energy function to evaluate the labeling problem: where l p is the label of an image pixel p (l p = 0 denotes a background pixel, l p = 1 denotes a foreground pixel), R p (l p ) is the regional term that measures the penalties for assigning l p to p, B p,q is the boundary term for measuring the interaction potential between pixels p and q, N is the neighborhood set, α adjusts the balance between R p (l p ) and B p,q · δ(l p , l q ), and δ(l p , l q ) = 1, if l p = l q 0, if l p = l q (10) The segmentation task aims to determine the labeling that minimizes Eq. 9. We use the graph-cut method to optimize the energy function.

Regional term
We assume that all Lambertian objects in the image should be labeled as background, and the refractive transparent object should be labeled as the foreground. As illustrated in Fig. 7, the background and the occluded areas (shown in blue and orange) should be labeled as the background, and the transparent object (red) should be labeled as foreground.
The Lambertian object has good LF-linearity while the transparent object has poor LF-linearity. The occlusion area also has poor LF-linearity and can be detected by the occlusion detector, so the transparent object locates in area with poor LF-linearity other than the occlusion area. The case of the occlusion area with good LF-linearity rarely occurs because, when the forward-backward matching is not consistent, the LF-linearity will be poor. Therefore, the region with good LF-linearity should be background. When a pixel belongs to the background, the penalty for labeling this pixel as a Lambertian object or occlusion area should be low, while the penalty for labeling this pixel as part of a transparent object should be high. The opposite is true when a pixel belongs to the foreground.
Before defining the regional term of the energy function, we first scale the LF-linearity E(u, v) to the range [0, 1] using a sigmoid function: where sigmoid(ϕ, a, b) is the function: a controls the steepness of the function, and b is the shift, which acts as the threshold value here. The regional term for a pixel p is defined as: whereÕ p = O(u, v,θ), which is the maximum response from the occlusion detectors descried in Eq. 7 and Eq. 8. R p (0) assigns a large penalty to pixels that have poor LFlinearity exclude the occlusion area, and R p (1) assigns a large penalty to pixels with poor LF-linearity inside the occlusion area or pixels with good LF-linearity. β adjusts the balance between R p (0) and R p (1).

Boundary term
In the boundary term of the energy function, we must define the pairwise potentials between two neighboring pixels. We use the 4-neighbor system, so each pixel has two horizontal neighboring pixels and two vertical neighboring pixels. We utilize the maximum response of the occlusion detectors to assign pairwise potentials.
The boundary term applies a penalty when neighboring pixels p, q are assigned different labels. Given a pixel p (see Fig. 8), the weight of its 4 neighboring edges can be described as: and so forth. The weight for each edge is calculated twice as w p,q and w q,p , and the penalty for assigning different labels to p and q is defined as: B p,q = exp(−γ · (w p,q + w q,p )). The weight is small in the background and foreground regions. The penalty of the region is high in the case of assigning different labels to the neighboring pixels. It works easy to propagate the same labels in the same regions. In contrast, the occlusion boundary will have large values of O p , and it stop to propagate the label between the different regions. γ controls the rate of the importance of the penalty.

Experiments
As there are no light field datasets available for the evaluation of transparent object segmentation, we captured the necessary data ourselves. We shall demonstrate our proposed transparent object segmentation method on various examples, including single and multiple objects segmentation with different backgrounds, and compare with other methods such as finding glass [16].

Assumptions
To ensure the effectiveness of the matching process, our experiments were conducted under the following assumptions: • All viewpoints of the light-field camera can capture the entirety of the target objects.
• The degree of reflection on the surface of the target objects is relatively low.
• Background is relatively far away with rich texture.

Results and discussion
In the experiments, we used a light-field camera with 5× 5 viewpoints (ProFusion 25, Viewplus Inc.) to acquire the images. We placed the target objects about 50 cm from the camera, with the background a further 100 cm behind the objects. We captured seven transparent objects (shown in Fig. 9) with seven different background scenes (shown in Fig. 10). The backgrounds include indoor scenes such as a library and outdoor scenes such as a city backdrop seen through a window. As mentioned in Sec. 3, we use an optical flow algorithm to obtain the corresponding points p, p ′ and p ′′ in the central viewpoint view(0, 0) and the other viewpoints view(s, t). We utilize the optical flow algorithm proposed in [5], which integrates descriptor matching into variational motion estimation. Although this optical flow algorithm is very accurate, it cannot deal with textureless regions, and such areas will cause problems when the matching is not correct. For this reason, we remove those textureless regions for which the squared horizontal intensity gradient averaged over a square window of a given size is below a given threshold [23]. The parameters used in all experiments are fixed to the same values. We determine the parameters α, β, γ based on the preliminary experiments, and set α = 70, β = 4.5, γ = 4.5 which are suitable for our dataset. Parameter a decide the thresholding is hard or soft, b is determined by the level of least-squares error, and τ is related to the accuracy of optical flow and image resolution. We set a = 0.5, b = 5 and τ = 8, which are suitable for our case.
We compare our segmentation results with those from LF-linearity thresholding and the finding glass method. For the thresholding method, we simply filter out the Lamber- tian background by removing feature points whose leastsquares error E(u, v) is below a certain threshold, i.e., E(u, v) < th. In our experiments, we set th=5 which is same to b. For the finding glass method, we implemented the method described in [16] and applied to the center view of our dataset. Figure 13 shows the results for the same scene with different objects, and Fig. 14 shows the segmentation results for the same object with different backgrounds. We can see that, simply LF-linearity thresholding will result in holes inside the target object at points where the light field is nearly linear, and mismatched regions from outside will be included in the object. The finding glass method falsely detected the rich texture background as glass, since this method is not suitable for rich texture images, which is mentioned as the limitation in the paper. The proposed TransCut method gives very stable results for various objects in different scenes.
We determined the ground truth by manually labeling all pixels, and quantitatively compared the segmentation results. This comparison is tabulated in Table 1. We have used the F-measure to compare the performance of each algorithm. This metric is the harmonic mean of the precision (Pr) and recall (Re), i.e., where Re = T P/(T P + F N ), and P r = T P/(T P + F P ) (TP=True Positive, FN=False Negative, FP=False Positive). We also compare the results calculated by different number of viewpoints. We reduced the viewpoints to the central view with 4 far corner views, and uniformly distributed 3 × 3 views with larger disparity. The results are shown in Table 2. We can see that the performance decreases when the viewpoints become fewer, because fewer viewpoints are more vulnerable to the noise.
The results of experiments including multiple objects are shown in Fig. 11. These images show that the proposed Figure 11. Comparison of segmentation results for multiple objects in different scenes. The 1st row shows the image from the central viewpoint. The 2nd, 3rd, and 4th rows show output from the finding glass, LF-linearity thresholding, and proposed Tran-sCut methods, respectively. method is effective when there is more than one object in the scene, whereas the other two methods do not produce good results in such scenarios. Further results can be found in our supplementary material.
Moreover, we also conduct some experiments with real scene. We can see that our method works though it is not perfect in Fig. 12.

Conclusion
In this paper, we have proposed TransCut which is the method for the segmentation of transparent objects. Unlike conventional methods, our technique does not rely on Figure 13. Comparison of segmentation results for the same scene with different objects. The 1st row shows the image from the central viewpoint. The 2nd, 3rd, and 4th rows show output from the finding glass, LF-linearlity thresholding, and proposed TransCut methods, respectively. The last row shows the manually labeled ground truth. Figure 14. Comparison of segmentation results for the same object in different scenes. The 1st row shows the image from the central viewpoint. The 2nd, 3rd, and 4th rows show output from the finding glass, LF-linearity thresholding, and proposed TransCut methods, respectively. We refer to the 3rd object in the last row of Fig. 13 for the ground truth. color information to distinguish the foreground and background. We have used LF-linearity and occlusion detector in 4D light field space for describing a transparent object, and designed an appropriate energy function utilizing the LF-linearity and occlusion for pixel labeling by graph-cut. The results show that our method produces stable results with various objects in different scenes.
There are several future directions we are planning to explore. Our dataset was captured by camera array where the camera baseline is large and viewpoint number is few.
An straightforward future step is to apply our algorithm to the light field image captured by Lytro camera. The current results are not yet perfect, as our assumptions produce some limitations. We intend to overcome these limitations in future work, and extend to more flexible environment and other non-Lambertian objects.


A Scheme for Increasing Visibility of Single Hazy Image under Night Condition

This paper proposes an approach for Increasing visibility of single hazy image under night condition which utilizes a combination of histogram equalization, gamma correction, and dark channel prior with soft matting technique, refined transmission procedure to avoid the generation of block artifacts in the restored image, and effective transmission map estimation by adjusting its intensity via an enhanced transmission procedure based on the adaptive gamma correction technique. Our result shows better contrast noise ratio and peak signal to noise ratio values over existing methods based on dark channel prior.

Introduction
The image is captured in the outdoor scene are highly despoiled due to the reduced lighting situation or due to the soil particles. So due to these particles the irradiation coming from the objects is scattered or absorbed and hence the phenomena of haze and fog occurs. The dark channel prior 5 method is extremely helpful to dehaze the foggy images but fails to remove halo effects, to be more precise, it fails to estimate the correct transmission map for hazy low light images. So in outside low light image case the dark channel prior scheme is incompetent to improve the whole scene.
The optical model has been widely used in the computer vision research field, particularly to describe the formation of hazy images captured by digital cameras. It is based on the physical properties of light transmission through atmospheric conditions, and can be described as 10 .
Where P(x) is the intensity of the observed hazy image, Q (x) is the scene radiance, A t is the universal atmospheric light, and t(x) is the medium transmission representing the portion of light, which is not scattered and subsequently is received by the camera. On the right-hand side of (1), the first term Q(x)t(x) is called the Direct reduction; the second term A t (1−t(x)) is called atmosphere light. The optical model can be described by direct attenuation and air light. Direct attenuation describes the decay of scene radiance and is dependent upon medium and scene depth, while air light represents the scattering of light that leads to color shifts in the scene.

Haze Removal Using Dark
Channel Prior

Dark Channel Prior
In order to restore image visibility degraded by haze, He et al. 5 provide a DCP method to estimate scene depth in a single image. The method is based on the key observation that a haze-free outdoor image exhibits at least one color channel with a very low intensity value in regard to patches of the image, which do not contain sky 5 . Thus, the dark channel J dark of the outdoor haze-free image J can be expressed as dark c min min J (X) J (y) y (x) c {r,g,b} Where J c is a color channel of the RGB image is the minimum value of the RGB channel, Ω(x) is a local square centered at location x, and is a minimum filter. According to 5 , if J is an outside fog-free image, the corresponding intensity of dark channel J dark is low and close to zero.

Estimating the Transmission
In 10 , the dark channel prior provides a method by which to estimate transmission in a hazy image.
Where ω is set to 0.95.

Atmospheric Light Estimation
As discussed in 5 , for estimation of the atmospheric light A in the outdoor image, the brightest 0.1% of pixels are chosen from within the dark channel prior. From among these, the pixels with the highest intensity in the input image are determined to be the atmospheric light A.

Soft Matting
The restored image may contain some block artifacts after haze is removed by employing the transmission produced via (3). To resolve this, the transmission can be refined as optimal transmission t(x) through soft matting, as described in 5 .

Proposed Algorithm to Detect the Type of Images and Enhancement of Hazy Night Images
In order to detect, whether the image is during day light or it is degraded due to fog and insufficient lighting during night time, the following algorithm has been proposed.

Proposed Approach Description
Our propose approach involves two important modules: • Transmission Estimation Module • Recover Scene Radiance Module

Transmission Estimation Module
The propose TE module is based primarily on the dark channel technique and is used to estimate the transmission map of a hazy image. However, two prominent problems exist in regard to the dark channel prior technique: • Generation of halo effects • Insufficient transmission map estimation. The TE module circumvents these problems using a enhance transmission procedure. Because the primary operation of the dark channel prior depends on the minimum filter, the transmission map will usually experience a loss of edge information when estimation occurs. For this reason, we propose a enhance transmission procedure that uses an adaptive gamma correction technique to preserve edge information of input hazy images and there by avoid generation of halo effects. We apply an adaptive gamma correction technique to adjust the intensity of the transmission map to achieve optimum haze removal result that can effectively hold back impulsive noise components while preserve edge information and estimating sufficient transmission map. The enhanced transmission form Et (q) is derived via the adaptive gamma correction operate as Where Et(q) is the maximum intensity of the input image, R t is the transmission map after performing equation (3), Υ is a varying adaptive parameter, is equal to 0.60

Recover Scene Radiance
Using the small amount of natural low light and transmission map, the scene radiance quality can be improved according to equation one. The direct reduction expression can be extremely close up to zero when the transmission t(x) is close to zero. So, we limit the transmission map t(x) by the lower limit t o and maintain a little fog in low light regions. The image radiance J(x) is recovered as: 16 Where t o be 0.1.

Experimental Observations
The proposed algorithm is implemented in MATLAB version R2010b running on Windows 7 operating system with 4GB RAM. Refer to Table 1. sample input images. The peak to signal ratio (PSNR) and contrast to noise ratio (CNR) has been calculated for first output images of different authors using matlab code refer to Table 2 ; PSNR and CNR has been calculated for second output image using matla code refer to Table 3. Graphical Analysis of Different Methods refer to Table 4.

Conclusion and Future Scope
The propose work applies a refined transmission procedure to avoid the generation of block artifacts in the restored output image using the DCP. Subsequently, an effective transmission is estimated by adjusting its intensity via an enhanced transmission procedure based on the adaptive gamma correction technique. Since the weight parameter "w" generally varies from scene to scene, it becomes very important parameter to deal with the night haze image. Therefore our proposed model fails to make the parameter "w" adaptive for all night climate conditions