Learning and Collusion in Multi-unit Auctions
Authors: Simina Branzei
Mahsa Derakhshan
Negin Golrezaei
Yanjun Han
Venue: NeurIPS 2023 poster (2023)
Keywords: multi-unit auctions
repeated auctions
online learning
collusion
games and learning
lower bounds
multiplicative weight updates
bandit learning
TL;DR: We consider repeated multi-unit auctions with uniform  pricing and study offline/online learning and equilibrium quality in two  main auction variants, finding that one variant is susceptible to collusion among bidders while the other is not.

Abstract: In a carbon auction, licenses for CO2 emissions are allocated among multiple interested players. Inspired by this setting, we consider repeated multi-unit auctions with uniform pricing, which are widely used in practice. Our contribution is to analyze these auctions in both the offline and online settings, by designing efficient bidding algorithms with low regret and giving regret lower bounds. We also analyze the quality of the equilibria  in  two  main variants of the auction, finding that one  variant is susceptible to collusion among the bidders while the other is not.

Learning and Collusion in Multi-unit Auctions"
Simina Brânzei Purdue University
Mahsa Derakhshan Northeastern University
Negin Golrezaei MIT
Yanjun Han New York University
Abstract
In carbon auction, licenses for CO2 emissions allocated among multiple in- terested players. Inspired by this setting, we consider repeated multi-unit auctions with uniform pricing, which are widely used in practice. Our contribution is analyze these auctions both the offline and online settings, by designing effi cient bidding algorithms with low regret and giving regret lower bounds. We also analyze the quality of the equílibria in two main variants of the auction, finding that one variant susceptible collusion among the bidders while the other is not.
Introduction
In multi-unit auction, a seller brings multiple identical units of good to a group of players (buyers) interested in purchasing the items. Due to the complexity and depth of the model, the multi-unit auction has been explored in a significant volume of research [MRH89, EWK98, DN07, DLN12, FFLS12, ACP* 14, DN15, BCI+ BGN03, GML13, DHP17, BMT19] and recommended as lens to the entire field of algorithmic mechanism design [Nis14]. The prior literature has often focused on understanding the equilibria of the auction under various solution concepts and designing revenue or welfare maximizing one-shot mechanisms.
We consider the setting where each player i has value v. for receiving j-th unit in their bundle, which is reported to the auctioneer in the form bid bi.j After receiving the bids, the auctioncer computes price p per unit, then sorts the bids in descending order and allocates the j-th unit to the player that submitted the j-th highest bid, charging them p for the unit. The price is set so that all units sold and the resulting allocation has the property that each player gets their favorite bundle given their preferences.
This allocation rule represents the well-known Walrasian mechanism in the multi-unit setting: com- pute the market (aka competitive or Walrasian) equilibrium with respect to the reported valuations. The template for the mechanism is: elicit the valuations from the buyers and then assign set of prices to the goods such that when each buyer takes their favorite bundle of goods at the given prices, the market clears, i.c. all goods are sold and there is no excessive demand for any good (see, e.g., [BLNL14]), Due to the strong fairness and efficiency properties of the market equilibrium, the resulting allocation is envy-free with respect to the reported valuations. A strand of research concentrated on achieving fair pricing in auctions, which often involves setting uniform prices for identical units [GHK* 05].
Repeated auctions take place in many real world settings, such as when allocating licenses for car- bon (CO2 emissions) [CK02], ads online platforms [BBW15, GJM21], U.S. Treasury notes to investors or trade exchanges over the internet [MT15]. Repeated mechanisms often give rise to complex patterns of behavior. For example, the bidders may the past transaction prices way of discovering the valuations of the competing bidders, or engage in collusion using bid rotation
Authors listed in alphabetical order. This work was done in part while the authors visiting the Simons Institute for the Theory of Computing. Simina was supported in part by NSF CAREER grant CCF- 2238372.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

schemes since the history of bids can serve as communication device [Aoy03]. In fact, [CCDP2]] show that in markets such as Cournot oligopolies with stochastic demand, collusion observed even when the bidders are not explicitly trying to conspire. Instead, collusion emerges naturally when the agents use Al algorithms based on Q-learning to update their strategies.
Since repeated multi-unit auctions are used in high-stakes environments such as allocating licenses for carbon [GIL20], it paramount to understand: (i) what features should the auction have in the first place?; and (iz) given an auction format, how should the players bid to maximize their utility?
A good bidding strategy generally guarantees the player using it will not "regret" its strategy in hindsight, regardless of the strategies of others. There has been extensive work on understanding dynamics in auctions and games under various behavioral models of the players (see, e.g., INCKP22, RST17, DS16, MT15, HKMN11, 1, BR11 LB10, 10, GJM21, GJLM21, GJI.23, BF19], but due to the complexity of understanding dynamical systems many questions remain open.
In this paper, we design efficient learning algorithms that players can use for bidding, in both the offline and online settings. We also give regret lower bounds and then analyze the quality of the equilibria in two main variants of the auction, finding that one variant is susceptible to collusion among the bidders while the other is not.
1.1 Model
Consider a seller with K identical units of good and a set of players [n]] {1, ....... . n2 that have quasi-linear valuations with decreasing marginal returns. Formally, let v; (0i,1,.... (;,K) be the valuation of player i, where Vi.j 2 0 is the marginal value for getting a j-th unit in their bundle. The value of player i for getting units is Vi(e) = Σ Vi Diminishing marginal returns require that U1,1 02,2 2 ... UiKK Vi E [n]. A player i is said to be hungry if Ui > 0 Vj E [K].
Auction format: uniform pricing. The auctioneer announces K units of good for sale. Each player i submits bids b; = (b.,1.-..,hb bi.k) sorts the bids in decreasing order and computes price p. Then for each = 1,... ....... K, the auctioneer allocates the j-th unit to the player that submitted the j-th highest bid, charging them for the unit. If multiple bids are equal each other, ties are broken in lexicographic order of the player names.
). where br, is player i's bid for j-th unit. The auctioneer
We consider two variants of the auction:
ii the K K-th price auction, where the price per unit is set to the K-th highest bid; (ii) the (K + 1)-st price auction, where the price is set to the (K + 1)-st highest bid.
Both of these variants implement the market equilibrium with respect to the reported valuations of the players, which are represented by their bid vectors. The K-th price format selects the maximum possible market equilibrium price, namely the highest possible price per unit at which all the goods are sold and each player purchases their favorite bundle given their utility. The (K + 1)-st format selects the minimum possible market equilibrium price.
Allocation, Price, Utility. An allocation z is an assignment of units to the players such that 2, 2 0 is the number of units received by player and ΣØ= 2j K.
Given bid profile b, let p(b) be the price per unit and x(b) (b),,, ...., (b)) (b,,..,,,,,,))))) the allocation
obtained when the auction is run with bids b. where x, (b) E (0..... K} is the number of units received by player i. The utility of player i at b is: (b) = (z(( p(b) (b).
Revenue and Welfare. The revenue obtained by the auctioneer at a bid profile equals K p(b). The social welfare of the bidders at b is SW
Σ (b().
Notation. W.l.o.g., we have b ... 2 d, for each bid profile b is such that and E [n]. Given a bid profile b = (b)...., b,), let b-; denote the bid profile of everyone except player i. The bid profile where player uses a bid vector and the other players bid b_: is denoted (B.b... b..).
An illustration of how the auction works is given in Example 1.
In other words, after the players submit their bids, the auctioneer arranges these bids in descending order (C....,, .j...., Cn. k) and then allocates unit 1 to the bidder with bid c,, unit 2 to the bidder with bid ez, and

---

Example 1. Ler K = 3 and n. = 2. Suppose the valuations are vi = (5. and v2 = 1). If the players submit bids b (2. 1) and b2 (3.2), 2). the bid are sorted in the order (b2,1. b1,1, b2.2 b1,2). Then the allocation is
and 2.
Under the K-th price auction, the price is set to p b2.2 2. The utilities of the players are (b) = Vi (1)
- 2 and u2 u2(b) = [22 - (4 + 2.2 1.
Under the (K 1) price auction, the price is set to p 61.2 1. The utilities of the players are u1 (b) = (1) - 500--p=5-20 5-1
and (b) = (2) 2 (4+1) 3.
Repeated sefting, We consider repeated setting, where the auction is run multiple times among the same players, who can adjust their bids based on the outcomes from previous rounds. Formally, in each round = 1,2,...,77 T,
the next steps take place:
The auctioneer announces K units for sale. Each player E [n] submits bid vector by i x(,x)) privately to the auctioneer, where bi, player i's bid for a j-th unit at time t. Then the auctioneer runs the auction with bids bt = (bf..... bb, and reveals information (feedback) about the outcome the players. We consider two feedback models for the information revealed at the end of round t:
Full information: All the bids b' are public knowledge.
Bandit feedback: The price p(b") is the only public knowledge; additionally, each player privately learns their own allocation (b')..
Thus the allocation at time solely depends on the bids submitted by players in round 4, excluding any prior rounds.
1.2
Our Results
The next sections summarize our results for both the K-th and (K 1)-st price variants.
1.2.1
Offline Setting
In the offline setting, we are given a player with valuation v, and a history H-; = (bl....., bT,) containing the bids submitted by the other players in past auctions. Here restrict the bidding space to discrete domain = [k & l E NJ, for some E > 0.
The goal is to find fixed bid vector bj (b.,,...., kT,x) that maximizes player i's cumulative utility on the data set given by the history H-i, that is, b; = arg maxBEDK Σ u,B b(.).
The offline problem is challenging because the decision (bid) space is exponentially large and hence naively experimenting with every possible bid vector leads to impractical algorithms.
We overcome this challenge by relying on the structural properties of the offline problem. At high level, we carefully design a weighted directed acyelic graph (DAG) and identify bijective map between paths from source to sink in the graph and bid profiles of player i. Since a maximum weight path DAG can be found in polynomial time, this yields a polynomial time algorithm for computing optimum bid vector.
Theorem 1 (informal). Computing optinum bid vector for one player in the offline setting is equivalent to finding maximum-weight path in a DAG and can be solved in polynomial time.
Theorem applies to both versions of the auction, with K-th and (K + 1)-st highest price.
1.2.2 Online Setting
In the online setting, the players run learning algorithms to update their bids as they participate in the auction time. The first scenario consider is that of full information feedback, where the end of each round t the auctioneer makes public all the bids b' submitted in that round.
2 players. Suppose that round 5. player submits the bid vector of = (4, 2) and player submits bj = (5, 3). The auctioneer sorts these bids in decreasing order, obtaining the vector (5, 4, 3, 2). Then the allocation in round 5 is to give the first unit to player I and the second unit to player 2; the allocation disregards any events from preceding rounds.
FFor example, consider
units

---

Building on the offline analysis, we design an efficient online learning algorithm for bidding, which guarantees low regret for each player using it. The main idea is to run multiplicative weight updates, where the experts are paths in the DAG from the offline setting. Each such path corresponds to bid profile for the learner. A challenge is exponential. Nevertheless, we can achieve a polynomial runtime by representing the experts implicitly, using a type of weight pushing algorithm based on the method of path kernels [TW03].
that the number of paths in the graph (and so experts)
Theorem 2 (Full information feedback, upper bound). For each player i and time horizon T, there an algorithm for bidding in the repeated auction with full information feedback that runs in time O and guarantees the player's 's regret is bounded by O VTK3 log T)-
To the best of our knowledge, our paper is the first to connect the path kernel setting with auctions and obtain efficient algorithms for learning in auctions via this connection.
We also consider bandit feedback, which limits the amount of information the players learn about each other: at the end of each round the auctioneer announces publicly only the resulting price, and then privately tells each player their allocation. Bandit feedback could be relevant for reducing the amount of collusion among the players in repeated auction environments [HP89].
Theorem (Bandit feedback, upper bound). For each player i and time horizon T, there is an al- gorithm for bidding in the repeated auction with bandit feedback that runs in O(KT + K -5///77/4) and guarantees the player's regret bounded by Ov min ( T/TK Koogg T, KT)).
Although our bidding policy is similar to the EXP3-type algorithm in [GLLO07], and our compu- tational efficiency relies on the path kernel methods in [TW03]. major difference is that our edge weights are heterogeneous, i.c. the weights of different edges could be of different scales, To cir- cumvent this issue, we need use different estimator for the weight under bandit feedback which in turn also changes the technical analysis.
We complement the upper bounds with the following regret lower bound, where the construction of the hard instance relies heavily on the specific structure of our auction format.
Theorem 4 (Lower bound, full information and bandit feedback). Let K 2 2. Suppose the auction is run for T rounds. Then for each strategy of player i, under both full information and bandit feedback, there exists bid sequence {b', )=>))=> by the other players such that the expected regret of player i is at least c. U1 K VT, where c > is an absolute constant.
Theorems 2, 3, and 4 apply to both variants of the auction (with K-th and (K + 1)-st highest price).
1.2.3 Equilibrium Analysis
We also analyze the quality of the Nash equilibria reached in the worst case in the static version of the auction, as they naturally apply to the empirical distribution of joint actions when the players use sub-linear regret learning algorithms.
The (K- + 1)-st price auction has been observed to have low or even zero revenue equilibria [Wi179, KN04, ACP 14, BW20]. With > K hungry players, the next phenomena occur:
in the (K + 1)-st price auction: every allocation z that allocates all the units can be imple- mented in a pure Nash equilibrium b with price e, for every small enough 2 0.
in the K-th price auction: no pure Nash equilibrium with arbitrarily low price exists.
Our contribution is to show that the zero-price equilibria of the (K + 1)-st highest price auction are very stable. We do this by considering the core solution concept, which models how groups of players can coordinate.
In our setting, strategy profile is core-stable if no group S of players can deviate by simultancously changing their strategies such that each player in S weakly improves their utility and the improve- ment is strict for at least one player in S. The players outside S are assumed to have neutral reactions to the deviation, that is, they keep their strategy profiles unchanged. This is consistent with the Nash equilibrium solution concept, where only the deviating player changes their strategy.
body of literature studied the core in auctions when the auctioneer can collude together with the bidders (see, e.g., [DM08]). However, as is standard in mechanism design, it is also meaningful to

---

consider the scenario where the auctioneer sets the auction format and then the bidders can strategize and potentially collude among themselves, without the auctioneer; this setting our focus.
First, we consider the core without transfers, where a strategy profile is simply a bid profile b. Theorem 5 (Core without transfers). Consider K units and n > K hungry players. The core without transfers of the (K + s-stt auction can be characterized as follows:
every bid profile b that core-stable has price zero (i.e. p(b) =0);
forr every allocation z, there a core-stable bid profile b with price zero that implements
(i.e. x(b) z and p(b) 0).
If bid profile core-stable, then it is also a Nash equilibrium, for the simple reason that if no group of players can deviate simultaneously from b, then the group consisting of one player cannot find an improving deviation either. Thus Theorem 5 says that the equilibria with price zero are the only ones that remain stable when also allowing deviations by groups of players. Moreover, the theorem also says there are many inefficient core-stable equilibria, all with price zero.
Second, we also consider the core with transfers, where the players can make monetary transfers to each other. A strategy profile in this setting is given by pair (b. t), where b is bid profile and is a profile of monetary transfers, such that 4.j 2 O is the monetary transfer (payment) of player to player j (e.g., player could pay player j so that j keeps its bids low).
Theorem 6 (Core with transfers). Consider K units and > K hungry players. The core with transfers of the (K + )-stt auction can be characterized as follows.
. Let (b. t) be an arbitrary tuple of bids and transfers that is core stable. Then the allocation x(b) maximizes social welfare, the price zero (i.e. p(b) = 0), and there are no transfers between the players (i.e. t= 0).
To see why Theorem holds, if the price positive at some strategy profile, the players with "highest values" can pay the other players to lower their bids. When the price reaches zero, they can start withdrawing the payments. Thus the only strategy profiles in the core with transfers are those where the players with "highest values" win and pay zero. The difference from Theorem 5 is that transfers allow the players with highest values to force getting their desired items at price zero, which they cannot enforce without transfers. Nevertheless, even without transfers, the price remains zero.
Remarks on collusion. Given that the zero price equilibria of the (K + 1)-st price auction are very stable and easy to find, one can expect they can be determined by the bidders, for example in settings with few bidders who know each other. These equilibria can be easily implemented in repeated settings once the bidders agree on their strategies.
Strikingly, these zero price equilibria have in fact been observed empirically in repeated auctions for fishing quotas in the Faroe Islands, where even inexperienced bidders were able to collude and enforce them; see details in [LMTI8]. In the carbon setting, the Northeast US auction is based on the (K + 1)-st price format [GIL.00] and has very low prices as well.
In contrast, the K-th price auction format does not have any Nash equilibria with price zero, let alone core-stable ones. Thus the K-th price auction format may be preferable to the (K + 1 1)-st price auction in settings with high stakes, such as selling rights for carbon emissions. Another remedy, also discussed in [LMT18], is to make the number of units a random variable.
2 Related Work
Our work is related to the rich literature on combinatorial auctions (e.g., [DVV03, BN07, CSS07)) and more specifically auctions for identical goods, which are widely used in practice in various settings: Treasury Auctions [GI05, BS00], Procurement Auctions [AC05], Wholesale Electric- ity Markets [TSM08, FR03, FvdFH06], Carbon Auctions [GS13, SS17, GIL20J. The two most prevalent multi-unit auctions are uniform price auctions and pay-as-bid auctions that are widely studied in the literature either empirically (e.g.. [BZ93, MA98, BB01, HG13]) theoretically under the classical Bayesian setting (e.g., [AHP13, GII-20, BILI223]. In partieular, there have been several studies that aim to compare uniform price auctions versus pay-as-bid auctions (c.g..
5

---

[KCPTOI, FR03, SBLS04, LMMM11, ACP* 14]) in terms of revenue and welfare under Nash equi- libria, and the possibility of collusion. Our work contributes this literature by studying uniform price auctions the angle of designing bidding algorithms for the players.
Designing learning algorithms in auctions has attracted significant attention in recent years. Several papers study the problem of designing learning/bandit algorithms to optimize reserve prices in auc- tions over time (e.g.. [KN14 14, MRI6, MM16, CD17, DHL 17, GJL23, GJM21, GJLM21J). There are papers that have focused on designing bandit algorithms to optimize bidding strategies in single- unit second price and first price auctions (e.g.. [WPR16, BMSWI8, FPS18, HZF+20 20, HZW20, BGM 22]). Prior to our work, such problem was not studied for multi-unit uniform mnifor--price auctions.
Leveraging structural information in designing bandit algorithms has been the topic of the rich liter- ature, which includes linear reward structures [DHK08, RT10, MRT09, LS17], Lipschitz reward structures [MCP14, MLS18], convex reward distribution structure [VPC20]] and combinatorial structures [AR08, UNK 10, CBL12, ABL14, CWY13, CTPL15, ZLW19, V NGW+21J. Our work is closest to the works that aim to exploit combinatorial structures. Within this literature, several papers leverage DP-based or MDP- -Ds-based structures (e.g., [TW03, GLL007, ZN13, RM21J).
The multi-unit auction setting was studied in large body of literature on auctions [DLN12, BCI 05, DN07, DL14, DN15], where the focus has been on designing truthful auctions with good approxi- mations to some desired objective, such as the social welfare or the revenue.
Uniform pricing represents a type of fair pricing, since when everyone gets charged the same price per unit, no bidder envies another bidder's allocation. Fairness is an important property that is at odds with maximizing revenue, since for the purpose of improving revenue the auctioneer is better off charging higher prices to the buyers that show more interest in the goods. However, there is evidence that buyers are unhappy with discriminatory prices (see, e.g., [AS08]), which led to body of literature focused on designing fair auction mechanisms [GHK+05, FGL14, FFLS12, 12, CAEFFI6, Sek17, AVGN17, BFMZ17, FMTV20, DGJ+ 22]. Collusion in auctions was also studied both experimentally and theoretically in various models (e.g.. [GN92, vdFH93, GNR15)).
3 Offline Setting
In the offline setting, we are given a player i with valuation v, and a history H-; = (b'a..... bT. with the bids of other players in rounds through T. We assume the bids are restricted to a discrete domain D = {k- E l E N), for some E >> O. The goal is to find an optimum fixed bid vector I
in hindsight: by- = arg maX
Σ (,((),b,,) where we recall that (,, bb.)) is the utility of 1=1
player i at the bid profile (B, b".)). We will see the maximum in the definition of b; is well defined since there is optimum bid vector /3 with entries at most E above the maximum historical bid.
For any & > O, the optimal solution on the discrete domain ID also yields an (c K))ootiiall strategy on the continuous domain. The offline problem we study here has some resemblance to the problems studied in [RW16, 16, DGPLI9, DPS21]. There, the goal is to optimize reserve prices in VCG auctions while having access to a dataset of historical bids."
To design polynomial time algorithm for solving the offline problem, we define set S of "can- didate" bids for player i, which has polynomial size in the history, player i's valuation, and 1/E:
S, = [0} (8 1j E [n] (i),k E [K]} u UB6 + + E [m] Nf) k E [K]]
(1)
Observation 1. Player has an optimum bid vector (3 (3) . Bx) E T with B, Si for all j E [K] where St is defined in equation (1).
The proof of Observation 1 is simple and deferred to Appendix A. Next construct directed acyclic graph (DAG) G, that will be used to compute an optimum bid vector for player i. Definition 1 (The graph G.). Given valuation v; of a player i, history H- (bl (b_..... bT.).
e > 0, and set St from (1), define a graph G; with the following features.
*IRW16] also presents an online version of their offline algorithms under full information feedback; see also [NGW+21] for an online version of [RW16]'s algorithm for both full information and bandit settings using Blackwell approachability [Bla56].

---

Vertices.
Create vertex 2a.j for each E S; and j [K]. We say vertex 2z,j is in layer j. Add source 2_ and sink 24.
Edges. For each index j E -|] and pair of bids r, E S₁ with 2 s, create a directed edge from vertex ž to vertex 2s.+11. Moreover, add edges from source z- to each node in layer 1 and from each node in layer K the sink 24.
Edge weights. For each edge e (2r.g, Zs.+11 or (2r,K, let B (,,,....,, E S. be bid vector with 3j and 3j+1 (we define s = 0 if K). For each E [T', let h' = (B, b'.). Define the weight of edge e as
We Σ (1(0022))) (w15-1) r) + [ (r 8) + (=,(h))==) (r --ppp()))
(2)
recalling that p(h")) and x(h') are the price and allocation at h', respectively 5. The edges incoming from 2_ have weight zero.
A pictorial illustration of the graph G; is displayed in Figure
Layer
Layer
Laver
Layer
Zy,1
Zy
2
Z-
7,11
212
2
21,4
Z+
2111
Z22
21.1
Figure 1: Example of DAG as in Definition 1. Here, we have K = 4 units and the set of candidate
bids for player is S; = f0, 1, The graph has a source 2-, a sink 24, and nodes 2r,5 for all r S; and j [4]. Edges of the form Zs.f++ for all < 4 and r, S; with r s. There are also edges from the source = to nodes 2j.1 and from nodes æj.4 to the sink 24 Vj E S;.
At first glance, it may seem as though the weight w. of edge depends on the whole bid vector G since we use the value of x; (h') in its definition. However, this is not the case. Mcaning that, this formula gives the same value for any choice of , that satisfies B3
and B3+1 8. This is due to the fact that the values of variables 1 (z.(h)))) 1 (z.(h))) and 1 (h,())) can be determined only knowing the values of BJ++ and Bj (without knowing the rest of the vector ()..
We will show that computing an optimum strategy for the player equivalent to finding a maximum- weight path in the DAG G, from Definition 1.
Theorem 1 (formal version). Suppose we are given number of players, number K of units, valuation Vi of player i, discretization level e > 0, and bid history H (b',..... b²,) by players other than i. Then an optimum bid vector for player i can be computed polynomial time in the input parameters.
The proof of Theorem 1 is in Appendix A, together with the other omitted proofs of this section.
At a high level, for any bid vector B, we first write the cumulative utility of player when playing (3 while the others play according to b'4 Then observe the cummulative utility can be rewritten as a sum of K terms, so that each term only depends on j. By. and By+1- Create a layered DAG as in Definition 1, where the weight of edge (3,.j) to (3)+1.} + 1) is the j-th term of the sum above, with special handling for edges involving the source or the sink. The entire graph can be computed in polynomial time.
Then the proof shows there is bijection between the set of bid vectors of the player and the set of paths from the source to the sink in the graph. Thus the solution to the offline problem is obtained by computing a maximum weight path the graph and returning the corresponding bid vector.
The algorithm for the offline problem summarized in the next figure.
'hht is, Ie rrahh)) is the number of units received by player & allocation x(h"). ).)).
7

---

Input:
Player i with valuation v, = (Bi,1....; P. K,K)),
history H- = (b' j:..... b².) of bids
submitted by players other than i, and grid ID) = (k l E N] with allowed bid values.
Output: b arg max
Ei=1, (1, b'..)
Compute set S, defined in equation (1). By Observation 1, player has optimum bid vector by with br E S₁ for each j E [K].
Construct directed acyclic graph G; as in Definition By Theorem there is a bijective
map between paths from the source to the sink in G, and bid vectors B É S; of player i.
Compute a maximum-weight path in graph G, and output the corresponding bid vector.
algorithm 1: Optimum Strategy for the Offline Problem.
4 Online Setting
In the online setting, we consider the repeated auction where in each round / the auctioneer an- nounces K units for sale. Then the players privately submit the bids b' and the auctioneer computes the outcome. At the end of round f, the auctioneer gives full information or bandit feedback. The information available to player at the beginning of each round is the history: H (b.... b U
where
(b' - bb, - - - (p(b)), pp(b-)) in the bandit setting.
the full information setting,
A pure strategy for player at time is a function पं H RK where H is the history available to player the beginning of round Thus the pure strategy tells player what bid vector to submit next given the information observed by the player about the previous rounds. A mixed strategy a probability distribution over the set of pure strategies. Consequently, the bid vector by submitted by player at time the realization of the mixed strategy xf (H( We denote by TT (".,,"., or.") the overall strategy of player over the entire time horizon.
Regret. From now on we fix an arbitrary player i. Given a bidding strategy x; of player i, the regret of the player is defined with respect history H², of bids by other players:
Reg, (T,, (Tg, H.
max BESK
(uis p(B.b',)) (2.(88.5))))))
T
K (vi. - p(b')) 1(.)
E B Σ
(3)
For the purpose of equipping player i with a bidding algorithm, we will think of the other players as adversarial, and aim achieve small regret regardless of H", A way to interpret the regret is that player is competing against oracle that (a) has the perfect knowledge of the history of bids, but (b) is restricted to submit a time-invariant bid B. The regret quantifies how much worse player does compared to the oracle.
Before studying the feedback models in greater detail, replace the S, of candidate bids for player i from equation (1) of the offline section by a coarser set S = {E, 25, ... [[]./E]s].
4.1 Full information
In the full information scenario, at the end of each round t the auctioneer announces the bids b' submitted by the players in round t. We define a graph G that forms the basis of the learning
"We omit the allocation information in the history, for it is not informative when other players are adver- sarial: from the price information, player i knows her own allocation; treating all other players as a giant adversarial player, that player gets the rest of the allocation.

---

algorithm for the player. The graph G* is the same as in the offline setting (Definition 1), except for the next differences:
The vertex Zs,j is indexed by E Se. instead of Sü;
The edge weights are based only the current round t, rather than the sum over all rounds in the offline setting. More specifically, for edge (Zrus Raj+1) or (2r, 2+), set
w² (e) 1 (2;(122))) (ei, - r) + (1,(())))))) (r - 8) (zx(h))))) (r- (o-pp(h)))
(4)
The formal definition is deferred to Definition 2 in Appendix B. This DAG structure enables us to formulate the learning problem as online maximum weight path problem, and therefore treat each path as an expert and apply online learning algorithms to compete with the best expert. Theorem shows such algorithm (Algorithm 2) works for both K-th and (K 1)-st price auctions.
Input: time horizon T, valuation (Ui,1, "r k of the player
Output:
bid vectors (b) b)
Set the resolution parameter 14,1 K/T, and learning rate rj vlog T (VL, KT). For every / = 1,...,7 T:
Construct a graph G as in Definition 2, initially without weights on the edges.
If 1: for each edge initialize edge probability as
1/|Sel (e) = 1/1(r' E r srl
if (2-, kr.1;
if (Erji Zej+1), if = (Er.K, 2+).
If 2 2:
- starting from (==((4) = 1, recursively compute in the bottom-up order
(u)
Σ
(e) exp(n - w we)) I²))(,), Vu E v(G)):
etem EE
for each edge update the edge probability
(m) (e) (e) exp (1 w (e))
aor (u, F(G").
(5)
[1-1(1) (m))
For j = 1,2, K: sample b/ (
)) where ZM :=
The player observes bL,, and sets the edge weights w*( in Gt according to (4).
algorithm 2: Selecting bids using the weight pushing algorithm [TW03].
In Algorithm 2, inspired by the path kernel algorithm in [TW03], we define of (u, -) as probability distribution over the outneighbors of vertex To determine the bid vector in each round, we use random walk starting from the source z-, where the learner selects random neighbor using (2 then selects random neighbor 22 of 21 using &f (2). and so on, until reaching the sink 24. Remarkably, as we prove in Theorem 2, the distribution of the resulting path p is the same as that in the Multiplicative Weight Update (Hedge) algorithm [LW94].
of z
Thus while the number of paths in the DAG (corresponding to experts in the Hedge algorithm) is exponentially large,
the Hedge algorithm with polynomial space and time complexity by leveraging the DAG structure. We do not need to keep track of the weights of every path, but only need to store and update the weights of every edge in the DAG using the variables Φ'(e) and the recursive formula in equation (5). To accomplish this, we use the variables (u), for every vertex in the DAG, which can be viewed as the weights of paths starting at vertex u.
We obtain the next theorem, the proof of which can be found in Appendix B.
Theorem 2. For each player and time horizon T, under full-information feedback, Algorithm runs in time ( and guarantees the player's regret is at most O T log T).

---

4.2 Bandit feedback
The next theorem presents an upper bound on the regret under the bandit feedback. Similar to the -ulliinformation case, the algorithm we design works for both the K-th and (K+1)-st price auctions.
Theorem 3. For each player i and time horizon T, there is algorithm for bidding in the repeated auction with bandit feedback that runs in O + K K-b/177/1y and guarantees the player's 's regret is bounded by O min V/3K² T, }TT).
We describe the algorithm below, while the proof of the theorem be found in Appendix B.
The bidding strategy and its efficient implementation are the same as those the proof of Theorem 2, with the only difference follows. Under bandit feedback, we are not able to compute w' (e) for every edge e at the end time t; instead, we are able to compute w' (e) for every edge on the chosen path pt time t. This observation motivates us to use the next unbiased estimator w (e):
Th (e(e) wee) wi() we(e)
(e) (eEp*):
with (e())
Σ Pt(p),
(6)
P:EEP
where p is the player's action distribution over paths, and for each edge e:
- + j(r 5)
if (En Zaittli if (2,,K, 2+); if 2r,1)
(<(e)
U1 + Kr
The resulting algorithm is exactly the same Algorithm 2, with the only difference being that all wt are replaced by wt, with an additional step (6) for the computation of 0²
The regret analysis will appear similar to that in [GLLO07], but a key difference is that no longer have w/ (e) I V1,1 for every edge e in our setting. Instead, we apply an edge-dependent upper bound w (e) S (e)), and use the property that Eeep w(e) s K0;,1 for every path p from source to sink.
4.3 Regret lower bounds
The following theorem establishes D(KVT) lower bound on the minimax regret of single bidder in the full information scenario. Clearly the same lower bound also holds for bandit feedback.
Theorem 4 (restated, formal). Let K 2. For any policy n. used by player i, there ists a bid sequence (b',)T= for the other players such that the expected regret in (3) satisfies E(Reg, (Tt, (b',) 2 KV,, where O is absolute constant.
The proof of Theorem is in Appendix B. The idea employ the celebrated Le Cam's two-point method, but the construction of the hard instance is rather delicate to reflect the regret dependence on K. We also remark that this regret lower bound still exhibits gap compared with the current upper bound in Theorem 2, while it seems hard to extend the current two-point construction to Fano-type lower bound arguments. an outstanding question to close this gap.
Concluding Remarks
Several open questions arise from this work. For example, is the regret O(KVT) in both the full information and bandit setting? In the full information setting, the challenge in obtaining al- gorithm with regret O is that the expert distribution is not product distribution over the layers, but rather only close to a product. Furthermore, how does offline and online learning take place in repeated auctions when the units not identical, the valuations do not necessarily exhibit diminishing returns, or the pricing rule is different (e.g. in the first price setting)?
10

---

References
[ABL14] J-Y. Audibert, S. Bubeck, and G. Lugosi. Regret in online combinatorial optimization. Mathematics of Operations Research, 39(1):31-45 2014.
[AC05] I.. Ausubel and P. Cramton. Dynamic auctions in procurement. Handbook of Procure- ment, 2005.
[ACP+14] I.. Ausubel, P. Cramton, M. Pycia, M. Rostek, and M. Weretka. Demand reduction and inefficiency in multi-unit auctions. The Review of Economic Studies, 8 81(4):1366-144 2014.
[AHPI3] E. Anderson, P. Holmberg. and A. Philpott. Mixed strategies in discriminatory divisible-goon good auctions. The RAND Journal of Economics, 44(1):1-32, 2013.
[Aoy03] M. Aoyagi. Bid rotation and collusion in repeated auctions. Journal of Economic Theory, 112(1):79-055, 2003.
[AR08] E. Abemethy, Jand Hazan and A. Rakhlin. Competing in the dark: An efficient algo- rithm for bandit linear optimization. In COLT, pages 263-273, 2008
[ASO8] E. Anderson and D. Simester. Price stickiness and customer antagonism. Available at SSRN 1273647, 2008
[AVGN17] E. Areyan Viqueira, A. Greenwald, and V. Naroditskiy, On approximate welfare- and -venue-maximizing equilibria for size-interchangaable bidders. In AAMAS, page 1666-1468, 2017.
[BB01] J. Bower and D. Bunn. Experimental analysis of the efficiency of uniform- prince ver- sus discriminatory auctions in the england and wales electricity market. Journal of economic dynamics and control, 25(2-454444))) (53--))561-552 2001.
[BBW15] Balseiro, Besbes, and G. Y. Weintraub. Repeated auctions with budgets in ad exchanges: Approximations and design. Management Science, 61(4):864 - 884, 2015.
[BCI+05] C. Borgs, J. Chayes, N. Immorlica, M. Mahdian, and A. Saberi. Multi-unit auctions with budget-constrained bidders. In ACM EC, pages 44-51, 2005.
[BF19] S. Brânzei and A. Filos-Ratsiae Rats-Rassikss. Walrasian dynamics in multi-unit markets. In AAAI, pages 1812-1819. AAAI Press, 2019.
[BFMZ17] S. Brânzei, A. AillosRatsskaas, P. B. Miltersen, and Y. Zeng. Walrasian pricing in multi- unit auctions. In MFCS, volume 83 of LIPles, pages 80:1-80: 2017.
[BGM 22] S. Balseiro. N. Golrezaei, M. Mahdian, V. Mirrokni, and J. Schneider. Contextual bandits with cross-learning. Mathematics of Operations Research, 2022.
[BGNO3] Y. Bartal, R. Gonen, and N. Nisan. Incentive compatible multi unit combinatorial auctions. In TARK, pages 72-87, 2003.
[BILL23] M. Babaioff, N. Immorlica, Y. Li, and B. Lucier. Making auctions robust aftermar- kets. In ITCS, 2023.
[Bl556] D. Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1):1-8, 1956.
[BLNL14] M. Babaioff, B. Lucier, N. Nisan, and R. P. Leme. On the efficiency of the walrasian mechanism. In ACM EC, pages 700. ACM, 2014.
[BMSW18] M. Braverman, Mao, J. Schneider, and M. Weinberg. Selling to a no-regret buyer. In ACM EC, page 523 538. Association for Computing Machinery, 2018.
[BMT19] G. Birmpas, Markakis, and Telelis. Tight welfare guarantees for pure nash equi- libria of the uniform price auction. Theory Comput Syst, 63:1451 1469, 2019.

---

[BN07] L. Blumrosen and N. Nisan. Combinatorial auctions. 267:300, 2007.
Algorithmic game theory,
[Bon63] O. N. Bondareva. Some applications of linear programming methods the theory of cooperative games. Prob. Kibern., 10:119 133, 1963. Published in Russian.
[BR11] K. Bhawalkar and T. Roughgarden. Welfare guarantees for combinatorial auctions with item bidding. In SODA, 2011.
[BS00] K. Binmore and J. Swierzbinski. Treasury auctions: Uniform or discriminatory? Re- view of Economic Design, 5:387-410, 2000.
[BW20] J. Burkett and K. Woodward. Uniform price auctions with a last accepted bid pricing rule. Journal of Economic Theory, 185(10):49 54, 2020.
[BZ93] K. Back and Zender. Auctions of divisible goods: On the rationale for the treasury experiment. The Review of Financial Studies, 6(4):733-764, 1993.
[CAEFF16] V. Cohen-Addad, A. Eden, M. Feldman, and A. Fiat. The invisible hand of dynamic market pricing. ACM EC, pages 383-400 2016
[CBL06] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge univer- sity press, 2006.
[CBL12] N. Cesa-Bianchi and G. Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 184-41244- 2012.
[CCDP21] E. Calvano, G. Calzolari, V. Denicoló, and S. Pastorello. Algorithmic collusion with imperfect monitoring. International Journal of Industrial Organization, 79:102712, 2021.
[CD17] Y. Cai and C. Daskalakis. Learning multi-item auctions with (or without) samples. In FOCS, 2017.
[CK02] Cramton and S. Kerr. Tradeable carbon permit auctions. Energy Policy, 30:333-345, 2002.
[CSS07] Peter Cramton, Yoav Shoham, and Richard Steinberg. An overview of combinatorial auctions. ACM SIGecom Exchanges, 7(1):3-14, 2007.
[CTPL15] R. Combes, M. Sadegh Talebi, A. Proutiere, and M. Lelarge. Combinatorial bandits revisited. In NeurlPS, pages 21 2116-2124, 2015.
[CWY13] W. Chen, Y. Wang, and Y. Yuan. Combinatorial multi-armed bandit: General frame- work and applications. In ICML, pages 151-159, 2013.
[DGJ+22] Y. Deng, N. Golrezaci, P. Jaillet, Liang, and V. Mirrokni. Fairness in the autobidding world with machine-leareee advice. arXivv2209.04777 249444448 2022.
[DGPL19] M. Derakhshan, N. Golrezaei, and R. Paes Leme. Lp-based approximation for person- alized reserve prices. In ACM EC, pages 589-589, 2019.
[HH08]] V. Dani, T.P. Hayes, and S.M. Kakade. Stochastic linear optimization under bandit feedback. In ALT, pages 355-366, 2008.
IDHL+17) M. Dudík. N. Haghtalab, H. Luo, R. E. Schapire, V. Syrgkanis, and J. W. Vaughan. Oracle-efficient learning and auction design. In FOCS, 2017.
[DHP17] N. R. Devanur, N. Haghpanah, and C.-A. Psomas. Optimal multi-unit mechanisms with private demands. In EC, pages 41-42,
[DL14] S. Dobzinski and R. P. Leme. Efficiency guarantees in auctions with budgets. In ICALP, pages 392-404. Springer, 2014.
[DIN12] S. Dobzinski, Lavi, and N. Nisan. Multi-unit auctions with budget limits. Games and Economic Behavior, 74(2)4486503, 2012.
12

---

[DM08] R. Day and P. Milgrom. Core-selecting package auctions. Int. J. Game Theory, 36(3 4073 mar 2008.
[DN07] S. Dobzinski and N. Nisan. Mechanisms for multi- unit auctions. In ACM EC, pages 346-351, 2007.
[DN15] S. Dobzinski and N. Nisan. Multi-unit auctions: beyond roberts. JET, 156:14-44 2015.
[DPS21] M. Derakhshan, D. Pennock, and A. Slivkins. Beating greedy for approximating re- serve prices in multi-unit veg auctions. In SODA, pages 1099-1118. SIAM, 2021.
[DS16] C. Daskalakis and V. Syrgkanis. Learning in auctions: Regret is hard, envy is easy. In FOCS, pages 219-228, 2016.
[DVV03] De Vries and R. Vohra. Combinatorial auctions: A survey. INFORMS Journal on computing, 15(3):284-303 2003.
[Edg81] Y. Edgeworth. Mathematical psychics: An essay on the mathematics to the moral sciences. London: Kegan Paul, 1881.
[EWK98] R. Engelbrecht-Wiggans and C. M. Kahn. Multi-unit auctions with uniform prices. Economic Theory, 12:227-255 258. 1998.
[FFLS12] M. Feldman, A. Fiat, S. Leonardi, and Sankowski. Revenue maximizing envy-free multi-unit auctions with budgets. In ACM EC, pages 532-549, 2012.
[FGL14] M. Feldman, Gravin, and B. Lucier. Combinatorial auctions via posted prices. In SODA, pages 123-135. SIAM, 2014.
[FMTV20] M. Flammini, M. Mauro, Tonelli, and C. Vinci. Inequity aversion pricing in multi- unit markets. In ECAI, volume 325, pages 91-98. IOS Press, 2020.
[FPS18] Feng, Podimata, and Syrgkanis. Learning to bid without knowing your value. In ACM EC, pages 505-522. ACM, 2018.
[FR03] G. Federico and D. Rahman. Bidding in electricity pay-as-bid auction. Journal of Regulatory Economics, 24(2):175-22 211, 2003.
[FvdFH06] N. Fabra, N-H von der Fehr, and Harbord. Designing electricity auctions. The RAND Journal of Economics, 37(1):23-46, 2006.
[GHK+05] V. Guruswami, J. Hartline, A. Karlin, D. Kempe, C. Kenyon, and F. McSherry. On profit-maximizing envy-free pricing. In SODA, pages 1164-1173, 2005.
[G105] K. Garbade and J. Ingber. The treasury auction process: Objectives, structure, and recent adaptations. Structure, and Recent Adaptations, 2005.
[Gil59] D. B. Gillies. Solutions general non-zero-sum games. Contributions the Theory of Games, 40, 1959. In Tucker, A. W.; Luce, R. D. (eds.). Contributions to the Theory of Games IV. Annals of Mathematics Studies.
[GIL20] K. Goldner, Immorlica, and B. Lucier. Reducing inefficiency in carbon auctions with imperfect competition. In ITCS, 2020.
[GJL23] N. Golrezaci, Jaillet, and J. Liang. Incentive-aware contextual pricing with non- parametric market noise. In AISTATS, pages 9331 PMLR, 2023.
[GJLM21] N. Golrezaci, P. Jaillet, J. Liang and Mirronni. Bidding and pricing in budget and roi constrained markets. w:Xiv:2107.07725. 2021.
[GJM21] N. Golrezaei, A. Javanmard, and Mirrokni. Dynamic incentive-aware learning: Ro- bust pricing in contextual auctions. Operations Research, 69(1):297-314, 2021.
13

---

[GLLO07] András György. Tamás Linder, Gábor Lugosi, and György Ottucsák. The on-line short- est path problem under partial monitoring. Journal of Machine Learning Research, 8(10), 2007.
[GML13] G. Goel, V. S. Mirrokni, and R. P. Leme. Clinching auctions with online supply. In SODA, pages 605-619, 2013.
[GN92] R. J. Green and D. M. Newbery. Competition in the british electricity spot market. The Journal of political economy, 100(5):929 953, 1992.
[GNR15] G. Goswami, T. H. Noe, and M. J. Rebello. Collusion in Uniform-Price Auctions: Ex- perimental Evidence and Implications for Treasury Auctions. The Review of Financial Studies, 93))7777-785, 06 2015.
[GS13] L. H. Goulder and A. R. Schein. Carbon taxes versus cap and trade: A critical review. Climate Change Economics, 4, 2013.
[HG13] S. Heim and G. Götz. Do pay-as-bid auctions favor collusion? evidence from ger- many's 's market for reserve power. Evidence from Germany's 's Market for Reserve Power, 2013.
[НКMNI]] A. Hassidim, H. Kaplan, Y. Mansour, and N. Nisan. Non-price equilibria in markets of discrete goods. In EC,, pages 295 296, 2011.
[HP89] K. Hendricks and R. Porter. Collusion in auctions. Annals of Economics and Statistics, Jul- (ul-Dec(15-16))217222
1989.
[HZ Y. Han, Z. Zhou, A. Flores, Ordentlich, and Weissman. Learning to bid optimally and efficiently in adversarial first-price auctions, 2020.
[HZW20] Y. Han, Z. Zhou, and T. Weissman. Optimal no-regret learning in repeated first-price auctions. CoRR, abs/2003.0977 ..9990,...99,..... 2020.
[KCPTОI] A. Kahn, P. Cramton, R. Porter, and R. Tabors. Uniform pricing or pay-as-bid pricing: dilemma for california and beyond. The Electricity Journal, 14(6):70-79, 2001.
[KN04] I. Kremer and K. G. Nyborg. Underpricing and market power in uniform price auctions. The Review of Financial Studies, 17(3):849-877, 2004.
[KN14] Y. Kanoria and H. Nazerzadeh. Dynamic reserve prices for repeated auctions: Learning from bids. In WINE, volume 8877, page 232. Springer, 2014.
[Koc07] L. Koezy. A recursive core for partition function form games. Theor. Decis., 63:41-51, 2007.
[Koc09] L. Koczy. Sequential coalition formation and the core in the presence of externalities. Game. Econ. Behav, 66(1):559-565, 2009.
[KVO5] A. Kalai and S. Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 7 71(3):291-307 2005.
[LB10] B. Lucier and A. Borodin. Price of anarchy for greedy auctions. In SODA, pages 537-553, 2010.
[LMMM11] G. Lopomo, I. Marx, D. McAdams, and B. Murray. Carbon allowance auction design: an assessment of options for the united states. Review of Environmental Economics and Policy, 2011.
[LMT18] Sanna LaksA;, Daniel Marszalec, and Alexander Teytelboym. Epic fail: How below- bid pricing backfires in multiunit auctions. CIRIE F-Series CIRJE-F-1096, CIRIE, Faculty of Economics, University of Tokyo, 2018
[LS11]] Lattimore and Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. In AISTATS, volume 54, pages 728-737. PMLR, 4 2017.
14

---

[LS20] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[LW94] Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Infor- mation and computation, 108(2):212-2) 2611, 1994.
[MA98] Paul F Malvey and Christine M Archibald. Uniform-price auctions: Update of the treasury experience. US Treasury, 1998.
[MCP14] S. Magureanu, R. Combes, and A. Proutiere. Lipschitz bandits: Regret lower bound and optimal algorithms. In COLT, volume 35, pages 975-999. PMLR, 2014.
[MLS18] Mao, Leme, and J. Schneider. Contextual pricing for Lipschitz buyers. In NewrIPS, pages 5643-5651, 2018.
[MM16] M. Mohri and A. M. Medina. Learning algorithms for second-price auctions with reserve. The Journal of Machine Learning Research, 17(1):2632-2666, 2016.
[MR16] J. Morgenstern and T. Roughgarden. Learning simple auctions. In COLT, volume 49, pages 1298-1318. PMLR, 23-26 Jun 2016.
[MRH89] E. Maskin, J. Riley, and F. Hahn. Optimal Multi- Uoiti-Unit.ae Auctions, pages 312-335, Oxford University Press, 1989. Reprinted in P. Klemperer, The Economic Theory of Auctions, London: Edward Elgar, 2000.
[MRT09] A.J. Mersereau, P. Rusmevichientong, and J.N. Tsitsiklis. A structured multiarmed bandit problem and the greedy policy. IEEE Transactions on Automatic Control, 54(12):2787-288) 2802, 2009.
[MT15] E. Markakis and O. Telelis. Uniform price auctions: Equilibria and efficiency. Theory Comput. Syst., 57(3):549 5759995752220 2015.
[NCKP22] T. Nedelec, C. Calauzenes, N. El Karoui, and V. Perchet. Learning in repeated auctions. Foundations and Trends Machine Learning, 1563):176-334, 2022.
[NGW+21] R. Niazadeh, N. Golrezaei, J. Wang, F. Susan, and A. Badanidiyuru. Online learning via offline greedy algorithms: Applications market design and optimization. InACM EC, pages 737-738, 2021.
[Nis14] N. Nisan. Algorithmic mechanism design through the lens of multi-unit auctions. Handbook of Game Theory 4, 2014.
[Pes00] M. Pesendorfer. A study of collusion in first-price auctions. The Review of Economic Studies, 63(3):38--411, 2000.
[RM21] Aviv Rosenberg and Yishay Mansour. Stochastic shortest path with adversarially changing costs. arXiv:2006. 15611, 2021.
[RST17] T. Roughgarden, V. Syrgkanis, and E. Tardos. The price of anarchy in auctions. J. Artif. Intell. Res., 59:59-101, 2017.
[RT10] Rusmevichientong and Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 41,, 2010.
[RW16] T. Roughgarden and J. Wang. Minimizing regret with multiple reserves. In ACM EC, pages 601-616, 2016.
[SBLS04] Y. S. Son, R. Baldick, K-H. Lee, and S. Siddiqi. Short-term electricity market auction game analysis: uniform and pay-as-bid pricing. IEEE Transactions on Power Systems, 1994)1990-, 2004.
[Sek17] S. Sekar. Posted pricing sans discrimination. In IJCAI, pages 388-399 088-394,1 2017.
[Sha67] I.. S. Shapley. On balanced sets and cores. Nav. Res. Logistics Quart., 14:453 460, 1967.
15

---

[SMR*13] 13] S.Brânzei, T. P. Michalak, T. Rahwan, K. Larson, and N. R. Jennings. Matchings with externalities and attitudes. AAMAS, pages 295-302. IFAAMAS, 2013.
[SS69] L. Shapley and M. Shubik. market games, Journal of Economic Theory, 1(1):9-25, 1969.
[SS17] R. Schmalensee and R. N. Stavins. Lessons learned from three decades of experience with cap and trade. Review of Environmental Economics and Policy, 11, 2017.
[TSM08) S. Tierney, T. Schatzki, and R. Mukerji. Uniform-pricing versus pay-as-bid in whole- sale electricity markets: Does it make difference? New York ISO, 2008.
[Tsy09] A. Tsybakov. Introduction to Nonparametric Estimation. Springer- Verlag, 2009.
[TWO3] E. Takimoto and M. Warmuth, Path kernels and multiplicative updates. The Journal of Machine Learning Research, 4:773-818, 2003.
[UNK10] T. Uchiya, A. Nakamura, and M. Kudo. Algorithms for adversarial bandit problems with multiple plays. In International Conference on Algorithmic Learning Theory, pages 375-389, Springer, 2010.
[vdFH93] N-H. der Fehr and D. Harbord. Spot market competition in the uk electricity industry. The Economic journal (London), 103(418):531-546, 1993.
[VPG20] B. Van Parys and N. Golrezaei. Optimal learning for structured bandits. arXiv:200..07302, 2020.
[Wi179] R. Wilson. Auctions of shares. The Quarterly Journal of Economics, 93(4):675-689, 1979.
[WJ08] M. Wainwright and M. Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends@ in Machine Learning, 1(1-2):1-305, 2008.
[WPR16] J. Weed, V. Perchet, and P. Rigollet. Online learning in repeated auctions. In Confer- ence on Learning Theory, pages 1562-1583, 2016.
[ZLW19] Zimmert, H. Luo, and C-Y. Wei. Beating stochastic and adversarial semi-bandits optimally and simultancously. In ICML, pages 7683-7692. PMLR, 2019.
[ZN13] A. Zimin and G. Neu. Online learning in episodic markovian decision processes by relative entropy policy search. NeurlPS, 26, 2013.
16

---

Roadmap to the appendix
Appendix A includes the proofs omitted from Section (Offline Setting). Appendix B includes the proof' omitted from Section 4 (Online Setting). Appendix C includes the equilibrium analysis. A few results from prior work that we invoke are in Appendix D.
A Appendix: Offline Setting
In this section we include the proofs omitted from the main text for the offline setting.
Observation 1 (restated), Player i has an optimum bid vector 3 = (B E D with By S₁ for all j E [K].
Proof. Let c (c....,, (x) be an arbitrary optimum strategy for player i. Suppose c & SK We use с to construct an optimum bid vector 3 E S.K as follows. For each j E [K]:
If eg E S5, then set 33 = =G.
* Else, set 83 = max (u E St Selve c.
Then in each round I, player gets the same allocation when playing 33 as does when playing c and the others play b', since the ordering of the owners of the bids is the under (c, b", as is under (3, b' :) moreover. the price weakly decreases in each round Thus player i's utility weakly improves. Since was an optimal strategy for player i, it follows that f is also an optimal strategy for player and, moreover, 3 E S.K required.
Next we show how to find an optimal bid vector in polynomial time. The proof uses several lemmas, which are proved after the theorem.
Theorem (restated, formal), Suppose we are given a number of players, number of units, valuation V. of player i, discretization level e >> O, and bid history H (b'....., b²,) by players other than i. Then an optimum bid vector for player i can be computed polynomial time in the imput parameters.
Proof of Theorem I. Compute the set S, given by equation (1) and the graph G, from Definition 1. The proof has several steps as follows.
G2 is DAG. All the edges in G, flow from the source x_ to the nodes from layer 1, then from the nodes in layer j to those in layer j ++1 (i.e. of the form (ær.j, Ze.j+1) for all E [K-1] and r, E S with r 2 s). and finally from all the nodes in layer K the sink 24. A cycle would require least one back edge, but such edges do not exist.
Bijective map between bid vectors and paths from source to sink in Gi. To each bid vector
(3 .., E S.K. associate the following path in G;: P(B) 2- 28, ... 2fx Ks 2+)
We show next the map is a bijection from the set S; of candidate bid vectors for player to the set of paths from source to sink in G, Consider arbitrary bid vector B (B1, 10,,.... BK) ) E SK By
definition of a bid vector, we have 31 2 ... 2 3K Then P(3) = (2_, 29,1, 23x K 2+ is valid path in G,
Conversely, since G, has an edge (Zngj Rz.j (1)+++)+)))))) if and only if 2 8, each path from source to sink in G2 has the form Q (=_, 28,,1, 1.... ....... 28x,K K, =_) for some numbers $I...., 3x E S,, and so it can be mapped to bid vector 3 =
Thus Q = P(3). and so is a bijective map.
Utility of player and weight of a path of length K in G.. Let Additionally, let 3K-1 = 0. The total utility of player when bidding B in each round & while the others bid by_ is (,) = ΣT u,(h), where h' = (B, b(, VI E [7].
(B...., 3K) E S.K.
17

---

Let P(3) = (2- 23,.1.................,...,.. K 2+) be the path in G; corresponding to 3. The edges of the path P(3) are (2_, path is equal to the of its edges. Summing equation (2), which gives the weight of an edge, across all edges of ((3) implies that the weight of path (()) is equal to
28..2).......................... (23k_1.K-1, 2 xBxxx)x K). (2gx,K k.²+). while the weight of the
w(((3))) ΣΣ
1 A000 - B3) + (1 (s:00)s)) (3, B5+1) + 1 (m200)=)) p( p(hh)))
We claim that (3) w (())). The high level idea is rewrite the utility "spread it" across the edges of the path corresponding to bid profile B. Towards this end, recall the utility of player strategy profile h' (G, b)_;) is
u (h') Σ 1 (20022 (p(s)((h))))))
(8)
By Lemma 1, equation (8) is equivalent u;(hi (hh)
K
Σ
L (2a Bj) + (1) B5+1) + (m((()))) p(hh)))]
(9)
Summing u; u;'h') over all rounds t gives
T
U,(3) =
Σ
u/ (hh)))
1=1
T
(0:00)20)013 + ( (1,101)))))) Bz+1) + (x,(h))=)) p(h')))
(By equation (9)
K T
ΣΣ j=1
(1:0))25)))) B,) + (1 (I(0 - Bz+1) + (ax(h)))) p p(h')))
(Swapping the order of summation) (By equation (7))
w(P(B))
Thus the weight of the path P(3) is equal to the utility of player i from bidding B. The implication that to find an optimum bid vector, it suffices to compute a maximum weight path in G,-
Computing maximum weight path in G,, The graph G is DAG with number of vertices of G, that is polynomial the input parameters. By Lemma 2, the edge weights of G, can computed in polynomial time.
maximum weight path in DAG can be computed in polynomial time by changing every weight to its negation to obtain graph -G. Since G' has no cycles, the graph -G has no negative cycles. Thus running shortest path algorithm on -G will yield a longest (i.e. maximum weight) path on G in polynomial time, as required.
The unique bid vector corresponding the maximum weight path found then be recovered in time (K) and it represents an optimum bid vector for player i.
Lemma 1. the setting of Theorem I, for each bid profile B SK and round t e [T], define h' = (B, b².). Then we have
K
u: wa(h')
Σ
[1 (2.00)22)) B3) + (1 (2.00))))))) BB41) 1 1 (o,(h))=) p(h')))]
(10)
18

---

Proof. Given bid profile 3 = (x), we also define 5x+1 = 0.
If v. (h') then both sides of equation (10) zero, the statement holds. Thus it remains prove equation (10) when z; (h²) > O. Let (ky(h") = 1 (w,)))) (Va.j p(h') for each j E [K]-
The term (h") represents the amount of utility obtained from the j-th unit acquired by player K at price p(h'), so (h')) Σj= 4cy(h")
We first show that for each j E [K]]
ue.(hh) (z.(h))2))) By) Σ
1 (m.(h))2)) (5x - Bk+1) + 1 (z.(h))= p(h'))
(11)
To prove (11), we will rewrite (h'(h') by considering three cases and writing unified expression for them.
1. 1. (h') j. Then
un ui.(h') vij p(h²) (ci 8j) + (B, -p(h')
1(m:(h122))(01 - -3,) + (knn( -p(h')
(10001922)) - -3,) + Σ (2)()))))) (Bx 3x-1) + (x=0)))=)))( (ak-)(hh))) p(h'))] b=
(Since (x,(1)>)) = 0 vk 2 and (()(()))=)) = and only if j.)
2. xr; xr;hh' j. Then z; (h') = j + f, for some e E f1, fI..... K)j). We have
u = Vis -phh)
(Ur.) - -B,) + (B/ - -Bjte) + (Bgte -p(h')
j+t-1
= (vii--B +
Σ
Bx 3x+1
+ (1854e-((h))
(12)
We are in the case where (2,(h))2)) = 1, (2,(b))))) = if and only if E .J..... +
f. 1}. and 1 (x,(h()=k) = if and only if h = + Adding indicators to the terms in (12) gives
Us. (h') = 1(m/(122)(015 - -3)) + Σ
((n(h)))4)) (3x - 3x-1)) + k=j
( [())(k)=2)) - p(h'))
3. xr (h') j. Then 1 (2.(h))23) 0, 1 (m:(he)>4)) for all i {j...., K}. and (x2(ht))= 0 for all k E (j....,K KJ. Thus we trivially have the identity required by the lemma state- ment since Uz, (h') and the right hand side (11) is zero as well.
Thus equation (11) holds in all three cases as required.
For each i [n] and j E [K], define
k
A.
Σ
(e.00))00)(8 - 9K+1) + (e,()))))) --(h)))
(13)
Then equation (11) is equivalent to
(h,)(h") = (2) - B3) + Aij.
(14)
19

---

Summing equation (13) over all j E [K] gives
K
Σ
A
(z,(he)>)) (Bc - Bk+1) + + (2,(60)= p>(h)(h))))
(15)
K
(xith)) - -B++1) + (z. (b)))) -p(h'))
(16)
K
K
(3x- - BK+1) Σ (.((b)))) +
Σ
(3x - p(h"))
Σ
((,))))))
(17)
k=1
j=1
K Σ (Bx - Bk+1) h (2.()))) +
K
(Ok - p(h')) k (2,(h))o)
(18)
1=1
k=1
where equation (a) holds because we change the order of the double summations and in the double summations, we consider any (integer) pair of (j, k) such that s k $ j s K.
Then we rewrite the utility u:(h')
uy mh'hh)
Us.5 (h')
Σ (1 BB) Aij]
(By equation (11))
K
k
K
Σ
1000022))) -33) + > (B, Bz+1) -j- 1 (m)(h))))
+
(3, p(h')) j (a;(k))-5)
j=1
k=1
(By equation (18))
K -' (100)22) - 3₂) + (1,000)))))8 - -3+1) + (x.0))=))) - 100--p(h))) p(h'))]
j=1
as required by the lemma statement.
Lemma 2. In the setting of Theorem 1, the edge weights of the graph G, can be computed in polynomial time.
Proof. Recall the graph G; constructed given as parameters the number n of players, the number of units K, a player i with valuation v,, discretization level > O. and a bid history H (b'...... b_:) by players other than Thus the goal is to show the edge weights of G, can be computed in polynomial time in the bit length of these parameters.
Towards this end, we will show there exist efficiently computable values 15 11 E {0, and qº E S, such that the weight we of edge = (Zr.j: 2e.j+1) is equal to
We
(Ui r) + j 1 (r 5) + (r-
(19)
Roughly, q' will correspond to the price and 1 1 I3 will tell whether player gets more than units, least j units, exactly j units, respectively, at some profile B (B1,... 3x) S; with 33 = and By+1 = s. The choice of / in will not matter, as long as 3, = r and 35+1 = 8.
We prove equation (19) in several steps:
Step (i). For each E [T]. define re: + R, where
I' r'(x)= = K (e,5) (bb, > r and le [n] [t.j [K])
or (be, and é [n), < (K])
20

---

Thus I (x) counts the bids in profile b": that would have priority to a bid of value z submitted by player i (i.e. it counts bids strictly higher than z and submitted by players other than as well as bids equal to but submitted by players lexicographically before i).
Let B E S; be an arbitrary bid profile with Step (ii). Recall the edge denoted e =
33 r and Bj = s. Also define 3x+1 = O.
(s) K-j, j, then h (3, bL_ bb_;) player i receives one unit for each of the bids 31,..., 8z+1. since there are at most j-j -1 bids of other players that have higher priority than player i's highest j + bids. Else, player does not get more than j units. Thus /2 1l (x((h()>)>
Step (iii).
(r) < K -j. j. then player receives at least j units at (G, b),;). The corresponding indicator is
r -1((()))k))) {o:(()))))
Step (iv). (r) S - j and ((5) K j, then player receives exactly units at (3, bL
The indicator is
rj = ==( (<>)))>>>)> = (b)))))
Now suppose 1; = 1. Then we show the price q¹ = p(h") can be computed precisely without knowing the whole bid B.
Consider the multiset of bids B = UEB B5+1 J. recalling 8K+1 was defined as zero. Sort B in descending order. We know the top j bids of player are winning, so the price is determined by any of them. Thus the price is determined by Bj = r, 85+1 = 8, or by one of the bids in b' Remove elements . B from and set the price follows:
Case (iv.a). For (K + 1)-st price auction: set q' to the (K + 2- - 2)th highest value B.
Case (iv.b). For K-th price auction: set 9² to the (K + 1 - jh highest value in B.
Step (v). Combining steps (i-iv), the weight of edge (Zrg. Faj+1) can be rewritten as
(k())) (vi. r) + (1a)(1))2)) (r (r-s) 1 [m)( (r- p(h'))
(
We
(By Definition 1)
Σ 2 (ua - r)+ + (r
(By steps (i-iv))
Thus the weight of each edge can be computed in polynomial time as required.
21

---

B Appendix: Online Setting
In this section we include the material omitted from the main text for the online setting.
Before studying the full information and bandit feedback models in greater detail, we replace the set S; of candidate bids for player from equation (1) of the offline section by coarser set
S. - (c, .., ...
/s
The regret, which was defined in equation (3), depends on whether the model is the K-th or (K + 1)- price auction; however the next lemma holds for both variants of the auction.
Lemma 3. For all & > 0, let Reg, (Ti, H H_,,e) ) be the counterpart of (3) where St is replaced by the set S.. Then Reg, (TT HΣ)) I Reg, (T;, =) TKE.
Proof. First observe that it is not beneficial to bid above U1,1, SO we can assume without loss of generality that the maximizer [ in (3) satisfies 3g S 441 for all [K]. Now we convert & into another bid vector 3 E S. as follows: for each [K]. let
3 = min Se y 2 3/).
Clearly Bj S 83 S Bj +
Then we claim that the next inequalities hold:
p(0 b) S p(3, bb,,) + (Im,0rrb))) 2 (x.(0.b())))))
(20)
(21)
Inequality (20) follows since
p(b) is either the K-th or the (K + 1)-st largest element of b, and
increasing each entry of b by at most can only increase p(b) by no more than e.
Inequality (21) is due to the fact that bidding higher price can only help to win the unit.
Consequently, we have
K
ΣΣ =1
(o.. -(B,b'_) (o.
(oig p(B,bb.)) (ecisrrbb)220
j=l
(1.. p(BF,b',)) -6) 6) (m;(00,b1)22))
(vi. p(3 ,b..))))) 1 (m008r (2n (25) TKe.
This gives the desired statement of the lemma.
B.1 Full Information Feedback
In this section we include the omitted details for the full information setting.
We begin with the formal definition of the graph G = (V, E, w²) used by the online learning algorithm with full information feedback.
Definition 2 (The graph G¹), Given valuation v of player i, bid profile b' of the players at round t, and 0, construct graph Gt EV w²) as follows.
Vertices. Create a vertex 2a.j for each s E S, and index j E [K]. We say vertex and is in layer Add source z_ and sink 24-
Edges. For each index j E IK - and pair of bids Sz with 2 create directed edge from vertex žr.j to verlex 2s.j+1. Moreover, add edges from source z to euch node in layer and from each node in layer K to the sink 2
22

---

Edge weights. For each edge e (2r,5, 2a.j+1) ore (+), let 3 = (Bi.....P 3x) E s be bid vector with By = r and By+1 = s (we define s = if = K). Define the weight of edge as
w') - (m1((aL))2)) (vis -)) + i (a (r - + (2(bh)=s) (r- 11-ple p03,,b/1))) b'.))
The edges incoming from z_ have weight zero.
The next observation follows immediately from the definition.
Observation 2.
The next properties hold:
Gf can be computed efficiently (see Lemma 2). The weight (e) of each edge of G
There is bijective map between bid vectors B E SK of player i and paths from the source to the sink of G¹ (see proof of Theorem I).
Next include the main theorem with its proof for the online learning algorithm under full infor- mation feedback.
Theorem 2 (restated). For each player and time horizon T. under dall-information feedback, Algorithm 2 runs in time ( and guarantees the player's regret is at most O TTK
Proof. The detailed algorithm description is presented as Algorithm 2. At a high level, the proof has three parts: (i) showing that Algorithm 2 is correct implementation of the Hedge algorithm where each expert is a path from source to sink the DAG G' for time i, (ii) bounding its regret for an appropriate choice of the learning rate, and (iit) bounding the runtime.
Step Algorithm 2 is a correct implementation of Hedge. We show that Algorithm 2 is the same as the Hedge algorithm in which every path in the DAG is equivalent to an expert in the Hedge algorithm.
To do so, for each vertex a in the DAG, let ø² (u, .) be a probability distribution over the outneighbors of Then, given the recursive sampling of the bids based the probability distribution Ø ss the probability that a path is chosen in Algorithm 2 is equal to
p' (p) = (ee.
(22)
<EP
where o are updated in equation (5), which is restated below:
(w-1(w)
=e))) = (0- exp (n) w (e))
T r=-(uw) for all (u, E F(G').
(5 revisited .)
On the other hand, in the Hedge algorithm, the path probabilities are updated as follows: Given learning rate define Pj (p(p) ITeep 0² (e), and for 2,
(p) = px- (p) exp(1 EeEo w' (e) (e)
(23)
P/ (q) exp(1) Ecso w w()
The subscript 'h' in (p) stands for Hedge. To show that the update rule in Algorithm is equiva- lent to the one in Hedge, we first prove the following statement:
(i) For any vertex u in the graph, let P(u) be the set of all paths from u to 24. Then
Σ II (e)x(e))
(24)
(e)( eEq
23

---

We prove equation (24) by induction on from the bottom layer to the top layer. If u
2+, by
definition I (2+)
and (24) holds. Now suppose that (24) holds for all in the (k + 1)-st layer, for some 0 s k I K. Then if u is in the k-th layer, the recursion of [ gives that
(w)
Σ
(1, v)) exp(mu' v)) (v)
v((,))E
Σ
( exxpx))))ppp [xp,
Σ II qEP(w) eEq
(e) exp(mxl
v:(u,))E
Σ QEP(N) eEq
II
(e) exp(mx"
and therefore (24) holds.
Having shown equation (24), we prove by induction on claim that Algorithm 2 is correct
implementation of Hedge, i.e. that ((pp) = (p) for all paths and rounds l. For = 1, by definition of our initialization we have P/ (p) = Pl (p). Suppose that at time - 1, for every path
we have P/ (p) = pt- (p) ITeep 6² (e). Then at time t, holds that
[-1(0)
P'(p) II (e) .Ep
II
o' (e)
exp (1) - w (c))
e (a.
r (2+)
P
(p)
exp
Σ w (e)
(2-1(__)
eEP
where step (a) is due to equation (5), and step (b) follows using telescoping and the induction hy-
pothesis pp-) = Ileep (e).
Given equation (23), by applying equation (24) to u E {z-,z_} and the induction hypothesis
(p- ( (e), the induction complete.
Thus Algorithm a correct implementation of Hedge.
Step II: Regret upper bound.
Let
8= U1,1 K/T.
(25)
Applying Lemma 3 yields
Reg, H.)) S (T, HI,, + + = (eg +
(26)
where Reg, (m,, , e) is the counterpart of (3) where S; replaced by the set
S = = 22, ... [u,,//]
We also claim that Eeep (e) KU;, for each path p from source to sink in G To see this, let be the bid vector corresponding path p. As shown in Lemma and using the fact that edges outgoing from 2 have weight zero, we have (B, b Eeep (=).). Since player i's utility satisfies u. (B, b),)) < (3 I KV,1, obtain Eeep w² KV1,1-
By Step I, Algorithm 2 is correct implementation of Hedge. To bound the regret of the algorithm, will invoke Corollary I-which is a slight variant of [CBL06, Theorem 2.2]-with the following parameters:
N experts, where each expert is path from source to sink in G*;
learning rate 7, time horizon T, and maximum reward L Kv,,1
initial distribution a on the experts, where op pi(p) for each expert (path from source to sink) p.
24

---

By Corollary 1, we obtain
1 ( opp (1)++
TI 8
max log Reg. (m; H_,,e) E) -
(27)
PE[N]
Recall Algorithm 2 initially selects path by starting the source and then performing unbiased random walk in the layered DAG until reaching the sink 24- Since the number of vertices in each layer is [e the initial probability of selecting particular expert (i.e. path from source to sink) p is
Op = (p) 2
Vp E [N].
(28)
R
Substituting (28) in (27) yields
1
TL
K log ([va./El)
TL2n
(T; H {) max log PE(N]
Op
"
([v
K log
T (Kuu,1)
(Since 02 K and T. KV;,1.)
log
T
T (KKu,)))
(29)
"
For 1) vlog T (U / KT), inequality (29) gives
K log T
T Tooog T S(U,IVKT)
Reg, [ H.,,))
(Kei.))
Vog T (I,IVTT) KT)
0.11 TK*
(30)
8
Combining inequalities (26) and (30), we get that the regret of player i when rumning Algorithm 2 is
(eg H1_.) Reg, (T,, HT, + VTT
9 14,1 /TK3logT + %1 VTK3 E (O.
s
(31)
This completes the proof of the regret upper bound.
Polynomial time implementation. Finally we analyze the running time of the above algorithm. At every step, the computation of path kernels traverses all edges (note that each edge only appears in the sum once) and could be done in O El) = 0 Ku?
/////"") /e²) time. Similarly, the update of edge
probabilities o' for all edges also takes O( = O(K /e2) time.
Therefore, the overall computational complexity is O choice of = = U4 /LT/K/T This completes the proof of the theorem.
11, 166)) O(T2), where we used the
B.2 Bandit Feedback
In this section we include the main theorem and proof for the bandit setting. Recall that our algorithm for the bandit setting is the same as Algorithm 2, only with w'(e) replaced by T (e):
w(e) (e())
w=(e) 1 (cEp');
Th (e) w(e)
with p²(c)
Σ P'(p),
P:cE
with p given in (22), and
U1 +r
if (En Za.++1), if (2,,K, 24), if e = (z_,
(()
U1,1 - r Kr
25

---

The resolution parameter and learning rate are chosen to be
== U1,1 ( log T/T) n= 7=min
min ( (eVlog(or//))/(TKK> (((o))))
(32)
Theorem 3 (restated). For each player and time horizon T, under the bandit feedback, there is an algorithm for bidding that runs in time O + K (s////T//a and guarantees the player's 's regret is at most O(min (VL, (T's K" log T) U1, 1.,1 KT)).
Proof. By Lemma 3 and the choice of & in (32), it suffices to show that the above algorithm T; runs in time O(T vf.1/ ())) and achieves
K2 Reg, (TT, E) =0 p2. TK* log(v;, + Us K log log(vs.//))
The claimed result then follows from the fact that the regret is always upper bounded by O(vi, KT). Before we proceed to the proof, we first comment on the choice of estimator (e). First of all, this is an unbiased estimator of w' w'(e). i.c Epe=ps [0 (e)] = ('(e) weeihtte estimator w (e) w (e) (cEp") /p), the current form
(e) for every edge e in G Second, instead
of using the natural in (6) is the loss-based importance- importanco-weighted estimator used for technical reasons, similar to [LS20, Eqn. (11.)).. Third, by exploiting DAG structure and the definition of w w'(e) in (4), we construct an edge-specific quantity we) which always upper bounds w (e).
We now analyze the regret of the algorithm with (e) given by (6). The standard EXP3 analysis (see, e.g. [LS20, Chapter 11)) gives that
1 max log (p)
(EPtpeentto) Σ ('p)
Reg, (T., (T.
V E
log
1
11
(33)
where (p) = Eeep (e) is the estimated total weight of path p. and the expectation is with respect to the randomness in the estimator T² (e). For every path p (2-,2r1.1 : Frx.K. 2+)
from the source to the sink, we have (by convention TK+1 = 0):
K
(p)=
Σ w
(())
Σ
11.1 - - 1ir jrz+1) KVs,1.
cEp
cEp
j=1
Since ex < 1 x + x² whenever x < 1 and log(1 + y) S whenever y > -1, if S 1/(Kor.)) inequality (33) gives
T
1
Reg, (Ti H H c) < max log p((p)
+ 1)
P'(p) (p)
17 p
T
K
log
U1
Σ (p) (K + 11 > El (e)²),
eEP
where the last equality uses (Ein x:) 2 < n Σ xt and that each path p from the source to the
sink has length K 1. To proceed, note that
[e)'(c) w(e) (1 11-pp' p'(c)) w(()) w(e) (ee)-w((e) m((()) (e()
p'(e)
w'(e)² (T(e) (e))2 ( (p((e) -1).
and therefore
- =(()))) (x(C) ]
-1)
Σ
(p)
Σ
E
W1 (e) = Σ Pd (p) Σ
w'(c)2 + (w(())
P cEP
PEP
1 - :)] Σ P'(p)
= Σ
w (w(e))
(
P:EEP
Σ
(m))) p'(e) Σ w(e)²
26

---

where in the middle we have used the definition E ('(p) = p²(e) in (6). To further upper bound the above quantity, note that
Te) 2 S
Σ
(v + (j- 1)re)² ()-))r=
j j=1 1 S S [waa/e]
K [u,a/e]
1
(V+ 1)rs)²
[vea/e]
[ KK
U1,1
Σ (uf + + 1)-1)))88)) =0
2
E
E²
j=1
combination of the above inequalities shows that long as 17 S (K111,,))
Reg, (TT, H H) =
K
log
U1
1/ 1
17
E2
Next, by the choice of v in (32), we have
1h.1 TK' log(vi,1/))
Reg, ( e)) o
K K2v,,1 log
Ut
As for the computational complexity, the only difference from the Algorithm 2 is the additional computation of the estimated weights (e) in (6), or equivalently, the marginal probability (e). As ps has product structure in (22), the celebrated message passing algorithm in graphical mod- els [WJ08, Section 2.5.1] takes ((E))r,,1e)) = O(K / time to compute all edge marginals {p' (e)} Therefore the overall computational complexity is O
B.3 Regret Lower Bound
In this section we include the theorem and proof for the regret lower bound. The construction uses the (K + s) highest price, but is similar for the K-th highett price.
Theorem 4 (restated, formal). Let K 2. For any policy n; used by player i. there ists a bid sequence (b_,Y= for the other players such that the expected regret in (3) satisfies BlReg, (b' 11 2 eo,,KVII VT, where >> 0 is absolute constant.
Proof. Without loss of generality assume that K = 2k is an even integer, and by scaling we may assume that 1 = 1. Consider the following two scenarios:
the utility of the bidder i V.y = for all j [K]:
at scenario 1, for every 1 (T), the other bidders' bids are
0, .. with probability 0.5 + 6,
bz_
3..3. 2) with probability 0.5 5,
where the number of non-zero entries is l in the first line and 2k in the second line, and 6 E (0, 1/4) is parameter to be determined later. The randomness used at different times is independent.
* at scenario 2, for every t E [T']. the other bidders' bids are
0. ... 0) with probability 0.5 6,
bC_
with probability 0.5 6,
where the number of non-zero entries is & in the first line and 2 in the second line, and 8 E (0, 1/4) is parameter to be determined later. The randomness used at different times is independent.
27

---

We denote by P and Q the distributions of [b' under scenarios 1 and 2, respectively, then
(kl(P)))) = T DxL (Bem (0.5 + Bern (0.5 - -))
S T x (Berm(00.5 + 6)] Bern - 6))
(25)²
64 T82.
T (0.5 + (0.5- 6) - 3
Consequently, by [Tsy09, Lemma 2.6],
6478
1- -V 2 2
exp (-Dk) 2 exp 3
Next we investigate the separation between these two scenarios. It is clear that max Ep (b;; bL:)] Ep
[1,
,1,0, [],]]
b.
2 + 25
+ 8
h +
0
k;
2
2
3
3
max Eg [u; b':)] 2 Eq [4,(11,
,,,,,,
b):b",)]]
b;
-
1
2h
1
2k
2k
2 -
+
3
2
3
3
Moreover, under (P+ Q)/2 (i.e. bL_ follows Bern /2) distribution), suppose that the vector b; has k' components smaller than 2/3. Distinguish into scenarios:
kf < k, then
1
2k
K
2k
K
2k
[ur <
+
2
3
2
3
3
kf k then
1
2k
k'
2k
E/ [u,(b;; s
(2k
K)+
3
Therefore, always holds that
max E(42)//2 [u:(b;; b",)] - 2k
b.
3
Consequently, for each b,
max Ep [b; bl..) us (b,; b",)] + max Be [u;b;; u.;b;;; b",]] b;
by
2 max Ep (b, b' b'.)] max b;
Eq [b;;;; b' ) 2 max mmax (() [b,
b;
b:
2 28
2k
2k
25k
2
In other words, any bid vector b; either incurs total regret (BkT)/3 under P. or incurs a total regret (8 under Q.
Now the classical two-point method (see, e.g. [Tsy09, Theorem 2.2]) gives
5kT (1 (1- (V-TV(P.Q) 2
5kT exp
64
((P+0)/ (b', (b',
for every 1/4). Choosing 11((8T)) gives that
KVT
E E(p4t)/2(Reg(TT, (b= IT
9/3
i.e. the claimed lower bound holds with c = 1/ 1/(96e2/3)
28

---

C Appendix: Equilibrium Analysis
In this section show that the pure Nash equilibria with price zero of the (K + 1)-st auction the only ones that are robust to deviations by groups of players, captured through the notion of the core in the game among the bidders. The core of a game was formulated by Edgeworth [Edg8] I] and brought into game theory by Gillies [Gi159]. There is an extensive body of literature on the core of various games, including for auctions; see, e.g., analysis of collusion (cartel behavior) in first price auctions in [Pes00].
Our focus here is the core of the game among the bidders, where the auctioneer first sets the auction format and then the bidders can strategize and collude among themselves, without the auctioneer. Roughly speaking, strategy profile core-stable if no group C. of players deviate simultane- ously (i.e. each player i E C deviates to some alternative strategy profile), such that each player in C weakly improves and the improvement strict for least one player. For a deviation take place, the players in C' coordinate and switch their strategies simultaneously. while the players outside C keep their previous strategies. Every core-stable strategy profile is also Nash equilibrium, since strategy profile that is stable against deviations by groups of players is also stable against deviations by individuals.
We consider two variants of the core, with and without monetary transfers [SS69, Bon63, Sha67]. In the case with transfers, the players profile consists of a tuple of bids and transfers. In the case without transfers, the players cannot make such transfers and their strategy is the bid vector; thus the only agreement they can make in this case is to coordinate their bids.
make monetary payments to each other, and strategy
C.1 Core with transfers
A strategy profile in this setting is described by tuple (b, t). where b is bid profile and t is profile of payments (aka monetary transfers), such that (4 2 0 is the monetary payment of player i to player j. At this strategy profile, the auctioneer runs the auction with bids b and returns the outcome (price and allocation), while the players make the monetary transfers t to each other.
For each profile of monetary transfers t, let mt,t) be the net amount of money that player gets after all the transfers are made:
n
n
m²(t)
Σ
tij
The utility of player i at profile (b, t) is
(b)
u t) = m; (t) +
Σ Ui.j
p.p.. (b).
Deviations. Since in the case of auctions the actions (e.g. bids) of a group of players can affect the utility of the players outside of the group, it is necessary to model how the players outside S react to the deviation. Such reactions have been studied in the literature on the core with externalities (see, e.g.. [Koc07, Koc09]).
We consider neutral reactions, where non-deviators (i.e. players outside S) have mild reaction to the deviation: they maintain the same bids as before the deviation and the monetary transfer of each player i e [x]] S to each player j S is non-negative. The core where the deviators assume the non- deviators will have neutral reactions to the deviation is known as the neutral core [SMR + 13]. Several other variants of the core exist, such as pessimistic core, where each deviator assumes that they will be punished in the worst possible way by the non-deviators. Such variants are also interesting to study, but next we focus on the basic case of neutral reactions.
A group of players will alternatively be called a coalition. The set of all players, [n], will also be called sometimes the grand coalition.
group of players that agree on deviation are known as blocking coalition, formally defined next.
29

---

Definition 3 (Blocking coalition, with transfers). Let (b,t) t) be tuple of bids and monetary trans- fers. A group S [n]] of players is blocking coalition there exists profile (b, t). which each player i E S weakly improves their utility, the improvement is strict for at least one player in S, and
bis bus if E [n] S [K].
[, = Of in] and j E S.
In other words, the blocking coalition S needs to agree on their bids and transfers to each other, such that they improve their utility when the players outside S maintain their existing bids but stop payments to players in S. In fact our characterization holds even if the players outside S make any non-negative transfers to the players in S; the case where the transfers are zero is the extreme case. If a coalition S deviates with zero transfers from players outside S, it also deviates for any transfers that are non-negative.
Definition 4 (The core with transfers). The core with transfers consists of profiles (b, t) at which there are blocking coalitions. Such profiles core-stable.
Theorem 6 (Core with transfers; restated). Consider units and n. > K hungry players. The core with transfers of the (K 1)-st auction can be characterized as follows:
Let (b, t) be an arbitrary tuple of bids and transfers that is core stable. Then the allocation x(b) maximizes social welfare, the price is zero (i.e. p(b) = 0), and there are no transfers between the players (i.e. t = 0).
Proof. The proof has three steps as follows.
Step I: core transfers are zero. Assume towards contradiction that (b, t) is core stable and + O. Consider the directed weighted graph = ([m), E, t), where E consists of all the directed edges (i,j) and the weight of each edge is tt.. The net amount of money that each player gets from transfers mt,t)) Σ)= 1j Σド=
If there is cycle C (f1,..., . ix) such that the payments along the cycle are strictly positive: &, > O.......t. &i > 0, and ti > O, then some cancellations take place. That is, by subtract- 14e ( from the weight of each edge (i.j) E C, we obtain a weighted directed graph without cycle C' and where each player has the same net amount of money as in the original graph. Iterating the operation of removing cycles, we obtain a directed acyelic graph where the players have the same net amount of money as in the original graph.
ing mi,
Thus in fact assume the transfers t such that G is acyclic.
Consider a topological ordering ( in) of the vertices G. Let ÿ be the minimum index for which vertex i has no incoming edges and at least one outgoing edge. Then mi, (t) < 0. The utility of player iy can be upper bounded as follows:
Σ (b)
(b)
Uiy = =m;)) +
Uiy.k - -p(b) (())).;,()))
<
Σ
-p(b) Izg (b).
We claim that player iy has an improving deviation by keeping its bid vector by, and stopping all payments other players. Since the other players have neutral reactions the deviations, we obtain an outcome (b, i) such that b = b, Te = 0 for all [r]]. and Un.i, S Luyis for all k + ig. The gain of player is from the deviation can be bounded by:
ui (b, t)
ui, (b, t) Us, (b, 21, (b,t)
(Since io = b.)
sr, (b)
xxy (b)
mi, (t) +
Uiy.k p(b) Fi (b)
mi, (t)
Σ k=
Vigak - -p(b) Diy xii
mi, mi, (t)
-m, (t)
(Since mi, (t) = 0.)
> 0.
(Since mi, (t) < O by choice of iz.)
30

---

Thus player ig has a strictly improving deviation, which contradicts the choice of (b, t) as core- stable with * O. Thus the assumption must have been false. follows that the only core stable profiles (if any) have t = O.
Step I: the social welfare is maximized. Next we show that if (b, t) is a core-stable outcome, then the allocation induced by b is welfare maximizing. Assume towards contradiction this is not the case. By Step I, we have t = O.
Let W1 ... Wn-K be the bids sorted in decreasing order (breaking ties lexicographically) the truth-telling bid profile v. For each j E [n K], let x be the player that submitted bid uy in this ordering.
Let Wi 2 ... wn-K be the bids sorted in decreasing order (breaking ties lexicographically) the bid profile b. Let 5 be the player that submitted bid W in this ordering.
Consider undirected bipartite graph G (L, R, E), where L is the left part, I the right part, and E the set of edges. Define
. -= ((i,)) E [n].j E [K], and (v) 2 j). For example, if 2v(v) 2, then L has nodes (7, 1) and (i, 2). If on the other hand (v) 0, then has no nodes (i, j), for any j.
R {(t,)) E [n].] [K], and (b) 2 j}.
E (s1, 82); for all 81 E L and 82 E R.
Since both allocations x(v) and x(b) allocate exactly K units, we have [L] |R] K. Consider now graph G1 (Z1, R1, F1) obtained from G as follows. Set G = G1. Then for each node (i,5) L: if the node also appears in R, then delete both copies of the node, together with any edges containing them.
Thus in G1, the left side L1 consists of nodes (i,j) with 2;(vv 2 j but (b) j. For each such node (i, let k be the rank of the valuation Vi. in the ordering т. By definition of Gr, we have that Rú does not have any node of the form (i,8) for any To see this, observe that
nodes si with s < j were deleted when constructing G, from G, and
nodes (i, s) with s 2 j do not exist even in G (if they did, then (i,j) would exist in both L and Rt and so would have been deleted when constructing Gi).
Let d(i,j) be the player that displaces player i's bid for the j-th unit at the bid profile b. Formally, d(i, j) is the owner of bid wh when considering the bids b in descending order. Let wii,j) e N be such that player d(i.j) obtains an w(i, ji-hh unit in their bundle at b.
Since x; (b) < j. we have + d(i,j). Since at the truth-telling profile player i gets a j-th unit but player dii,j) j) does not get an (i. unit, we have U. 2 (((,.))..(..j) Moreover, since the allocation x x(v) maximizes welfare but x(b) does not, the inequality is strict for some (i,j) E T1-
We claim that [ni] is a blocking coalition. To show this, we will argue there bid profile b" and vector of transfers t* such that at (b", t*) the utility of each player E [n] is weakly improved and the improvement is strict for at least one player. For each E [n].
A [K], let
Viij 10
if
otherwise.
Then x(b²) = x(v) and p(b*) = 0. Also define monetary transfers t" as follows:
Initialize t* 0. Let min (ois -a((.)).0iss)) /2. Then Ui 2 (a(is) + for each (i,j) E L1.
* For each (i,j) Tr,, let 17 (,(().)) (.. + (d(l)))wldd) +
31

---

Thus each player i that got j-th unit in their bundle at the truth-telling profile did so because their bid for the j-th unit had rank k I K. Since does not get the j-th unit at bid profile b, there is a player (iii j) whose bid for the j-th unit had rank k and who received this way a j')th unit in their bundle.
We argue that all the players weakly improve their utility at for at least one of them.
and the improvement is strict
For each pair (i,j) E L1, under the bid profile b* player receives the j-th unit at a cost of zero and transfers an amount of (d((.)).oli.)) + to player d(i,j).
The component of the utility that player i gets from unit j. counting the value, price, and transfer related to unit j. is V4, - 0 ((a(). + +) 2 0, where the inequality holds by choice of e. This is weak improvement compared to the utility that player gets from unit at profile (b, 0), which is zero. Moreover, the improvement is strict for at least one pair (i. L1, since the bid profile b does not induce welfare maximizing allocation.
For each pair (i.j) L L1 at the profile (b, 0) player gets utility vi. - -pbb from unit j. since it makes no transfers. At profile b". player gets unit at a price of zero and makes no transfers (towards other players) related to unit j. Thus the component of the utility related to unit j is vi.j 0 - 0 = Vi.j- Since p(b) 2 O, we have Uaj p(b) I Ut.j. a weak improvement for player with respect to unit j.
For each pair (i.5) & L: if (i.j) & R, then player i does not get a j-th unit under either b or b", so its utility from unit j is zero at both profiles. If on the other hand (i.j) E R. since (i.j) & L,, it must be that (i,j) R1. At profile (b, t) the utility of player from unit j is V1.j p(b) since it gets the unit and receives no transfers. At profile (b", t²) player i does not receive the unit but receives a transfer of v., + e from the player that gets the unit instead. This is again a weak improvement.
Thus all players weakly improve their utility (b*,t*) and the improvement is strict for least one player, so the profile (b, 0) is not stable. This is a contradiction, thus the assumption that x(b) is not welfare maximizing must have been false.
Step III:
the price is zero. Next we show that if profile (b,0) 0) is core-stable, then p(b) = 0. By Step I1, the bid profile b induces a welfare maximizing allocation.
Suppose towards a contradiction that p(b) > Then we show there exists a blocking coalition. Let W1 ... Wn-K be the bids sorted in decreasing order (breaking ties lexicographically) at bid profile b. For each i E [n- K]. let my be the owner of bid w,
We match the players as follows. Create bipartite graph with left part L = (TI.... Tx) (allowing repetitions) and right part R = (I T22k (allowing repetitions). For each i E [K]. create edge (T,, ki). Consider the profile (b", tt), where
if z žj
bi
0
otherwise.
Define the transfers as follows:
Initialize t* O. Set = (2K)). For each i E [K], let player n, pay an additional amount of to player TKii: L (,551:
1 + E.
Then each player i with x; (b) > 0 gets the same allocation at b' as at b, but pays a price of zero for the units and makes a transfer of most p/2 to other players, resulting improved utility compared to the utility at profile (b.0). 0).
On the other hand, each player with x, (b) 0 on the other hand gets the same allocation at b* as at b (i.e. no units), but receives a non-negative amount of money from other players, and the net amount of money received is strictly positive for all the players π TK+1y--.,, T2K.
Thus there is an improving deviation, which contradicts the choice of (b, t.) as core-stable, Thus the assumption must have been false, and p(b) = 0.
D
32

---

C.2 Core without transfers
strategy profile in this setting is described by a bid profile b, where b, = (bi,1..... b,.k) is the bid vector of player In the setting without transfers, given profile b of bids, blocking coalition needs to agree on simultancously changing their bids, such that when the players outside still bid according to b, the players in S weakly improve their utility and the improvement is strict for at least one player in S.
The core stable profiles are those that have no such blocking coalitions. Formally, we have:
Definition 5 (Blocking coalition, without transfers). Let b be bid profile. A group S S [n] of players is a blocking coalition if there exists a bid profile b, which each player S weakly improves their utility, the improvement is strict for at least one player in S, and bigj b for all i E [m] S E [K].
Definition 6 (The with transfers). The core with transfers consists of bid profiles ba which there are no blocking coalitions. Such profiles are core-stable.
The non-transferable utility core can be characterized as follows.
Theorem (Core without transfers; restated). Consider K units and K hungry players. The core without transfers of the (K + 1)-st auction can be characterized as follows:
every bid profile b that is core stable has price zero (i.e. p(b) = =0);
each allocation z where all the units are allocated can be supported in core stable bid profile b with price zero (i.e. x(b) = z and p(b) = 0).
Proof. The proof is in two parts.
Part I: the price in the core is zero. Consider a bid profile b that is core-stable. Suppose towards a contradiction that p(b) >
n Σ
Let M
Σ
V4.62 Define bid profile such that for all e [n].j [K]:
( M
j S 2bbb)
bij
(34)
otherwise.
At b, the players only submit bids equal to M > 0 for the units they are supposed to get at allocation xbb), and moreover, there are exactly K strictly positive bids. Thus x(b) = -(b).. Moreover,
p(b) since the (K + 1)-st highest bid
Then the grand coalition = [n] is blocking with the profile b, contradiction with b being core stable. Thus the assumption must have been false, so p(b) 0.
Part II: every allocation can be implemented at core-stable bid profile. Let z be an arbitrary allocation at which all the units are allocated.
Define b such that for all i [m]. j [K], we have b M Mf S 2, and b,, = 0 otherwise. Then x(b) = z and p(b) 0. Let W = {i E [x] 2 > 0} be the set of "winners" at b.
Assume towards contradiction that b is not stable. Then there is blocking coalition C (i.....,44) C in] with alternative bid profile d (d,,..... d. Denote 5 (d, b-c)) the profile where each player C' bids b, d; and each player C bids b, b, We must have u, 2 (b) for all i E C, with strict inequality for some player E C.
If ifnwW 0. then the only way for at least one of the players in C' to change their allocation is to make some of their bids at least H. But this increases the price from zero to at least H, which yields negative utility for everyone. Thus C' n W * 0. We consider two cases:
33

---

1. Case p(b)
0. Each player i E C n W requires strictly more units at b than at b, to compensate for the higher price b. Thus xx 2 for all C n W (t). If (b:b))) < 2; for some player E W \ C, there would have to exist at least K + bids with value at least H, and so p(b) 2 H, which would give negative utility to all the players including the deviators. Thus x, (b;b)) 2
for all i W \ (+).
Combining (1) and (t) gives contradiction:
Σ
xz (b(b)>
Σ
24 = K.
(ECU(W)O)
(ECU(NO)
Thus p(b) 0 cannot hold.
2. Case p(b) = 0. Then each player E Cn W requires (z(bb) 2 2,. Since p(b) = 0, the top K bids are strictly positive and the remaining bids are zero. Then each player C n W submits exactly 2; strictly positive bids. follows that x; xb)) x; (b) and p(b) p(b) for each E [n]. which means no player in C' strictly improves. Thus C' cannot be blocking.
In both cases and we obtained contradiction, so core-stable, p(b) = 0, and x(b) z as required.
D Theorems from prior work
In this section we include the theorem from [CBL06] that we use. In the problem of prediction under expert advice, there are N experts in total, and at each round t E [T):
learner chooses probability distribution Pt over [N];
nature reveals the losses (le,hee of all experts at time t, where l,s [0, L].
For given sequence of probability distributions (pi,". .Pr). the learner's regret is defined to be
T
N
T
Reg(T, (PI, .PT))
p((i) min be..
Σ
For this problem, the exponentially weighted average forecaster, also known the Hedge algorithm, defined as follows. The algorithm initializes Pi = a, an arbitrary prior distribution over the experts [N] such that each expert is selected with probability 0, O. For t 2 2, the forecaster updates
((( = Pt- (xp((-xx)ppppl exp(-1f(-11a))
ViE [N],
where 17 > 0 is learning rate.
Next we include the statement of Theorem 2.2 of (CBL06) in our notation.
Theorem 7 (Theorem 2.2 of [CBL06]). Consider the exponentially weighted average forecaster
with N experts, learning rate > O, time horizon T, and rewards in [0, Suppose the initial distribution on the experts is uniform, that a
The regret of the forecaster
is
Reg(T, (pI...., ... ,PT)) < log N
Tn 8
The following corollary a well known variant of the above theorem, to allow rewards in an interval
[0, L) and an arbitrary initial distribution over the experts.
Corollary 1. Consider the exponentially weighted average forecaster with N experts, learning rate 7 O. time horizon T, and rewards [0, L). Suppose the initial distribution on the experts a.
The regret of the forecaster is
1 0;
TL
Reg(T,, (p1.... ..r.) < max log
+
[E[N]
8
34

---

The proof of Corollary is identical to that of Theorem 7, except for the following two differences:
Instead of W, E exp(-1) exp(-nEuse (ai). we define W, E o, exe(((-1) Eoge l,xi) In this way,
log
WT Wo
log WT -1 min E
Σ
l,a
max log NN
1
di
When applying (CBL06, Lemma 2.2], we use the interval for the rewards as [0, L] instead of [0, 1].
35


Reviews:
[{"review_id": "2W8PMqexeN", "reviewer": "Reviewer_ZdSw", "summary": "In this paper, the author proposes efficient algorithms that players can use for bidding, in both the offline and online settings. Furthermore, the paper shows regret lower bounds and then analyzes the quality of the equilibria in two main variants of the auction. It focuses on studying uniform price auctions the angle of designing bidding algorithms for the players.", "questions": "Please refer to the weakness section.", "limitations": "Please refer to the weakness section.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper well points out several limitations regarding multi-unit uniform-price auctions that previous works have not focused on and addresses the novel algorithm for those limitations with online and offline settings for bidding with many theorems and their proofs.", "weaknesses": "Regarding a carbon auction, licenses for CO2 emission mentioned in the abstract are not well delivered in the paper. Moreover, The abstract seems to be different from what I see on the review page. Please be consistent with the abstract that the authors deliver.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\n- The uniform price auctions play a pivotal role in determining the allocation of CO2 emission licenses in the EU Emissions Trading System (EU ETS). See also the paper “Reducing Inefficiency in Carbon Auctions with Imperfect Competition, ITCS 2020”, which explains the auction model used for carbon emissions and gives additional references.\n- In these auctions, learning effective bidding strategies is challenging. This is because of the nontruthful nature of the auction and the bid space being exponentially large, which the paper addresses. \n- The relevance of revenue obtained from these auctions holds paramount importance in the context of the carbon market. This revenue can potentially drive investments in green technology and further sustainability initiatives.\n"}, {"review_id": "nJ6PQvczir", "reviewer": "Reviewer_bLMv", "summary": "This paper studies the problem of learning to bid in a multi-item auction. There are k identical item to be sold. Each bidder has decreasing value v_1, v_2, ..., v_k with value v_j for j'th item allocated to the bidder. The auction allocates to the k highest bidder and charge k'th or (k+1)'th price. It's worth noting that k'th and (k+1)'th price are neither truthful nor first price in this setting. It has the value of being fair - same price is charged to all bidders. However, it is not truthful as the (k+1)'th bid might belong a bidder obtaining some of the items and that bidder might have an incentive to mis-report. \nThe authors consider two problems in this setting: how does the bidder learn to bid with low-regret in this setting and what type of equilibria can be obtained that are core-stable (no subset of bidders can deviate to obtain a better outcome. \nFor the first, the authors provide an offline algorithm for computing best-response to a history of bids by the competitors, provide a low regret algorithm when in each round the full vector of bids is revealed and provide a low regret algorithm when in each round only the winning price and the allocation to the individual player is revealed. The authors also provide a lower bound example to bound the minimum regret that is unavoidable. \nThe authors also study equilibria that are core-stable - however even though this is an auction setting they only consider settings where the players other than the auctioneer deviate. They show that (k+1)'th price can only have zero price pure Nash equilibria that are core stable. \n\nThe paper is very well written. All the arguments are detailed and easy to follow. All the proofs are in the appendix but the statements in the main body are clear enough to give the sense of the result and a sketch of how the result is obtained. \nFor the learning to bid results, the authors map the problem of computing optimal bid to finding a maximum weight path in a directed acyclic graph. With this mapping, they use existing technology to instantiate the hedge algorithm to explore paths. For the bandit setting where only signal about the price and number of units won is available a slower update along the path that won is used. \n\nI am not sure about the value added by the equilibrium analysis. It is not related to the other set of results. Authors show bad properties of the (K+1)'th price auction, and conclude that k'th price auction might be preferred - however that conclusion is not clear. \n\nUpdate post rebuttal:\nThank you for the rebuttal. It seems fair to restrict to just uniform price auctions. Perhaps the authors can make this more explicit and include further justification in the paper. \nFor the preference between (K+1)'th, k'th price - I am not sure authors fully addressed this question. Agreed that zero revenue equilibria are bad and the auctioneer would like to know about that, but with the k'th price not even having a pure Nash equilibrium, how should the auctioneer choose? Perhaps the authors should explore non-pure Nash equilibria for k'th price and show that those guarantee non-zero revenue? \nIt would also be good if the authors could tie together the no-regret analysis with the pure Nash equilibrium analysis - may be by making statements about the coarse-correlated equilibria of the two auction formats.", "questions": "Is the conclusion that k'th price is preferable clear? Is there any other connection to the rest of the paper of this equilibrium analysis?", "limitations": "Authors discuss open questions remaining. There is no potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is well written. Explains all the results well and provides adequate details in the main body and the appendix. \n- The algorithms for learning to bid are non-trivial, they build on existing technology but require ideas specific to the model.", "weaknesses": "- The results for equilibrium analysis seem unrelated and don't add a lot of value. The conclusion about k'th price auction being preferred is not clear. \n- The authors assume that uniform pricing auction is preferred. This could use more justification. Perhaps true first price or truthful payment rules are also worth studying. Would the regret analysis extend to those as well?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\n- Regarding equilibria, the possibility of learning algorithms promoting collusion is a significant worry. Thus, using an auction like the K+1-st, which features equilibria with zero prices, presents issues. These equilibria are not just resistant to coalition deviations but are also quickly identifiable by buyers. While participants might see this as beneficial, it does raise concerns about the auction's effectiveness.\nDelving into the understanding of Nash Equilibria (NEs) further sheds light on worst-case scenarios, providing valuable insights for the auctioneer. An illustrative example of this importance lies in the context of the carbon market. Here, revenue generation stands as a pivotal objective, as the obtained revenue predominantly fuels investments in green technology. \n\n- Regarding K-th price auction being preferred, uniform price auctions utilizing the K-st pricing rule do not allow for an equilibrium with zero revenue. This observation holds significant relevance and should be taken into consideration when deciding upon the appropriate variant of uniform pricing to adopt.\n\n- Regarding uniform pricing: Uniform pricing stands as a fundamental concept, on par with market equilibrium where the demand and supply get matched. Its practical application spans diverse sectors such as electricity, carbon trading, and institutions like the Bank of England and Treasury. Its pricing mechanism is perceived fair, which is important in settings such as carbon trading.\n\n- Regarding regret in auctions beyond uniform pricing: Our analysis covers the special case of K=1, including first price and second price auctions using the K+1st and K-th pricing rules.\nAdditionally, our study establishes a strong link to graphical models, suggesting applicability in exploring other auction formats like GSP and GFP. However more analysis is needed to fully solve other formats which we believe would belong to future work.\n"}, {"review_id": "57SKGq8K9a", "reviewer": "Reviewer_KDVH", "summary": "This work systematically considers computational, learning-theoretic, and game-theoretic aspects of multi-unit auctions with uniform pricing. In such auctions, $K$ identical goods are sold to agents with quasilinear utility with a uniform pricing scheme set to either the $K$th or $(K+1)$th highest overall bid (note bidders submit a list of $K$ nonincreasing bids for receiving subsequent goods by diminishing returns). On the computational side, it is shown that the offline optimization problem of maximizing hindsight utility given a history of competing bids (subject to discretization) can be nontrivially and efficiently reduced to computing a max-weight path in a DAG; a similar transformation is then used to devise no-regret algorithms in the online setting in both full-information and bandit information settings. These are complemented by nontrivial regret lower bounds. Finally, this work characterizes the core-stable allocations and prices in these settings to suggest that $K$th price auctions may be more resilient than $(K+1)$th price auctions in practice.", "questions": "---In general, this paper is quite well-written --- the authors provide nice discussion of the relevance of this setting as opposed to other natural auctions with (implicitly) discriminatory pricing, like GSP, as well as other related work.\n\n---I was not able to verify all the proofs in detail, but the general structure and ideas explained in the text made general sense.\n    \n---Are these results robust/naturally extendible in some way to the setting where the parameter $K$ instead is a time-varying parameter $K_t$?\n\n---On the learning-theoretic side, is it clear that existing online shortest path learning methods, i.e. FTPL, cannot work ``out-of-box'' in this setting after applying the (new) reduction? Or does the analysis done here to invoke Hedge guarantees seem necessary to re-do?", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The considerations given in this work to this setting are fairly comprehensive on a multitude of axes as listed above. The paper is fairly well-written and provides nice discussion of the problem and related work.", "weaknesses": "There remains a fairly large gap between the bandit upper and lower bounds; it's not entirely clear at present whether or not existing learning methods could resolve this gap easily.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\n- About lower and upper bounds: Despite our attempts to enhance these bounds, the ones presented in the paper remain the best results we could attain. Thus we leave this as a future work. Thank you for your understanding.\n\n- Regarding $K_t$: When the number of units $K_t$ is varied over time, our offline algorithm, which leverages a Directed Acyclic Graph (DAG), can be extended by adjusting edge weights according to $K_t$. Furthermore, our learning algorithms, designed for both full information and bandit settings, can be expanded by integrating the modified DAG into an environment where the bidder does not possess knowledge of $K_t$ at the time of bidding in round $t$.\n\n- Regarding FTPL: Yes you are right that FTPL can also achieve a sub-linear regret in $T$ for both full information and bandit settings. However, we found that the regret achieved by FTPL appears to be worse than that achieved by the Hedge algorithm in our problem. Take the full-information setting as an example: by adding independent exponential distributed perturbations with rate $\\eta$ to each edge weight, the regret upper bound from the regularizer part scales as $K\\log m/\\eta$ (m is the number of discretization levels). For the sensitivity part, an upper bound is $K^2 m \\eta T$ ($T$ rounds, per-step reward upper bounded by $K$, $Km$ edges in total, and total variation distance $\\eta$ between two shifted exponential distributions). Choosing the optimal $\\eta$ to balance these two terms gives us a worse regret upper bound than Hedge. Therefore, we decided to use Hedge in this work. \n"}, {"review_id": "72wDz6B0R8", "reviewer": "Reviewer_5cGR", "summary": "The paper considers a repeated autcion setting where\nthe players submit their bids for an item of which $K$ units are avaialble.\nAn auctioneer computes a price $p$ \nand allocates the j-th unit to the\nowner of the j-th highest bid, charging the price p$ for each unit.\n(I did not understand this part completely, see \"Questions\" below)\nThe players have quasi-linear valuations with decreasing marginal returns.\nThe paper considers the problem in both an offline and online settings.\nThey derive upper boudns on regret for the full information\nsetting, where the bids are public, and the bandit feedback setting,\nwhere each player only observes the price and their own allocation.\n", "questions": "The disucssion of the model is pretty confusing to me.\nHow does the auctioneer allocate the units?\nThe paper repeatedly says\n\"the j-th unit to the player that submitted the j-th highest bid\".\nBut the players have different bids for different units.\n\nDoes the auctioneer simply allocate each item to the player who has the highest\nbid for that item given the previous allocations? This would be the most reasonable\nthing to do. \n\n", "limitations": " ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper considers an interesting problem. \nRepeated multi-unit auctions are widely used in practice.\nThe problem formulation is nice and could lead to interesting follow-up works.\n", "weaknesses": "I found the writing to be somewhat confusing. In particular, \nsince the our results section does not end till page 4, the model\nshould have been described in more detail earlier on.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\n- Regarding the model: The model can be located on page 2 immediately after the introduction. We placed the model early within the paper to facilitate a comprehensive understanding of our contributions within the framework of our proposed model.\n\n- Regarding the allocation rule: The formal depiction of the allocation rule can be found in Section 1.1, while an illustrative example is provided in Example 1 within the appendix. In particular, consider the labeling of units as $1, 2, ..., j, ..., K$. The sentence \"the j-th unit to the player that submitted the j-th highest bid\" precisely signifies the allocation rule's operation: participants submit their bids, the auctioneer arranges these bids in descending order $(c_1, ..., c_j, ..., c_{n * K})$, and then allocates unit 1 to the bidder with bid $c_1$, unit 2 to the bidder with bid $c_2$, and so on.\n\n- Furthermore, it's important to note that the allocation at time t solely depends on the bids submitted by bidders in round t, excluding any prior rounds. As an example, let's consider K = 2 units and two bidders. In round 5, suppose bidder 1 submits the bid vector [4, 2], and bidder 2 submits [5, 3]. After sorting the bids – [5, 4, 3, 2] – the first unit is allocated to bidder 1, and the second unit goes to bidder 2 (this being the allocation in round 5). Notably, this allocation disregards any events from preceding rounds.\n\n"}, {"review_id": "9qlRZfGPOK", "reviewer": "Reviewer_BfUK", "summary": "This paper studies the setting in the multi-unit auction where there are $K$ items to allocate and buyer are not necessarily unit-demand and have quasi-linear valuations with decreasing marginal returns. The bidder set separate bid for each item, and each item goes to its highest bidder, where the price can be either the $K$-th bid, or the $K+1$-th bid. The goal is to design a low-regret algorithm from a bidder's perspective, with the goal of maximizing his utility defined as the value minus payment for the winning items. This paper gives a collection of interesting results:\n\n- a DAG construction of the construction for one bidder, and a proof for the bijection between the bid vectors and paths in the offline setting\n- Reduce the learning problem as an online maximum weighted path problem, and a weight-pushing algorithm as a solution to the online full information setting\n- Regret lower bounds for the setting. \n- Equilibrium analysis of this auction.", "questions": "- Is it possible to generalize this regret against an adaptive adversary to the policy regret?\n- The equilibrium analysis seems to imply this auction doesn't guarantee any positive revenue, why is it essential to study considered on this result? ", "limitations": "- no empirical experiments. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper provides several interesting results. \n- The model is well-motivated and the intro is clean and informative. ", "weaknesses": "- No empirical experiments, but that's fine since this is a theoretical paper. \n\nHere are some additional comments regarding the presentation:\n- The abstract in the pdf version is different from the abstract in the OpenReview system. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\n- Expanding to policy regret: Achieving a deeper understanding of policy regret involves transforming our current setup into a contextual bandit framework with an exponential range of contexts. This challenge presents an exciting avenue for future research.\n\n- Regarding  the Importance of Uniform Price Auctions and Their Variants: It's essential to highlight the distinction between uniform pricing auctions under the K+1-st pricing rule—yielding zero-price equilibria—and the K-th pricing rule, lacking this property. This distinction holds significance when selecting an appropriate uniform pricing variant due to its wide adoption.\nFurthermore, uniform pricing is foundational, achieving equilibrium by matching demand and supply. Its application spans electricity markets, carbon trading, and institutions like the Bank of England and Treasury. The pricing rule in this auction is perceived as fair, and fair pricing mechanisms are particularly relevant in high stakes settings like carbon trading.\nGiven these factors, studying uniform price auctions is well-justified. The interplay between pricing variants and their real-world implications underscores the importance of this investigation for informed decision-making.\n\n\n"}, {"review_id": "JkD9thGwOd", "reviewer": "Reviewer_Ge2c", "summary": "This paper studies a setting where a single seller runs repeated multi-unit auctions. In each multi-unit auction, there are $K$ identical units of good for sale. Each buyer individually has a valuation for the good with decreasing marginal returns and submits a bid vector. The seller will allocate the units according to the ranking order of the bids, and use uniform pricing. Specifically, the seller will set the price to be the $K$-th highest bid (or $(K+1)$-st highest bid in another variant). Such an auction format takes place in many important real-world settings, such as license auctions for CO2 emissions, ad auctions on online platforms.\n\nThe authors first show how to efficiently compute an optimum bid vector in the offline setting, which also serves as a benchmark bidding strategy for performance evaluation in the online setting. In the online setting, they can design algorithms with polynomial running time and low regret under either full information feedback or bandit feedback. They also give a lower bound on the expected regret of this problem. Additionally, they analyze the equilibria in the two variants of the auction to study whether they are susceptible to bidder collusion.", "questions": "1. I don't see why the authors concludes with a summary that the $K$-th price auction format may be preferable to the $(K+1)$-st price auction. Theorem 6 is a negative result about the core stable profile in the $(K+1)$-st price auction while the $K$-th price auction does not even have a pure Nash equilibrium. Why are they comparable?\n\n2. Minor comments.\n- In line 65, $z$ is used to denote an allocation, but then in the following paragraph, $x$ is used to denote the allocation. And $z$ is later used to denote a vertex in DAG.\n- I personally feel that \"repeated auctions\" is the only accurate expression, while \"repeated mechanisms\" (line 33), \"repeated setting\" (line 76), \"repeated auction\" (line 272) are not appropriate expressions.\n- Line 195, the angle -> from the angle.\n- Line 201, such problem -> such a problem.\n- In the definition of $S_i$ (equation 1), no value for $t$ (the superscript) is given.\n- The key evaluating metric, regret, is not defined in the model part.\n- There are some meaningless repetitions. For example, lines 220-223 almost repeat lines 89-93, the footnote on page 6 repeats the meaning of $x_i$ in line 68.\n- Example 1 can help readers to better understand the model, so I think it is better not to defer it to the appendix. \n- When $K=1$, the problem then becomes bidding in repeated first-price ($K$-th price) or second-price ($(K+1)$-st price) auctions. Pointing out the special cases may help readers better understand why the $k$-th price auction does not have a pure Nash equilibrium, and why the $k+1$-st price auction is more susceptible to bidder collusion.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. This work contributes the line of literature on multi-unit auctions by considering dynamic bidding strategies rather than focusing the seller's side. The model is well built on previous work of mechanism design in combinatorial auctions, learning algorithm design in repeated auctions, and has significant implications for real-world issues such as license allocation.\n\n2. The main insight that the bidder can compute an optimum bidding strategy in the offline setting by finding a maximum wight path in a DAG is quite novel. Particularly, the weight of an edge appears to depend on the whole bid vector but turns out to rely only on two neighbor bids, which I find quite interesting. Moreover, it also requires non-trivial techniques to design unbiased estimators for the bandit feedback model.\n\n3. Other characterizations about this problem are provided, including regret lower bounds and equilibrium analysis.\n\n4. All results and proofs are well written.", "weaknesses": "The organization of this paper looks weird to me. Section 1.2 covers more than two pages. In particular, \"equilibrium analysis\" is one of the contributions but all the results about it are piled up in Introduction without an independent section. The paper is titled with ``online learning'', so I assume the algorithms for the online setting should be the highlight of this work, but now Subsubsection 1.2.3 accounts for more than half of Subsection 1.2.\n\nActually, this part of equilibrium analysis seems to have almost no connection to the $T$-round setting. Theorem 3 and 4 only give regret upper bounds, and do not analyze the convergence of the algorithm. No-regret learning algorithms can converge to a coarse correlated equilibrium, but there is no guarantee of convergence to any pure Nash equilibrium. Therefore, this part in fact studies the pure equilibria in a static setting from the perspective of the seller, aiming to figure out which kind of uniform pricing is a better pricing rule. Maybe the authors should consider changing the title to enlarge the scope of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\n- Regarding Section 1.2 and Coarse Correlated Equilibria (CCE) and K+1-th pricing rule: Let us first note that in essence, our contribution introduces a learning algorithm for bidding which can enhance comprehension of CCEs within uniform price auctions.  This can be done by simulating our learning algorithm in various settings. This application holds practical significance.\nMoreover, our equilibrium analysis results in Section 1.2 bear substantial value for decision-makers. Specifically, they spotlight a critical distinction: while uniform pricing auctions under the K+1-st pricing rule yield equilibria with zero prices, the same does not apply to the K-th pricing rule. This observation is important given the prevalent use of uniform price auctions.\n\nIn any case, we are open to changing the title of the paper to reflect the additional results we have in Section 1.2 for NEs.\n"}]

Author rebuttal:

Meta-review: Overall, reviewers are all leaning towards acceptance. 

Some strengths reviewers mentioned to support the decision:
(1) This paper is well-written.
(2) The problem considered is well-motivated.
(3) The technique to solve the problem is non-trivial and novel.

The reviewers also gave some weaknesses and comments for further improving the paper. In particular, these could be done before publication:
(1) Reviewers have some questions on the connection between the equilibrium analysis and the rest of the paper. Adding some discussions  maybe helpful for readers.
(2) It might be also helpful to add some lines explaining how the conclusion that k-th price is more preferrable after Theorem 6.
Decision: Accept (poster)